All possible binary trees given only one traversal

Question

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?

Answer 1

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, ...