Thursday, September 8, 2011

Build a Binary Tree, given two traversals

Given two traversal sequences, can you construct the binary tree?

Answer: If one of the traversal methods is Inorder then the tree can be constructed, otherwise not.

Why?

Have a look - 

         A                A
        /                      \
     B                         B
      
      
Preorder and Postorder traversals are same for the trees given in above diagram. So, by just looking at pre and post order, we cannot be sure of the actuall tree.

Preorder Traversal  (root->left->right) = AB
Here we know that A is root for sure, but B is left or right - we dont know.

Postorder Traversal (left->right->root) = BA
Here we will know that last element A is always the root. But B may be left or right.

Thus, even if we have the data from pre and post order  here, there is still no clarity about B being the left or right. If we get inorder in combination with pre OR post - we can determine the tree.

Therefore, following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.

And following do not.
Postorder and Preorder.

References - 

http://geeksforgeeks.org/archives/6358

No comments:

Post a Comment