0
$\begingroup$

This question appeared in my data structures examination :

You are given that GDCBFAHEJ is an in-order traversal and GCDBHJAEF is a post-order traversal. Either build the unique tree for which these are traversals or argue that they are traversals of different trees.

Why are we unable to build a unique tree, despite of having a in-order & post-order traversal? Please explain.

Improve this question
$\endgroup$
1
  • $\begingroup$ Look at the 2nd alternative: or argue that they are traversals of different trees. $\endgroup$
    – greybeard
    Commented Mar 5 at 18:34

1 Answer 1

Reset to default
0
$\begingroup$

Given the in-order and the post-order, there is indeed a unique corresponding binary tree.

Since $F$ is the last node in the post-order, it is the root of the tree.

In the in-order, the root of the tree separates the in-order of the left tree (hence GDCB) and the in-order of the right tree (AHEJ).

That means that the left tree is of size 4. In the post-order, the first 4 nodes must represent the post-order of the left tree (GCDB). Similarly, the post-order of the right tree is HJAE.

Using the same method recursively, we get that the left tree is:

    B
   /
  D
 / \
G   C

But the problem is that when using the method on a tree with AHEJ as in-order and HJAE as post-order, we get that the root must be E, but then it decompose the in-order as AH (in-order of left tree), E (root) and J (in-order of right-tree). Can you see how it is a contradiction with the post-order?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.