# All possible binary trees given only one traversal

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?

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 theinodes before with each possibility for then-i-1nodes after. ThusT(3) = 5, T(4) = 14, T(5) = 42, T(6) = 132, ...

Tags: tree, traversal