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                      
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++                                 
2.3.
Complexity Analysis                          
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++                               
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Can the Inorder traversal sequence and the Preorder traversal sequence be the same?
4.2.
What are the different Binary Tree Traversal methods?
4.3.
What makes an effective hash function?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Constructing a Binary Tree from two Traversal Sequences

Author Vidhi Singh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Tree is a data structure which holds data in a hierarchical manner. It is also considered as a collection of nodes. Binary Tree can be said as a special kind of Tree that can have the utmost 2 nodes as its children. 

So, in this article we will cover the topic Constructing a Binary Tree from Two Traversal Sequences.

Problem Statement                                      

Given Inorder Traversal and Preorder Traversal of a Binary Tree, construct the Binary Tree. The traversals will be given in the form of the array.

Sample Example                      

Input: Inorder  traversal = {20, 10, 25, 5, 30, 15}, Preorder traversal = {5, 10, 20, 25, 15, 30}

Output: The constructed binary tree is

Alt text: Binary Tree

Explanation: The leftmost element of the Preorder traversal is the root of the binary tree. In the Inorder traversal sequence, the root element divides the sequence into the left and right subtrees. We can follow the previous step again to get the root of the subtrees and their child nodes.

Brute Force Approach

In the Preorder sequence, the first element is the root of the binary tree. 

So, we start our tree from there. Then we find the root element in the Inorder sequence and use it to divide the elements into the left (i.e. all the elements to the left of the root) and right subtrees(i.e. all the elements to the right of the root). For the problem in the example above, it would look like this:

Alt text: Binary Tree

Using recursion, we can apply the previous step to each subtree until we get null children. In the end, we would have the following tree

Alt text: Binary Tree

Algorithm

  1. Initialize a variable that would keep track of the Preorder traversal element that we are considering. This is the Preorder Index, which will be incremented to pick up the next element. We start it from the leftmost element of the sequence, the root of the binary tree.
  2. Add the picked element from the Preorder traversal as a node to the binary tree.
  3. Find the picked element in the Inorder traversal and store its index in the sequence in the Inorder Index.
  4. Recursively call the algorithm for elements before the Inorder Index value. This will create subtrees within the left subtree.
  5. Recursively call the algorithm for elements after the Inorder Index value. This will create subtrees within the right subtree.
  6. Return the constructed binary tree.

Implementation in C++                                 

#include <bits/stdc++.h>
using namespace std;

class node 
{
    public:
    char data;
    node* left;
    node* right;
};

node* newNode(char data) 
{
    node* Node = new node();
    Node->data = data;
    Node->left = Node->right = NULL;
    return(Node);
}

int fun_search(char ar[], int strt, int end, char value) 
{
    int i;
    for (i = strt; i <= end; i++) 
    {
        if (ar[i] == value)
            return i;
    }
}

node* contrBT(char in[], char pre[], int inStrt, int inEnd) 
{
    static int preIndex = 0;
    if (inStrt > inEnd)
        return NULL;


    node* tNode = newNode(pre[preIndex++]);


    if (inStrt == inEnd)
        return tNode;


    int inIndex=fun_search(in, inStrt, inEnd, tNode->data);


    tNode->left = contrBT(in, pre, inStrt, inIndex - 1);
    tNode->right = contrBT(in, pre, inIndex + 1, inEnd);
 
    return tNode;
}

void disInorder(node* node) 
{
    if(node == NULL)
        return;
    disInorder(node->left);
    cout << node->data << " ";
    disInorder(node->right);
}

int main() 
{
    char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
    char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
    int len = sizeof(inorder)/sizeof(inorder[0]);
    node* root = contrBT(inorder, preorder, 0, len - 1);


    cout << "Created binary tree in Inorder Traversal: \n";
    disInorder(root);
}

 

Output:

Created binary tree in Inorder Traversal:
D B E A F C

Complexity Analysis                          

Time Complexity: O(N2)
Explanation: In the worst case, the constructed binary tree would skew leftwards. Then the root element would be the rightmost in the Inorder traversal sequence, and the search function would take the longest time.

Space Complexity: O(N)
Explanation: In this approach, the space needed depends on the size of the arrays initialized.

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 above discussed Brute Force approach can be optimized by using  hashing techniques. We can make the entire process faster by storing the Inorder traversal sequence in a hash table.

