Introduction
Binary Tree is one of the favorite topics of Interviews. Out of these, Tree Traversals are the important one. In this Blog, We will learn how to make a Binary Tree From Inorder Traversals and Leval order Traversals.
Problem Statement
You have given Inorder Traversals and Leval order Traversals of a Tree. Your Task is to Construct a Binary Tree from Inorder and Leval order Traversals.
Sample Example
Input:
int Inorder[] = {4, 2, 5, 1, 3, 6};
int LevelOrder[] = {1, 2, 3, 4, 5, 6};
Output:
Explanation:
The first element in level order traversal is the root of the tree. So we know ’1’ is the root for given tree.
Now search for ’1’ in Inorder sequence, we find that all elements on the left side of ‘1’ are in the left subtree, and elements on right are in the right subtree. so, we made a partial tree like this.
1
/ \
/ \
{4,2,5} {3,6}
Now we have two parts left subtree{4,2,5} and {3,6} as the right subtree. Note that, in these subarrays, the Inorder traversal does not change, But level order changes. therefore we have to find the level order of subarrays formed.
Let ‘LoFLs’ and ‘LoFRs’ be two arrays for level order for left subtree and level order for right subtree.
We will start traversing the level order traversal from index 1 and seen that If an element was found before ‘idx’, then store it in l else store it in Array2.
Leftsubtree Rightsubtree
In[] = {4,2 5}; In[] = {3,6};
level[] = {2,4,5}; level[] = {3,6};
1
/ \
In {4,2,5} In{3,6}
Lo{2,4,5} Lo{3,6}
Following the same procedure, we create our entire tree.
1
/ \
2 3
/ \ \
4 5 6Brute Force Approach
- The Approach is very simple, as You know about Inorder Traversals and Leval order Traversals. The first element in the Leval order Traversal is the root node of the tree. Now, we search our root node in the Inorder Traversal. Let the index of the root node is ‘idx’. Now, Logically we have divided Inorder traversal into three parts. The root node has index ‘idx’ and all the elements that come before the root node are part of the Left Subtree, and all the elements that come after the root node in Inorder Traversals are part of the Right-Subtree.
- In the same way, we will recursively create the left and right subtree and Hence form our Tree. But, this will require Leval order Traversal for the left and right subtree(Formed above).
- Create two new Arrays ‘Array1’ and ‘Array2’ for creating level order traversal of the left subtree and right subtree.
- Now, We will start traversing the level order traversal from index 1 and place the elements in two Arrays formed. If an element was found before ‘idx’, then store it in Array1 else store it in Array2. Hence, Array1 becomes the level order traversal of left subtree and Array2 becomes the level order traversal of the right subtree. So, let's see how the code works.
- Again, we follow the same procedure for the left and right subtree.
Steps of Algorithm
- First, the first element of Leval order is the root node of the Binary Tree.
- We call the function to find the Index of The Root Element in the inorder traversal, i.e., ‘idx’.
- Here, We have divided our Inorder Traversal Into three parts.
- Now, For further creation of Tree, we should have Levelorder of LeftSubtree and RightSubtree with us.
- For, Left Subtree, we will call a function having Leval order and Inorder and ‘idx. Now, the Element of Leval order(Base Tree), which comes before index ‘idx’ will become part of Leval order for LeftSubTree.
- For the Right Subtree, we will call a function having Leval order and Inorder and ‘idx. Now, the Element of LevalOrder(Base Tree), which comes after index ‘idx’ will become part of Leval order for LeftSubTree.Therefore, we pass the part of Inorder, which comes after the index.
- Now, We Recursively Call for Left SubTree with the Leval order and Inorder of Left Subtree and Ending Index Will ‘idx’-1.
- Now, We Recursively Call for Right SubTree with the Leval order and Inorder of Right Subtree and Ending Index Will ‘idx’+1.
- Return Root.
Implementation in C++
// Program to create a Binary Tree from InOrder and LevalOrder
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
// Finding Index Of Root Element in InOrder Traversals
int Search_Index_Of_Element(int Inorder[], int Starting_Index, int Ending_Index, int value)
{
for (int index = Starting_Index; index <= Ending_Index; index++)
if (Inorder[index] == value)
return index;
return -1;
}
// This Actually Finds LevalOrder Of The SubTrees
int *Find_Element_Of_SubTree(int Inorder[], int leval[], int End_Index, int n)
{
int *NewArray = new int[End_Index];
int j = 0;
for (int i = 0; i < n; i++)
{
int value = leval[i];
for (int index = 0; index <= End_Index - 1; index++)
{
if (Inorder[index] == value)
{
NewArray[j] = leval[i];
j++;
}
}
}
return NewArray;
}
// Creation of New Node
Node *newNode(int key)
{
Node *node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
// Creating Binary Tree From InOrder And LevalOrder Traversals
Node *CreateTree(int InOrder[], int LevelOrder[], int IStarting_Index, int IEnding_Index, int n)
{
// If starting index is more than the ending index,It has No Children
if (IStarting_Index > IEnding_Index)
return NULL;
// First Node in the Levalorder is the root node
Node *root = newNode(LevelOrder[0]);
// Means This is the Leaf Node
if (IStarting_Index == IEnding_Index)
return root;
// Finding Index of Element in the Root Element in the Inorder Traversal
int RIndex = Search_Index_Of_Element(InOrder, IStarting_Index, IEnding_Index, root->key);
// Creating an Array for Finding the LevalOrder Of Left SubTree
int *LOLeftSubtree = Find_Element_Of_SubTree(InOrder, LevelOrder, RIndex, n);
// Creating an Array for Finding the LevalOrder Of Right SubTree.See,We have passed only Inorder Array After Root Node
int *LORightSubtree = Find_Element_Of_SubTree(InOrder + RIndex + 1, LevelOrder, n - 1, n);
// Recusive Function For Creating Left SubTree
root->left = CreateTree(InOrder, LOLeftSubtree, IStarting_Index, RIndex - 1,
RIndex - IStarting_Index);
// Recusive Function For Creating Right SubTree
root->right = CreateTree(InOrder, LORightSubtree, RIndex + 1, IEnding_Index,
IEnding_Index - RIndex);
delete[] LOLeftSubtree; // Deleting Left Leval Order Array
delete[] LORightSubtree; // Deleting Right Leval Order Array
return root;
}
// Printing The Element Of The Tree(InOrder Traversal)
void printInorder(Node *node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->key << " ";
printInorder(node->right);
}
int main()
{
int Inorder[] = {4, 2, 5, 1, 3, 6};
int LevelOrder[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(Inorder) / sizeof(Inorder[0]);
Node *root = NULL;
root = CreateTree(Inorder, LevelOrder, 0, n - 1, n);
cout << "Inorder traversal of the constructed tree is "
"\n";
printInorder(root);
return 0;
}
You can also try this code with Online C++ Compiler
Output:
Inorder traversal of the constructed tree is
4 2 5 1 3 6
Complexity Analysis
Time complexity
O(n³), where n is the number of nodes in a tree. Algorithms run for n Nodes and Creating SubTree for Main Tree takes O(n²). Hence, the Upper bound for time complexity is O(n³).
Space complexity
O(n).As recursive Stack takes O(n) time.
85+ registered