Objective:– Given a inorder and postorder traversal, write an algorithm to construct a binary tree from that. This problem was asked in the Microsoft coding competition.

Last element in the postorder [] will be the root of the tree, here it is 1.

Now the search element 1 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).

Suppose in previous step, there are X number of elements which are left of ‘i’ (which will construct the leftsubtree), take first X elements from the postorder[] traversal, this will be the post order traversal for elements which are left to i. similarly if there are Y number of elements which are right of ‘i’ (which will construct the rightsubtree), take next Y elements, after X elements from the postorder[] traversal, this will be the post order traversal for elements which are right to i

From previous two steps construct the left and right subtree and link it to root.left and root.right respectively.

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________