Binary Trees has been a favourite topic for 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.

Problem Statement

We are given 2 sequences of size N, i.e., the number of nodes in the binary tree. The first sequence is the post-order traversal of the binary tree, and the second sequence is the in-order 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.

Sample Example

Input

Post-order Traversal: 4 5 2 6 3 1

In-order Traversal: 4 2 5 1 6 3

Output

Binary Tree:

Return the pointer or reference to the root containing the value 1.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach

Letâ€™s understand how we got to the output binary tree.

Post-order Traversal: 4 5 2 6 3 1

In-order Traversal: 4 2 5 1 6 3

Now, we know that a post-order sequence can be recursively defined as:

Left Subtree--> Right Subtree--> Root

and an in-order sequence can be recursively defined as:

Left Subtree --> Root --> Right Subtree

So using the above postorder definition, we can find the root first and the last element in the sequence. If one tries to observe, the first thing we will do is find the root. After finding the root, we can split the inorder traversals into 3 parts:

the left subtree

the root

the right subtree

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 returning the reference to the root.

Algorithm

Find the root node using the postorder traversal.

Find the left and right subtrees using in-order traversal by finding the root node index 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 sub-array.

Dry Run

Post-order Traversal: 4 5 2 6 3 1

In-order Traversal: 4 2 5 1 6 3

Step-1

In the first step, we will create the tree's root, and initially, the index will be at the last of the post-order array.

Step-2

In the second step, we will first create the right subtree, and our postIndex will be decremented, and point to 3, and 3 will be the root of the right subtree.

Step-3

In the third step, the left and right child of the right subtree will be created since there is no right child, so we will create only a left child, postIndex will be decremented here. It will point to 6, so a node will a value of 6 will be created.

Step-4

Since we have created the right subtree, it is time to create the left subtree of the root node. So we will create the root node of the left subtree, i.e., 2, so here, the postIndex will decrease and point to 2.

Step-5

Now, again we will repeat the above steps. We will create the right subtree first, and after that, we will create the left subtree (In the left subtree of the root node). So the right subtree consists of only a single node, so only 5 will be created, and postIndex will be decremented.

Step-6

In the last step, we will create the left subtree, consisting of only a single node. In this step, postIndex will be decremented, now pointing to the first element.

Now our binary tree has been completely formed

Implementation 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
{
// value of the node
int data;
// left child
Node *left;
// right child
Node *right;
Node(int d)
{
this->data = d;
this->left = NULL;
this->right = NULL;
}
};
// 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)
{
// return index if the element matches the given value
if (inOrder[i] == val)
return index = i;
}
return index;
}
// function to constructBinaryTree from inOrder and postOrder Traversals
Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int &postIndex, int size)
{
// base case
if (startIndex > endIndex || postIndex < 0)
return NULL;
// subtree root Index
int rootIndex = findIndex(inOrder, postOrder[postIndex], size);
// create a tree with this root Node
Node *root = new Node(postOrder[postIndex]);
// decrement the postIndex pointer maintained
postIndex = postIndex - 1;
// 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)
{
// return if there is node
if (root == nullptr)
return;
// recursively go to left subtree
inOrderTraversal(root->left);
// print the root Node of each subtree
cout << root->data << " ";
// recursively go to right subtree
inOrderTraversal(root->right);
}
int main()
{
// size of the array
int n = 6;
// inOrderTraversal sequence
int inOrder[] = {4, 2, 5, 1, 6, 3};
// postOrderTraversal sequence
int postOrder[] = {4, 5, 2, 6, 3, 1};
// post order traversal index to keep track of subtree root nodes
int postIndex = n - 1;
// root Node of constructed binary tree
Node *root = constructBinaryTree(inOrder, postOrder, 0, n - 1, postIndex, n);
// check if the inorder traversal matches with the given traversal
cout << "The inOrderTraversal of the binary tree is: ";
inOrderTraversal(root);
return 0;
}

Output

The inOrder Traversal of the binary tree is: 4 2 5 1 6 3

Complexity Analysis

Time Complexity

O(n^{2}) because we traverse the inOrder array again in each iteration to create a subtree's root node, 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 recursively build up the binary tree.

Finding indices in the whole inOrder array is the main culprit for our time consumption. So can we develop an 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 Time-efficient 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, precomputations, or maps that store the elements and give O(1) access time.

Arrays take O(n) time, which is not working out here. It seems to be a good idea if we think about precomputation and storing results in maps. 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 above-given algorithm and store the elementâ€™s indices in a map.

Algorithm

Find the root node using the postorder traversal.

Find the left and right subtrees using in-order traversal by finding the root node index of respective subtrees. The root node index will be found using unodered_map.

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 sub-array.

Implementation 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
{
// value of the node
int data;
// left child
Node *left;
// right child
Node *right;
Node(int d)
{
this->data = d;
this->left = NULL;
this->right = NULL;
}
};
// 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 the index of the given data
return mp[val];
}
// function to constructBinaryTree from inOrder and postOrder Traversals
Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int &postIndex)
{
// base case
if (startIndex > endIndex || postIndex < 0)
return NULL;
// subtree root Index
int rootIndex = mp[postOrder[postIndex]];
// create a tree with this root Node
Node *root = new Node(postOrder[postIndex]);
// decrement the postIndex pointer maintained
postIndex = postIndex - 1;
// construct right subtree
root->right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex);
// construct left subtree
root->left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex - 1, postIndex);
// return the root of the subtree.
return root;
}
// function implementing the inOrderTraversal
void inOrderTraversal(Node *root)
{
// return if there is node
if (root == nullptr)
return;
// recursively go to left subtree
inOrderTraversal(root->left);
// print the root Node of each subtree
cout << root->data << " ";
// recursively go to right subtree
inOrderTraversal(root->right);
}
int main()
{
// size of the array
int n = 6;
// inOrderTraversal sequence
int inOrder[] = {4, 2, 5, 1, 6, 3};
// postOrderTraversal sequence
int postOrder[] = {4, 5, 2, 6, 3, 1};
// post order traversal index to keep track of subtree root nodes
int postIndex = n - 1;
for (int i = 0; i < n; ++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, n - 1, postIndex);
// 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

Complexity Analysis

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.

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 worst-case Time complexity if we want to search in a binary tree?

So the worst case in a binary tree would be when it is skewed, and in that case, we have the worst-case 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?

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 in the queue and visit the nodes in it. Also, pop the nodes once visited.

Can inorder traversal be used to reconstruct a binary tree?

Yes, inorder traversal along with either preorder or postorder traversal, can be used to reconstruct a binary tree.

Is inorder traversal unique for a given binary tree?

No, inorder traversal is not unique for a given binary tree. Two different binary trees can have the same inorder traversal sequence.

Conclusion

This article taught us how to Construct a Binary Tree from a given postorder and Inorder traversal by finally approaching the problem using a brute force approach to the most optimal approach. We discussed their implementation using a recursive method using illustrations, pseudocode, and 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, simplifying the results to a greater extent.

We recommend you practice problem sets based on binary trees to master your fundamentals.