All possible binary trees given only one traversal

1
votes

Given an inorder traversal only (or postorder/preorder only) traversal of a binary tree (not necessarily a BST), how does one code to generate all possible binary trees given this traversal?

I understand that the number of binary trees possible given 'n' nodes is (2^n)-n but if we have access to a single traversal of the tree, how can we code this algorithm?

2
treetraversal

2 Answers

0
votes

Do it recursively.

def emptyTree():
    return None

def node(l,d,r):
    return (l,d,r)

def singleton(x):
    return (emptyTree(),x,emptyTree())

def allBT(trav,length):
    if length == 0:
        return [emptyTree()]
    if length == 1:
        return [singleton(trav[0])]
    trees = [node(emptyTree(),trav[0],right) for right in allBT(trav[1:],length-1)]
    trees += [node(left,trav[i],right) for i in xrange(1,length-1) for left in allBT(trav[:i],i) for right in allBT(trav[i+1:],length-i-1)]
    trees += [node(left,trav[length-1],emptyTree()) for left in allBT(trav[:length-1],length-1)]
    return trees

def allBinaryTrees(trav):
    return allBT(trav,len(trav))

By the way, your number of binary trees is wrong. There is exactly one tree with 0 nodes and one with 1 node, there are 2 with two nodes. The recursion is

T(n) = \sum_{i = 0}^{n-1} T(i)*T(n-i-1)

since we can pick each item to be the root and can combine each possibility for the i nodes before with each possibility for the n-i-1 nodes after. Thus T(3) = 5, T(4) = 14, T(5) = 42, T(6) = 132, ...

0
votes
function Node(data) {
    this.data = data;
    this.left = null;
    this.right = null;
}

function Tree(arr, start = 0, end = arr.length - 1) {
    let trees = [];
    if (start > end) trees.push(null);

    for (let i = start; i <= end; i++) { // consider 0 to end all as root node one by one.
        let leftTree = Tree(arr, start, i - 1); // find left subtrees possiblr for node i
        let rightTree = Tree(arr, i + 1, end); // find right subtrees possiblr for node i

        // make all combinations of leftTree and rightTree
        for (let j = 0; j < leftTree.length; j++)
            for (let k = 0; k < rightTree.length; k++) {
                // cretate result tree and push in result arr.
                let root = new Node(arr[i]);
                root.left = leftTree[j];
                root.right = rightTree[k];
                trees.push(root);
            }
    }
    return trees;
}

let result = Tree([4, 5, 7]);

console.log(result);

//Output
// 4 5 7
// 4 7 5
// 5 4 7
// 7 4 5
// 7 5 4