Construct Binary Tree from Inorder and Preorder Traversal

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
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 7The 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