Why it is impossible to construct Binary Tree with Pre-Order, Post Order and Level Order traversals given?

Question

Given:

1. Pre-Order Traversal.
2. Post-Order Traversal.
3. Level-Order Traversal.

One can not contruct a Binary Tree with 12 or 23 or 31 or even if 123 are given! Why is this? and Why InOrder Traversal is very important to construct the original Tree?

Answer 1

We can't build a tree without the in-order traversal. Why? Let's say you are given the pre-order and post-order traversals only.A simple example is shown below.
Consider two different trees,

TREE 1:

root=a;  
root->left=b;  
root->left->right=c;  

Tree 2:

root=a;  
root->right=b;  
root->right->left=c;  

Both the trees are different, but have same pre-order and post-order sequence.

pre-order - a b c  
post-order - c b a  

This is so because we cannot separate the left sub-tree and right sub-tree using the pre-order or post-order traversal alone.

Pre-order, as its name, always visits root first and then left and right sub-trees. That is to say, walking through a pre-order list, each node we hit would be a "root" of a sub-tree.

Post-order, as its name, always visits left and right sub-trees first and then the root. That is to say, walking through a post-order list backward, each node we hit would be a "root" of a sub-tree.

In-order, on the other hand, always visits left sub-tree first and then root and then right sub-tree, which means that given a root(which we can obtain from the pre-order or post-order traversal as stated above), in-order traversal tells us the sizes of the left and right sub-trees of a given root and thus we can construct the original tree.(Think this out)

Same is the case with level-order traversal. Thus if we want to obtain a unique tree we need an in-order traversal along with any other of the three traversals.
Note - The exception is of course a full binary tree, in which pre-order and post-order traversals can be used to construct the tree, as there is no ambiguity in tree structure.