Construct Binary Tree from Inorder and Postorder Traversal

Algorithms and Data Structures: TheAlgorist.com

System Design: DistributedComputing.dev

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
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 7The 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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python 2 code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Related Chapters:
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.