Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.4.
Complexity Analysis
4.
Approach to a Time-efficient Solution
4.1.
Algorithm
4.2.
Implementation in C++ (Time Optimized)
4.3.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
How can we find the inorder traversal?
5.2.
How can we find the preorder traversal?
5.3.
How can we find the postorder traversal?
5.4.
What is the significance of inorder traversal?
5.5.
Can we use an iterative approach for inorder traversal?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Construct a Binary Tree from a given Preorder and Inorder Traversal

Author Aniket verma
1 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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. 

Intro Image

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. 

Binary tree Intro Image

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

Binary tree Image

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

Before jumping to the approach, let’s understand how we got to the output binary tree.

Pre-order Sequence1 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.

Image of binary tree

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

  1. Find the root node using the pre-order traversal.
  2. Find the left and right subtrees using in-order traversal by finding the root node index of respective subtrees.
  3. 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-1 image

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-2 image

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-3 image

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-4 image

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-5 image

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. 

Step-6 image

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:

  1. Find the root node using the pre-order traversal.
  2. 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.
  3. 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 Coding Ninjas Studio.

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio 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
Conversion from a Binary Tree to a Threaded Binary Tree
Next article
The Binary Lifting Technique
Live masterclass