You can read about Hashing and Hash Tables in detail from here.

Algorithm

  1. Initialize a variable that would keep track of the Preorder traversal element that we are considering. This is the Preorder Index, which will be incremented to pick up the next element. We start it from the leftmost element of the sequence, the root of the binary tree.
  2. Add the picked element from the Preorder traversal as a node to the binary tree.
  3. Map the values of the Inorder traversal sequence to a hash table using unordered_map.
  4. Find the picked element in the Inorder traversal hash table and store its index in the sequence in the Inorder Index.
  5. Recursively call the algorithm for elements before the Inorder Index value. This will create subtrees within the left subtree.
  6. Recursively call the algorithm for elements after the Inorder Index value. This will create subtrees within the right subtree.
  7. Return the constructed binary tree.

Implementation in C++                               

#include <bits/stdc++.h>
using namespace std;

struct Node 
{
    char data;
    struct Node* left;
    struct Node* right;
};
 
struct Node* newNode(char data) 
{
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return(node);
}

struct Node* contrBT(char in[], char pre[], int inStrt, int inEnd, unordered_map<char, int>&mp) 
{
    static int preIndex = 0;
 
    if (inStrt > inEnd)
        return NULL;


    char curr = pre[preIndex++];
    struct Node* tNode = newNode(curr);


    if (inStrt == inEnd)
        return tNode;


    int inIndex = mp[curr];
    tNode->left = contrBT(in, pre, inStrt, inIndex - 1, mp);
    tNode->right = contrBT(in, pre, inIndex + 1, inEnd, mp);
 
    return tNode;
}

struct Node* contrBTWrap(char in[], char pre[], int len) 
{
    unordered_map<char, int> mp;
    for (int i = 0; i < len; i++)
        mp[in[i]] = i;
    return contrBT(in, pre, 0, len - 1, mp);
}

void disInorder(struct Node* node) 
{
    if (node == NULL)
        return;
    disInorder(node->left);
    printf("%c ", node->data);
    disInorder(node->right);
}

int main() 
{
    char in_order[] = {'D', 'B', 'E', 'A', 'F', 'C'};
    char pre_order[] = {'A', 'B', 'D', 'E', 'C', 'F'};
    int len = sizeof(in_order) / sizeof(in_order[0]);
 
    struct Node* root = contrBTWrap(in_order, pre_order, len);


    printf("Created binary tree in Inorder Traversal: \n");
    disInorder(root);
}

 

Output:

Created binary tree in Inorder Traversal:
D B E A F C

Complexity Analysis

Time Complexity: O(N)
Explanation: In this approach, we replace the lengthy search function with the hash key search with time complexity O(1).

Space Complexity: O(N)
Explanation: In this approach, the space needed depends on the size of the arrays initialised.

Frequently Asked Questions

Can the Inorder traversal sequence and the Preorder traversal sequence be the same?

Both the Inorder and Preorder traversal sequences would be the same if the nodes of the binary tree had only right children.

What are the different Binary Tree Traversal methods?

There are primarily three Binary Tree Traversal methods: 

  1. Inorder Traversal 
  2. Preorder Traversal 
  3. Postorder Traversal

What makes an effective hash function?

An effective hash function should have four essential characteristics:

  • The data being hashed completely determines the hash value.
  • The hash function makes use of all of the input data.
  • The hash function distributes the data "uniformly" among all potential hash values.
  • The hash function can generate very dissimilar hash values for very similar strings.

Conclusion

This article extensively discusses the programming problem: Constructing a Binary Tree from Two Traversal Sequences along with their pseudocode, implementation, and time trade-offs.

We hope that this blog has helped you enhance your knowledge regarding Constructing a Binary Tree from Two Traversal Sequences. Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please have a look at these similar problems to learn more: Level Order Traversal, Specific LOTReverse Level Order TraversalDisjoint-set data structure, Boundary Traversal Of Binary Tree.

Recommended problems -

 

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem Design, 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 organized on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the Problems, Interview Experiences, and Interview Bundle for placement preparations.

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

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Previous article
Print Nodes between two given Level Numbers of a Binary Tree
Next article
Construct a special tree from given preorder traversal
Live masterclass