Can we construct a full binary tree with only post

Question

For example, we are provided with only post order traversal array or only pre order traversal array. Can we reconstruct the binary tree back? If we know that the binary tree is full. Moreover, if it is not, is it possible to construct the full binary if know both preorder and post order at the same time?

Answer 1

Suppose you had a tree w/ 3 nodes, all labelled the same. There are at least 3 such (not-necessarily full) trees, but all will have the same traversal arrays, no matter what order. That should answer your first question.

Answer 2

I was playing with the orders a bit to understand them better and here are my findings:

• Post-order - from the sequence you can always tell what is the root and what is the right-most child (ex. is 1,2,3,4,5 - 5 is the root and 4 is the right-most child)
• Pre-order - from the sequence you can always tell what is the root and what is the left-most child (ex. is 1,2,3,4,5 - 1 is the root and 2 is the left-most child)
• In-order - given a root vertex, you can always tell what is on the left and what is on the right (ex. is 1,2,3,4,5 and for the root 3 - 1,2 are on the left, 3,4,5 are on the right )

Now you can play with it. Having an in-order with either post-order or pre-order, you can easily reconstruct the tree because you can find the root and recursively find it always for the left/right branch. In case of having pre-order and post-order together, you can find the root and left-most children & right-most children. The problem happens in case the root has only left/right children, because you cannot tell which one it is and as such, you cannot easily reconstruct the tree.

However, as being asked, having the "full" binary tree, where every vertex has either both children or any, you don't have the problem with pre/post order combination and therefore every pair of orders will help you to reconstruct the tree. However only having one of the orders, you cannot reconstruct the tree (for example knowing only left child is not enough, you don't have information about which is the right one)

Answer 3

No, you can't from one list alone.

think of the postorder list: 4 5 2 3 1

    1         1   
   / \       / \
  2   3     4   3
 / \           / \
4   5         5   2

both trees are possible, but we don't know which one generated the list

Assuming every element in the tree is unique, we know that preorder is build like that:

[Node][     LeftTree     ][     RightTree     ]

and postorder like this:

[     LeftTree     ][     RightTree     ][Node]

if we have two lists, preorder 1 2 4 5 3 and postorder 4 5 2 3 1, we know that 1 is the root of the tree, because it is the first number of the preorder list (and the last number of the postorder list). Furthermore we know that 2 must be the root of the left tree and 3 the root of the right tree, because they are the first numbers after the root node which are roots of the left or right tree. With this in mind we can split the lists into this:

           [Root in preorder] [ LeftTree ] [RightTree] [Root in postorder]
preorder:        [1]             [2 4 5]      [3]     
postorder:                       [4 5 2]      [3]              [1]   

From here you can do this algorithm recursively with the left and right tree and in the end you get this:

    1     
   / \      
  2   3    
 / \       
4   5

Since every element is unique there is only one way to build the tree and therefore you can rebuild a tree from its postorder and preorder list.

In case you have elements that are the same you can't build a unique tree, example:

preorder:  1 X X 5 X
postorder: X 5 X X 1

from these lists you could create these two trees:

    1         1   
   / \       / \
  X   X     X   X
 / \           / \
X   5         5   X