• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Another Implementation:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Related Chapters:


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


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave