Constructing Binary Tree given Post order

Question

How to construct binary tree if only information given is post order traversal. Having googled on subject, i understood in such case there can't be unique constructed binary tree. But if given Integers it becomes easy to create BT based on less or greater then property . But if we have alphabet then i'm not able figure out on what basis we make left node or right node of Parent Node. Here is question which i'm trying to solve .

Q) The post-order traversal of a binary tree is DEBFCA .Find out the pre-order traversal?

Options :
(A) ABFCDE
(B) ADBFEC
(C) ABDECF
(0) ABDCEF

Correct Answer is : C

Can someone explain how do we reach to answer.

I found this answer https://www.quora.com/If-the-post-order-traversal-of-a-binary-tree-is-DEBFCA-how-can-I-find-out-the-pre-order-traversal/answer/Eugene-Yarovoi?srid=zy7j very helpfull but 3rd step onwards i don't understand how things are happening. Thanks for your time

Answer 1

if given Integers it becomes easy to create BT based on less or greater then property . But if we have alphabet then i'm not able figure out on what basis we make left node or right node

Well, in Java ("B" > "A") == true because strings are compared lexicographically...

The post-order traversal of a binary tree is DEBFCA

By the definition of post-order, you know A is the root, so the question is whether B or D are to the left or right of A. (if you consider the choices given to you)

Also from the post-ordering, you know D must be the very-left element because it is at the start of the post-order string. Now you can rule out option A (D is not a child of C) and option B (D is not immediately left of A).

At this point, you can determine your tree looks like so because the post ordering ends in CA and starts with D

    A 
  B    C
 ...   ...
D     ......

In the post-order, you have FCA, so F would be a child of C, which is a child of A for that to happen in that order.

    A 
  B    C
 ...   ...
D     ...  F

We've completed all but E. From the post-order, you have DE, and we have D as the very left leaf, so E must be it's sibling.

And here is the complete tree (the position of F is interchangeable, I think)

     A 
  B    C
D  E     F

Through elimination, option C remains.

Answer 2

The general algorithm for preorder traversal goes as follows,

public void preorder(Node n) {
    if(n == null) {
        return;
    }
    System.out.println(n.data);
    preorder(n.left);
    preorder(n.right);
}

So when going through preorder traversal, the first thing it does after verifying a node isn't null is print out the node's value. Then it goes on to recursively call the method on the node's left children first, right children second. Therefore, it should be easy to see the first three letters being ABD since the preorder method will be recursively called on the farmost leftside of the tree. D has no children, so the preorder traversal goes back to its method call on B. Now B's right child is visited, hence the order is now ABDE. E has no children, so the preorder traversal goes back to B. But all of B's children have been checked, so now it goes back to A. Now the preorder method is called on A's right child. The order now is ABDEC. C only has a left child, so the preorder traversal is completed after visiting F and the final order is ABDECF.

Answer 3

Many a times in multiple choice questions there are typos.Its same here there is no O. Unique tree can not be drawn just by post order to answer we have to search a possible pre-order which can be as below (ABDECF) so ans is C (assuming the typo in option) since A is at last in post order so it must be root so one possible tree is as

After you know A is the root we are left with only DEBFC. Here some of the nodes belong to the left side of the binary tree and some belong to the right side. How many nodes belong to the left and how many belong to the right. Since left side of the binary tree is considered first, and since every node is expected to have at most two child, DEB will be the left side of the binary tree and FC would be the right.Now, we know that FC is in the right side of the binary tree. Again the last node would be the root of the sub tree and F its left side.Next we come to the left side of the binary tree and it is DEB. Again B would be the root of the sub tree. D and E are its left and right side respectively.Thus the tree is created!!