Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Example
1.2.1.
Input:
1.2.2.
Output:
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is Hashing?
4.3.
What do you understand by Preorder Traversal?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Creating a Binary Tree From Inorder And LevalOrder Traversal

Author Sarthak
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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        6

Brute 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;
}

 

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.

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

Optimized Approach

The Optimized Approach is quite similar to above one. But We use a Unordered map to store the values and their respective index.It helps to excess index of the nodes very easily and saves time.

Steps of Algorithm

  • First, we will store elements and their index in an unordered map.
  • Now, the first element of Leval order is the root node of the Binary Tree.
  • Now, we will have the index ‘idx’ of the root node by map.
  • Now, We will Create Two Arrays for Left SubTree and Right SubTree.
  • Now, We will Traverse The Leval order List. If the Index of Element is less than ‘idx’, it will become a part of the Left SubTree. Otherwise, it goes to the right Subtree. See, We will have the index in our hand as it is stored in Unordered Map and excessed in O(1).
  • 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 <iostream>
#include <unordered_map>
using namespace std;
struct Node
{
    int key;
    struct Node *left;
    struct Node *right;

    Node(int x)
    {
        key = x;
        left = NULL;
        right = NULL;
    }
};
Node *helperFunction(int inorder[], int levelOrder[], int Starting_Index, int Ending_Index, int n, unordered_map<int, int> mp)
{
    if (Starting_Index > Ending_Index) // If Inorder Starting Index is Greater than Ending Index means It has No Child
    {
        return NULL;
    }

    Node *root = new Node(levelOrder[0]); // Making root Node
    int idx = mp[levelOrder[0]];          // Getting Index of root Node from
    int left_Array[idx - Starting_Index]; // Making Array for Left Subtree
    int right_Array[Ending_Index - idx];  // Making Array for Left Subtree

    int il = 0, ir = 0;
    // If the Index of Element is less than ‘idx’,then it will become a part of Left SubTree Otherwise,goes to right Subtree
    for (int i = 1; i <= Ending_Index - Starting_Index; i++)
    {
        if (mp[levelOrder[i]] < idx)
        {
            left_Array[il++] = levelOrder[i];
        }
        else
        {
            right_Array[ir++] = levelOrder[i];
        }
    }
    // Recusive Call For Creating Left and Right SubTree
    root->left = helperFunction(inorder, left_Array, Starting_Index, idx - 1, n, mp);
    root->right = helperFunction(inorder, right_Array, idx + 1, Ending_Index, n, mp);
    return root;
}
Node *CreateTree(int inorder[], int levelOrder[], int IStart, int IEnd, int n)
{
    // Creating an Unordered Map For Storing Values and Index of Inorder
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
    {
        mp[inorder[i]] = i;
    }

    return helperFunction(inorder, levelOrder, IStart, IEnd, n, mp);
}

void InorderTraversal(Node *node)
{
    if (node == NULL)
        return;
    InorderTraversal(node->left);
    cout << node->key << " ";
    InorderTraversal(node->right);
}
int main(){
// {4 2 5 1 3 6
// 1 2 3 4 5 6
    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 " << endl;
    InorderTraversal(root);
    cout << endl;
    return 0;
}

 

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). 

Space complexity

O(n), used for making the Hashmap.

Frequently Asked Questions

What is a Binary Tree?

A tree is a data structure in which every element have a maximum of 2 children is called a binary tree. These children are called Left child and Right Child.

What is Hashing?

Hashing is a process of mapping keys and values into the hash table by using a hash function. It is used for faster access to elements.

What do you understand by Preorder Traversal?

We can define the Preorder Traversal as, i.e.,  visiting the root, recursively going to the left subtree, and then going to the right subtree and forming the Preorder Traversal.

Conclusion

In this article, we discussed how to Construct a Binary Tree from a given Inorder and Levalorder Traversal. We have discussed the BruteForce Approach as well as the optimized approach of our problem using Hashmap and also saw its time and space complexity. we hope you will learn something from this and will continue learning.

Suggested problems are Construct a Binary Tree From Preorder and PostorderConstruct a Binary Tree From its Linked-List Representation, and many more.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDBMSSystem DesignWeb Development, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. You must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Find Maximum GCD Value from Root to Leaf in a Binary Tree
Next article
Construct the Full K-ary Tree from its Preorder Traversal
Live masterclass