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

• sandeep pandey: @daniel-fischer can you please help me with this question
• OneCricketeer: That is not how you notify someone. You can @ with their username
• castletheperson: I don't think you posted the right strings. There is no letter O in the question string, so C can't be correct.
• OneCricketeer: @4castle Probably a keyboard issue. The 0 and O are supposed to be D, I think
• Masum: Same question answer is given in Quora. quora.com/…

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.

• sandeep pandey: "you know A is the root, so the question is whether B or D are to the left or right of A." why are you only considering B or D . why not BF or DE (assuming you are comparing given pre-order options)
• sandeep pandey: "If this is a truly ordered binary-tree, the B is to the left. This rules out option B." -- I'm not sure if they are talking about truly ordered binary tree. What if they r not talking about truly ordered binary tree. I understand they can many possibility but we need see pre-order and post-order and find which pre-order is consistent with post-order
• OneCricketeer: To address first comment. You, for sure, get A as the root. I think we agree there. I only consider B and D because those are your only choices in your question. You either have AB or AD as options.
• OneCricketeer: And I edited to clarify why option B is ruled out in case top-down ordering is not applied.

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

enter image description here

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

• sandeep pandey: it is clear that A will be the root. On what basis you put in B, C in left and Right children, there can be other way around and same goes for others DEBFC
• Akshay: See the edit for explanation after you know A is the root.Cheers
• sandeep pandey: On what basis you claim "DEB will be the left side of the binary tree and FC " Because All DEBFC could be left subtree or right subtree. Saying every node can have at most 2 children doesn't prevent "DEBFC " altogether to be part of either left subtree or right subtree. Plz refer ugcnetsolved-computerscience.blogspot.in/2012/09/… and go comment section . thx
• Akshay: Alright.To make it simpler and from the point of view of this question you cannot generate tree for options A B and D.try that it will be easier.
• Akshay: to answer your question as to what basis "DEB" is left and "FC" is right....root is A.then it comes left to right so DEB and FC as DEB is the leftmost part in the post-order.But in MCQ I suggest you to go from the options and try to eliminate other options.reach out if you have more doubts.Cheers!