Construct Binary Tree from Postorder & Inorder traversal

This is solution of LeetCode question

Postorder Traversal : Left → Right → Root

Inorder Traversal : Left → Root → Right

From the question we can see that Post order and Inorder Traversal of the given tree is :

postorder = [9,15,7,20,3]

inorder = [9, 3, 15, 20, 7]

So our first step will be to find out the root. We cannot find root using Inorder Traversal because it will be sandwich between left and right. From postorder traversal we found Root = 3.

Now we all know that in inorder traversal we go from Left → Root → Right. Therefore by looking at inorder vector we can say that since Root = 3 therefore

Left Node Elements = 9

Right Node Elements = 15, 20, 7

Now Inorder to find out rest of the arrangement we will traverse postorder from right side because as already discussed we can find root only from postorder traversal.

For Left Node Elements : So ignoring 3 because its already a root element we will move forward. 20, 7, and 15 are Right Node Elements. So our only option left is 9 which will be root of left node.

For Right Node Elements : So ignoring 3 because its already a root element we will move forward. Now out of right node elements 20 is coming first so it will be our right root element.

Now since 20 is right root element from inorder we can easily see that 7 is to its right and 9,3,15 towards its left.

After placing 7 towards right of 20 we are left with 9, 3, 15. Out of these 3 is root element and 9 is left node element. Hence we are left with 15 which we will place in left of 20 and our binary tree will be formed.

Now Inorder to understand this more clearly we will take pictorial example. Suppose Postorder = 2, 4, 3, 6, 5 and Inorder = 2, 3, 4, 5, 6

Now coming to the Approach :

1. We will pass inorder and postorder vector in function with indexes. Starting & Ending index of inorder & postorder traversal.
2. Determine root from postorder vector.
3. Now search this root node in inorder vector.
4. Now calculate how far it is from the beginning of inorder vector.
5. Next step is to recursively call left & right node. Left index will start from starting index & end at the index of root and right index will start after root index and end at the last.

Solution of above mentioned approach.

Video ref. Jenny’s lecture, Knowledge Center