🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Given inorder and postorder traversal of a binary tree, construct the binary tree.

Solution:

I am assuming that you have strong understanding of recursion and how recursion works.

First thing first: why do we need both Inorder and Postorder traversal to reconstruct a Binary Tree ? The below two binary trees would clarify that:

 5                 5
  \               /
   7             7

The inorder traversal for the above two binary trees are 5 -> 7 and 7 -> 5 respectively.
However, the Postorder traversal for both the binary trees are 7 -> 5.
So just by having Postorder traversal won't help in reconstructing the tree correctly.

Why can't we just have inorder traversal ? Because we do not know what the value of the root is. This is where Postorder traversal comes into picture. We know in Postorder traversal the root is always visited at the end.

Now, let's take the below binary tree:

     6
   /   \
  1     7
 / \    / \
2   3  5   4

Postorder: {2, 3, 1, 5, 4, 7, 6}
Inorder: {2, 1, 3, 6, 5, 7, 4}

In Postorder we process the left subtree, followed by right subtree, followed by the root.
In Inorder we process left subtree, followed by root, followed by right subtree.

Now let's see how we can use the combined power of Postorder and Inorder to reconstruct the binary tree.

Looking at the Postorder Traversal, we know 6 is the root. Now looking at the Inorder Traversal we can say that

• all the nodes on the left of 6 in inorder traversal i.e. {2, 1, 3}, would constitute left subtree of root 6.
• all the nodes on the right of 6 in inorder traversal i.e. {5, 7, 4}, would constitute right subtree of root 6.

Now since we know that in Postorder: we first process the whole left subtree of the root, and then process the whole right subtree of the root before visiting the root.
Using this information we would quickly grab the left and right subtree from Postorder traversal result as well. We will be using the size of the subtrees to achieve this goal, where size of subtree = number of nodes in the subtree. If from inorder traversal result we get that there are n nodes in left subtree and m nodes in right subtree, then we would know that the first n elements in Postorder belong to left subtree of the root and the next m elements belong to the right subtree.

Now that we have gotten both Inorder and Postorder for both left subtree and right subtree, we could run the above described approach on them to recursively construct the left and right subtree. The below code beautifully implements this idea.

Java code:

Login to Access Content

Python 2 code:

Login to Access Content

Related Chapters:

1. Tree Construction: Inorder - Preorder
2. Tree Construction: Inorder - Level Order

Instructor: