I have given a post order & in order traversal a BST & I need to construct it. I want to know how to do this.
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.