Construct a Binary Tree from a given Preorder and Inorder Traversal
Introduction
Binary Trees have been a favorite topic of many companies, including Amazon, Google, Microsoft, etc. Usually, the problems on Binary Trees look very complicated, but it is easy to solve when we look at its solution.
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 Preorder 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 pre-order traversal of the binary tree, and the second sequence is the in-order traversal of the binary tree. Your task is constructing a Binary Tree from a given Preorder and Inorder traversal. Return the reference or the pointer to the root of the binary tree.
Input
Pre-order Traversal: 1 2 4 5 3 6
In-order Traversal: 4 2 5 1 6 3
Output
Return the pointer or reference to the root containing the value 1.
Approach
Before jumping to the approach, let’s understand how we got to the output binary tree.
Pre-order Sequence: 1 2 4 5 3 6
In-order Sequence: 4 2 5 1 6 3
Now, we know that a pre-order sequence can be recursively defined as
Root --> Left Subtree --> Right Subtree
and an in-order sequence can be recursively defined as
Left Subtree--> Root --> Right Subtree
So using the above pre-order definition, we can find the root first, the first element in the sequence. Hence root is 1.
If 1 is the root of the binary tree, using the in-order 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 the root as 1, respectively.
So we can understand the above explanation using the following illustration:
Suppose we use the pre-order and in-order recursive definitions and apply them to the left and right subtrees in the illustration above. In that case, we can understand the following process using the illustration given 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 at how we Construct a Binary Tree from a given Preorder and Inorder traversal, you will understand how the binary tree is constructed using the traversal sequences given to us.
If one tries to observe, the first thing we do is find the root first. After finding the root, we can now split the traversals into 3 parts: the left, root, and right, 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 returning the reference to the root.
Algorithm
So algorithm can be formulated as
- Find the root node using the pre-order 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 left and right subtrees, i.e., left subarray, and right 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: 1 2 4 5 3 6
In-order Traversal: 4 2 5 1 6 3
Step-1
First, we will create the tree's root, and initially, the preIndex would be at the first element of the pre-order array.
Step-2
In the second step, we will first create the left subtree, and our preIndex will be increment, which will now point to 2. Therefore, 2 will be the root of the left subtree.
Step-3
In the third step, the left child of the left subtree of root node 2 will be created; here, it will be 4. The preIndex will now point to 4.
Step-4
In this step, we will create the right child of the left subtree, and preIndex will be incremented to point to 5.
Step-5
Now, again, we will repeat the above steps. Since we have created the left subtree, we will now create the right subtree. preIndex will be incremented, and now it will point to 3 so a new node with value 3 will be created.
Step-6
In the last, we will create the left subtree of node 3, which only contains one node, i.e., 6; preindex will point to the last element of the Pre-order array.
Now our binary tree has been completely formed.
Implementation in C++
// C++ program to create the binary tree from the inOrder and preOrder 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 = 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)
{
// return index if the element matches the given value
if (inOrder[i] == val)
return index = i;
}
return index;
}
// function to constructBinaryTree from inOrder and preOrder Traversals
Node *constructBinaryTree(int inOrder[], int preOrder[], int startIndex, int endIndex, int &preIndex, int size)
{
// base case
if (startIndex > endIndex or preIndex >= size)
return nullptr;
// subtree root Index
int rootIndex = findIndex(inOrder, preOrder[preIndex], size);
// create the subtree root Node
Node *root = new Node(preOrder[preIndex]);
// increment the preIndex variable
preIndex = preIndex + 1;
// construct left subtree
root->left = constructBinaryTree(inOrder, preOrder, startIndex, rootIndex - 1, preIndex, size);
// construct right subtree
root->right = constructBinaryTree(inOrder, preOrder, rootIndex + 1, endIndex, preIndex, 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};
// preOrderTraversal sequence
int preOrder[] = {1, 2, 4, 5, 3, 6};
// pre order traversal index to keep track of subtree root nodes
int preIndex = 0;
// root Node of constructed binary tree
Node *root = constructBinaryTree(inOrder, preOrder, 0, n - 1, preIndex, 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 inOrderTraversal of the binary tree is: 4 2 5 1 6 3 Complexity Analysis
Time Complexity
O(n2)Note that the above algorithm takes O(n2) time complexity 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(n2) 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.
Also See, Binary Tree Postorder Traversal.
Also check out - Inorder Predecessor
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(n2) to O(n). What can we use when discussing 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
There would be a slight change in the previous algorithm:
- Find the root node using the pre-order traversal.
- Find the left and right subtrees using in-order traversal by finding the root node index of respective subtrees. Here root node index will be found using unordered_map.
- Once the root node is found, we can recurse down on the left and right subtrees, i.e., left subarray, and right 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 preOrder 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 = 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 preOrder Traversals
Node *constructBinaryTree(int inOrder[], int preOrder[], int startIndex, int endIndex, int &preIndex, int size)
{
// base case
if (startIndex > endIndex or preIndex >= size)
return nullptr;
// subtree root Index
int rootIndex = findIndex(preOrder[preIndex]);
// create the subtree root Node
Node *root = new Node(preOrder[preIndex]);
// increment the preIndex variable
preIndex = preIndex + 1;
// construct left subtree
root->left = constructBinaryTree(inOrder, preOrder, startIndex, rootIndex - 1, preIndex, size);
// construct right subtree
root->right = constructBinaryTree(inOrder, preOrder, rootIndex + 1, endIndex, preIndex, 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};
// preOrderTraversal sequence
int preOrder[] = {1, 2, 4, 5, 3, 6};
// pre order traversal index to keep track of subtree root nodes
int preIndex = 0;
// to store the indices of the elements in a map
for (int i = 0; i < n; i++)
mp[inOrder[i]] = i;
// root Node of constructed binary tree
Node *root = constructBinaryTree(inOrder, preOrder, 0, n - 1, preIndex, 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 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 the recursive stack, builds the whole binary tree and the space consumed in maintaining a map.
Frequently Asked Questions
How can we find the inorder traversal?
We can follow the recursive definition of the inorder traversal, i.e., recursively go to the left subtree, visit the root, and then go to the right subtree.
How can we find the preorder traversal?
We can follow the recursive definition of the preorder traversal, i.e., visit the root, recursively go to the left subtree, and then go to the right subtree.
How can we find the postorder traversal?
We can follow the recursive definition of the postorder traversal, i.e., recursively go to the left subtree, go to the right subtree, and then visit the root.
What is the significance of inorder traversal?
Inorder traversal is useful for binary search trees as it results in visiting the nodes in ascending order. It is also used to print the contents of a binary tree in a sorted manner.
Can we use an iterative approach for inorder traversal?
Yes, the iterative approach can also be used for inorder binary tree traversal. The iterative approach uses a stack to traverse the tree similar to the recursive approach.
Conclusion
This article taught us how to Construct a Binary Tree from a given Preorder 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 can 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. You can get a wide range of questions similar to the problem. Construct a Binary Tree from a given Preorder and Inorder traversal on CodeStudio.
Refer to our guided paths on Codestudio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations, and feel free to post any suggestions in the comments section.
Happy Learning!!
Previous Article 
