Need quick help on binary tree!!!!

[xonxon]

The following code lists the nodes in a binary tree in two different orders:
preorder:C,B,A,E,D,F,H
postorder:A,B,D,H,F,E,C
Draw the binary tree.
The answer is :
                                      C
                                   /     \
                                 B       E
                                /       /   \
                              A       D    F
                                            /
                                          H
so, my question is how should i think or is there any quick method to get the above answer?I know how to draw a binary tree by its sequence but become confuse in the other way round just like this question.Please help me as soon as possible.thanks.

[Narue]

If you want an algorithm, I'd recommend looking for patterns in the traversal results.

For example, the root is the first hit in preorder and the last hit in postorder. You can go from left to right in preorder and find the left parent vine (C, B, A in your case), but if you go from right to left in postorder you can find the right parent vine (C, E, F) with little difficulty.

However, just given preorder and postorder, you can't reconstruct the tree perfectly. For example, is H the left child of F or the right child? The preorder and postorder results will be the same for both. If you have an inorder traversal as well, you can reconcile the ambiguity.

[nucleon]

There would seem to be method in such madness. But, as Narue said, you cannot entirely solve the tree without an inorder traversal as well.

The problem should be solved recursively, as you might expect.

pre:  C B A E D F H
post: A B D H F E C

Either the first node of preorder or the last node of postorder gives you the top node in the current subtree. So in this case it is C. Enter that into the tree diagram and remove it from both lists, realigning them:

pre:  B A E D F H
post: A B D H F E
                                  C

Note that the lists divide into two parts indicated by the repetition of letters in different permutations. These are the left and right subtrees of the current subtree:

pre:   B A   E D F H
post:  A B   D H F E

Divide the problem into those two subtrees, go back and solve recursively.
That's basically it.

Continuing on, for instance, we have:

pre:   B A
post:  A B

which is either of the two possibilities we cannot distinguish between (A connected as left or right subtree). So, arbitrarily choosing to connect A to the left:

C
                                 B
                              A

The right subtree is this:

pre:   E D F H
post:  D H F E

E is clearly the top node, so remove it, realign the lists, add it to the tree:

pre:   D F H
post:  D H F
                                    C
                                 B     E
                              A

Obviously they divide here:

pre:   D   F H
post:  D   H F

And that essentially solves it (as much as we can; H is arbitrarily connected to the left of F).

C
                                B       E
                              A      D     F
                                          H

A case not covered in your example is the following.

pre:  B A C
post: A C B

B must be the top node. Removing it gives:

pre:  A C
post: A C

It seems these two orders disagree about which is the top node. Actually they are both right. The tree is:

B
     A     C

[nucleon]

Upon re-reading the above, I notice that finding the splitting point for the left and right subtrees (after discarding the root of the current subtree) is as easy as looking for the preorder list's first element in the postorder list's elements. The index of that element (in the postorder list) is the splitting point. If it is not the last element, then it and everything before it is on the left and everything past it is on the right. But if it is the last element, then you don't actually know whether this is a left or right branch. Again, you may as well attach it to the left, unless there is more information to go on (like the inorder traversal).

[dgkris]

http://myexps.blogspot.com/2009/11/create-tree-from-preorder-traversal.html

This code will help you. Its about creating a tree from the preorder traversal. Hope that solves your problem.

[mrnutty]

I suggest make a binary tree class and make the printing function.
Add a few numbers. And print them out pre,post, and mid. Examine the
output. Try to construct a binary tree from the output. You will then realize the pattern.