Constructing a binary tree with given traversals

Question Detail: 

I have given a post order & in order traversal a BST & I need to construct it. I want to know how to do this.

for eg.

Post Order : DCBGFEA

In Order : BDCAFGE

This is how I am trying to do :

• From POST order it is clear that A is root. So in IN order, I consider everything right to A is at it's right sub tree & so for left.

  

• Now, I consider A's left sub tree. It has BDC. Again from POST order, I conclude that B is root.

  

• Now, again consider B's sub tree. It has contents DC & POST order, C has to be at root. So now I get C at root. But where to place C, at B's left or right ? It's where I am getting stuck now.

Same happening with A's right sub tree also. I place E as root of A's right sub tree. Then I conclude element below should be F, but does it come at right or left of E ?

I want to know how to tackle this problem & also is there any better approach for this to do.

Asked By : avi

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11015

Answered By : Hendrik Jan

You are doing well. From the postorder determine the root, from the inorder determine which letters are in the left and right subtrees. Once you have done that, you can proceed in the same way for the subtrees.

In the example you start with postorder DCBGFE A and inorder BDC A FGE.

Using postorder you determine the root as A, and using inorder split the letters into left BDC and FGE. Thus (1) the left subtree has postorder DCB and inorder BDC while (2) the right subtree has postorder GFE and inorder FGE.

Let us look at left subtree (1) which you mention in your question. The root is B, and both DC follow to B in the inorder and thus are right from B. How to place them. This tiny subtree has postorder DC and inorder DC. Hence its root is C, and D is before C in the inorder, and is in the left subtree of C.