🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

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

Solution:

Please go through Tree Construction: Inorder - Postorder first, if your time permits. The first solution discussed in this chapter is very similar to that discussed in Tree Construction: Inorder - Postorder.

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

First thing first: why do we need both Inorder and Preorder 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 Preorder traversal for both the binary trees are 5 -> 7.
So just by having Preorder 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 Preorder traversal comes into picture. We know in Preorder traversal the root is always visited at the very beginning. So the first element of the preorder traversal result would be the root.

Now, let's take the below binary tree:

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

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

In Preorder we visit the root, followed by left subtree, followed by processing the right subtree.
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 Preorder and Inorder to reconstruct the binary tree.

Looking at the Preorder Traversal, we know 6 is the root, since 6 is the first element in the preorder traversal result. 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 we know that in Preorder: we first visit the root, then process the whole left subtree of the root, and then process the whole right subtree of the root.
Using all this information we would be able to quickly grab the left and right subtree from Preorder 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 n elements starting from second element (since first element in preorder is the root) in Preorder belong to left subtree of the root and the next m elements (basically the last m elements) belong to the right subtree.

Now that we have gotten both Inorder and Preorder 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

Another Implementation:

Java code:

Login to Access Content

Python 2 code:

Login to Access Content

Related Chapters:

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

Instructor: