Construct a Binary Tree from a given Postorder and Inorder traversal
Introduction
Binary Trees has been a favourite topic of many companies, including Amazon, Google, Microsoft, etc. Usually, the problems on Binary Trees look very complicated, but when we look at its solution, it seems very elegant and easy to solve.
Why is that so? This is because the topic binary trees require a stronghold over recursion and some visualization.
To help you solve binary tree problems, we will discuss a common problem, i.e., Construct a Binary Tree from a given Postorder and Inorder traversal. This problem has been asked in many interviews and tests your thought process about approaching binary tree problems.
Let’s look at the problem first.
We are given 2 sequences of size N, i.e., the number of nodes in the binary tree. The first sequence is the postorder traversal of the binary tree and the second sequence is the inorder traversal of the binary tree. Your task is to construct a binary tree out of the given traversals. Return the reference or the pointer to the root of the binary tree.
Postorder Sequence : 4 5 2 6 3 1
Inorder Sequence : 4 2 5 1 6 3
Output Binary Tree:
Return the pointer or reference to the root containing the value 1.
Approach
Let’s understand how we got to the output binary tree before jumping to the approach.
Postorder Sequence : 4 5 2 6 3 1
Inorder Sequence : 4 2 5 1 6 3
Now, we know that a postorder sequence can be recursively defined as:
{Elements of left subtree, Elements of right subtree, Root}
and, an inorder sequence can be recursively defined as:
{Elements of left subtree, Root, Elements of right subtree}
So using the above postorder definition, we can find the root first, the last element in the sequence. Hence root is 1.
If 1 is the root of the binary tree, then using the inorder definition, elements to the left will be present in the left subtree, and elements to the right will be present in the right subtree with root as 1, respectively.
So we can understand the above explanation using the following illustration:
Now, if we try to use the postorder and inorder recursive definitions and apply on the left and right subtrees in the above illustration, we can understand the following process using the illustration below:
So we have reached the condition that each subtree now has at most a single element. Hence we can replace the subtrees as nodes with values of each subtree.
I hope you got the essence of the question from the above example. If not, then no worries, we will discuss the approach here.
If you look, how we Construct a Binary Tree from a given postorder and Inorder traversal, you will get a sense of how the binary tree is constructed using the traversal sequences given to us.
If one tries to observe, the first thing we have done is finding the root first. After finding the root, we can now split the traversals into 3 parts, the left subtree, the root, and the right subtree, respectively.
We recursively follow the same procedure, i.e., finding root nodes of respective subtrees, splitting into 3 parts further, and repeating the same process.
Now when should we terminate? We terminate when we are left with 0 or, at most, a single element in each subtree.
We have understood how we identify repetitive work, asking recursion to do the same for us and finally returning the reference to the root.
So approach can be formulated as:
 Find the root node using the postorder traversal.
 Find the left subtrees and the right subtrees using inorder traversal by finding the index of the root node of respective subtrees.
 Once the root node is found, we can recurse down on the right and left subtrees, i.e., right subarray and left subarray split at respective root index to repeat the same process until we find at most a single element in either subarray.
PseudoCode
#Assume there is a function findIndex(inOrder, val) that computes sum of i*arr[i].
Algorithm
___________________________________________________________________
procedure constructBinaryTree(inOrder, postOrder, startIndex, endIndex,postIndex):
___________________________________________________________________
1. if startIndex > endIndex or postIndex < 0 do # base case
2. return NIL
3. end if
4. rootIndex ← findIndex(inOrder, postOrder[postIndex]) #find subtree root
5. root ← new Node(inOrder[rootIndex]) # create the root Node
6. root.right ←constructBinaryTree(inOrder, postorder, rootIndex+1, endIndex, postIndex) # recursively create the right subtree
7. root.left ←constructBinaryTree(inOrder, postorder, startIndex, rootIndex1, postIndex) # recursively create the left subtree
8. return root # root
9. end procedure
___________________________________________________________________
Explanation of the PseudoCode
The first condition handles the terminating conditions of the recursive functions, i.e., if we don’t have any element in the subtree.
Then, we found the root index using the postorder for finding the value of the next root of the subtree. We maintain the postIndex pointer to keep track of the element we are currently at and decrement it to find the root of the subsequent subtrees.
Now similarly, we do the same for creating the right subtree.
NOTE: The startIndex and the endIndex are maintained to split the inorder array, and we can get to know elements in the subarray that will be present in the left subtree and the right subtree, respectively. The postIndex is decremented because nodes of subtrees occur at the end.
IMPORTANT OBSERVATION
We also have a similar question in which we are given the preorder traversal sequence instead of the postOrder traversal. Note we used to recurse by creating the left subtree and then the right subtree. See Here.
So how is this different from the question in which we have the preorder traversal?
The basic difference lies in the definition of the two traversals. The root for each subtree comes at the lefthand side of the preorder traversal sequence and the righthand side of the postorder traversal sequence. So while constructing the binary tree, we must take care that we build the right subtree first and then the left subtree when we are constructing the binary tree using the postorder sequence and vice versa in the case of preorder traversal sequence.
CODE IN C++
//C++ program to create the binary tree from the inOrder and postOrder traversals #include <bits/stdc++.h> using namespace std;
// struct Node to create Nodes in the Binary tree struct Node { int data; // value of the node Node *left; // left child Node *right; // right child Node(int d) { this>data = d; this>left = nullptr; this>right = nullptr; } };
// function that finds the index of the given value in the inOrderTraversal int findIndex(int inOrder[], int val, int size) { int index = 1; for (int i = 0; i < size; ++i) { if (inOrder[i] == val) return index = i; // return index if the element matches the given value } return index; }
// function to constructBinaryTree from inOrder and postOrder Traversals Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int *postIndex, int size) { if (startIndex > endIndex or (*postIndex) < 0) // base case return nullptr;
int rootIndex = findIndex(inOrder, postOrder[*postIndex], size); // subtree root Index Node *root = new Node(inOrder[rootIndex]); // create the subtree root Node *postIndex = *postIndex  1; // decrement the postIndex pointer maintained
// construct right subtree root>right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex, size); // construct left subtree root>left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex  1, postIndex, size); // return the root of the subtree. return root; }
// function implementing the inOrderTraversal void inOrderTraversal(Node *root) { if (root == nullptr) return; // return if there is node inOrderTraversal(root>left); // recursively go to left subtree cout << root>data << " "; // print the root Node of each subtree inOrderTraversal(root>right); // recursively go to right subtree }
int main() { int size = 6; // size of the array int inOrder[] = {4, 2, 5, 1, 6, 3}; // inOrderTraversal sequence int postOrder[] = {4, 5, 2, 6, 3, 1}; // postOrderTraversal sequence int postIndex = size  1; // pre order traversal index to keep track of subtree root nodes
//root Node of constructed binary tree Node *root = constructBinaryTree(inOrder, postOrder, 0, size  1, &postIndex, size);
//check if the inorder traversal matches with the given traversal
cout << "The inOrderTraversal of the binary tree is: "; inOrderTraversal(root); return 0; }

Output
The inOrderTraversal of the binary tree is: 4 2 5 1 6 3 
Time Complexity: O(n^{2}) because we traverse the inOrder array again in each iteration for creating the root node of a subtree, which takes O(n) time. For n nodes will take O(n^{2}) to create the whole binary tree using the above algorithm.
Space complexity: O(n), as we are recursively building up the binary tree.
Finding indices in the whole inOrder array is the main culprit for our time consumption. So can we come up with some efficient approach that does the same work in less time? Let's discuss how we can optimize the solution for the problem.
Approach to a Timeefficient Solution
If we can find the indices in O(1) time, then we can surely improve the efficiency of the algorithm from O(n^{2}) to O(n).
So what can we use when we talk about accessing elements O(1) time. We can think of arrays or some precomputation or maps that store the elements and give O(1) access time.
We see that arrays take O(n) time, and it is not working out here. If we think about precomputation and storing results in maps, it seems to be a good idea. So if we hash the indices using the element values, we can access them in O(1) time.
Hence, we must modify the findIndex function in the abovegiven algorithm and store the element’s indices in a map.
CODE IN C++(Time Optimized)
//C++ program to create the binary tree from the inOrder and postOrder traversals #include <bits/stdc++.h> using namespace std;
// struct Node to create Nodes in the Binary tree struct Node { int data; // value of the node Node *left; // left child Node *right; // right child Node(int d) { this>data = d; this>left = nullptr; this>right = nullptr; } };
// map to store the indices of elements unordered_map<int, int> mp;
// function that finds the index of the given value in the inOrderTraversal int findIndex(int val) { return mp[val]; // return the index of the given data }
// function to constructBinaryTree from inOrder and postOrder Traversals Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int *postIndex, int size) { if (startIndex > endIndex or (*postIndex) < 0) // base case return nullptr; int rootIndex = findIndex(postOrder[*postIndex]); // subtree root Index Node *root = new Node(inOrder[rootIndex]); // create the subtree root Node *postIndex = *postIndex  1; // decrement the postIndex pointer maintained
// construct right subtree root>right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex, size); // construct left subtree root>left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex  1, postIndex, size); // return the root of the subtree. return root; }
// function implementing the inOrderTraversal void inOrderTraversal(Node *root) { if (root == nullptr) return; // return if there is node
inOrderTraversal(root>left); // recursively go to left subtree cout << root>data << " "; // print the root Node of each subtree inOrderTraversal(root>right); // recursively go to right subtree }
int main() { int size = 6; // size of the array int inOrder[] = {4, 2, 5, 1, 6, 3}; // inOrderTraversal sequence int postOrder[] = {4, 5, 2, 6, 3, 1}; // postOrderTraversal sequence int postIndex = size  1; // pre order traversal index to keep track of subtree root nodes
for (int i = 0; i < size; ++i) //store the indices of elements in the map mp[inOrder[i]] = i;
//root Node of constructed binary tree Node *root = constructBinaryTree(inOrder, postOrder, 0, size  1, &postIndex, size);
//check if the inorder traversal matches with the given traversal
cout << "The inOrderTraversal of the binary tree is: "; inOrderTraversal(root); return 0; } 
Output
The inOrderTraversal of the binary tree is: 4 2 5 1 6 3 
Time Complexity: O(n) on average because we build the binary tree by finding the index value now in O(1) time on average. The only time taken is to build the tree recursively. Hence the time complexity is O(n).
Space complexity: O(n), as a recursive stack, builds the whole binary tree and the space consumed in maintaining a map.
Frequently Asked Questions
How can we find the left view of a binary tree?
Answer) If you followed this blog, you would get to know how we can traverse a binary tree. If we want to find the left view of a binary tree, we will go to the left whenever possible, but when no node is present, the only possibility will be that the right node is visible. Hence using this approach, we can solve this problem.
What is the worstcase Time complexity if we want to search in a binary tree?
Answer) So the worst case in a binary tree would be when it is skewed, and in that case, we have the worstcase time complexity, i.e. O(n), where n is the number of nodes in the binary tree.
How can we find the level order traversal?
Answer) The level order traversal is a basic algorithm used extensively in various tree problems, which uses a queue and adds the nodes present at each level. In the case of a binary tree, we will add the children of all the nodes present in the queue and visit the nodes present in it. Also, pop the nodes once visited.
Key Takeaways
This article taught us how to Construct a Binary Tree from a given postorder and Inorder traversal by approaching the problem using a brute force approach to the most optimal approach finally. We discussed their implementation using a recursive method using illustrations, pseudocode, and then proper code.
We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most binary tree problems, which simplifies the results to a greater extent.
Now, we recommend you practice problem sets based on binary trees to master your fundamentals. You can get a wide range of questions similar to the problem Construct a Binary Tree from a given postorder and Inorder traversal on CodeStudio.
Comments
No comments yet
Be the first to share what you think