**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