Construct a Binary Tree from a given Preorder and Inorder traversal

Introduction

Binary Trees has been a favorite topic of many companies, including Amazon, Google, Microsoft, etc. Usually, the problems on Binary Trees look very complicated, but it seems pretty 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.

 

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 to construct a Binary Tree from a given Preorder and Inorder traversal. Return the reference or the pointer to the root of the binary tree.

Pre-order Sequence : 1 2 4 5 3 6

In-order Sequence :   4 2 5 1 6 3

Output Binary Tree:

Return the pointer or reference to the root containing the value 1.

Approach

Let’s understand how we got to the output binary tree before jumping to the approach.

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, Elements of left subtree, Elements of right subtree}

and, an in-order sequence can be recursively defined as:

{Elements of left subtree, Root, Elements of 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, then 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 root as 1, respectively.

So we can understand the above explanation using the following illustration:

Now, suppose we use the pre-order and in-order recursive definitions and apply them on 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 subtre

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, how we Construct a Binary Tree from a given Preorder and Inorder traversal, you will get a sense of how the binary tree is constructed using the traversal sequences given to us.

If one tries to observe, the first thing we have done is finding the root first. After finding the root, we can now split the traversals into 3 parts, the left subtree, the root, and the right subtree, 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 finally returning the reference to the root.

So approach can be formulated as:

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

PseudoCode

#Assume there is a function findIndex(inOrder, val) that computes sum of i*arr[i].

Algorithm

___________________________________________________________________

procedure constructBinaryTree(inOrder, preOrder, startIndex, endIndex, preIndex):

___________________________________________________________________

1.     if startIndex > endIndex or preIndex > inOrder.size do # base case 1

2.          return NIL

3.     end if

4.     rootIndex ← findIndex(inOrder, preOrder[preIndex++]) #find subtree root 

5.     root ← new Node(inOrder[rootIndex])      # create the root Node

6.     root.left ←constructBinaryTree(inOrder, preOrder, startIndex, rootIndex-1,   preIndex) # recursively create the left subtree

7.    root.right ←constructBinaryTree(inOrder, preOrder, rootIndex+1, endIndex,  preIndex) # recursively create the right subtree

8.   return root # root

9. end procedure

___________________________________________________________________

Explanation of the PseudoCode

The first condition handles the terminating conditions of the recursive functions, i.e., if we don’t have any element in the subtree.

Then, we found the root index using the pre-order for finding the value of the next root of the subtree. We maintain the preIndex pointer to keep track of the element we are currently at and increment it to find the root of the subsequent subtrees.

Now similarly, we do the same for creating the right subtree.

NOTE: The startIndex and the endIndex are maintained to split the inorder array, and we can get to know elements in the sub-array that will be present in the left subtree and the right subtree, respectively.

CODE 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
{
    int data;    // value of the node
    Node *left;  // left child
    Node *right; // right child
    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)
    {
        if (inOrder[i] == val)
            return index = i; // return index if the element matches the given value
    }
    return index;
}


// function to constructBinaryTree from inOrder and preOrder Traversals
Node *constructBinaryTree(int inOrder[], int preOrder[], int startIndex, int endIndex, int *preIndex, int size)
{
    if (startIndex > endIndex or (*preIndex) >= size) // base case
        return nullptr;
    int rootIndex = findIndex(inOrder, preOrder[*preIndex], size); // subtree root Index
    Node *root = new Node(inOrder[rootIndex]);                     // create the subtree root Node
    *preIndex = *preIndex + 1;                                     // increment the preIndex pointer maintained


    // 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)
{
    if (root == nullptr)
        return;                    // return if there is node


    inOrderTraversal(root->left);  // recursively go to left subtree
    cout << root->data << " ";     // print the root Node of each subtree
    inOrderTraversal(root->right); // recursively go to right subtree
}


int main()
{
    int size = 6;                        // size of the array
    int inOrder[] = {4, 2, 5, 1, 6, 3};  // inOrderTraversal sequence
    int preOrder[] = {1, 2, 4, 5, 3, 6}; // preOrderTraversal sequence
    int preIndex = 0;                    // pre order traversal index to keep track of subtree root nodes


    //root Node of constructed binary tree
    Node *root = constructBinaryTree(inOrder, preOrder, 0, size - 1, &preIndex, size);


    //check if the inorder traversal matches with the given traversal


    cout << "The inOrderTraversal of the binary tree  is: ";
    inOrderTraversal(root);
    return 0;
}

Output

Time Complexity: O(n²)

Note that the above algorithm takes O(n²) 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(n²) to create the whole binary tree using the above algorithm.

Space complexity: O(n), as we are recursively building up the binary tree. 

Finding indices in the whole inOrder array is the main culprit for our time consumption. So can we come up with some efficient approach that does the same work in less time?

Let's discuss how we can optimize the solution for the problem.

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(n²) to O(n).

So what can we use when we talk about accessing elements O(1) time. We can think of arrays or some precomputation or maps that store the elements and give O(1) access time.

We see that arrays take O(n) time, and it is not working out here. If we think about precomputation and storing results in maps, it seems to be a good idea. 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.

CODE 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
{
    int data;    // value of the node
    Node *left;  // left child
    Node *right; // right child
    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)
{
    if (startIndex > endIndex or (*preIndex) >= size) // base case
        return nullptr;


    int rootIndex = findIndex(preOrder[*preIndex]); // subtree root Index
    Node *root = new Node(inOrder[rootIndex]);      // create the subtree root Node
    *preIndex = *preIndex + 1;                      // increment the preIndex pointer maintained


    // 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)
{
    if (root == nullptr)
        return; // return if there is node


    inOrderTraversal(root->left);  // recursively go to left subtree
    cout << root->data << " ";     // print the root Node of each subtree
    inOrderTraversal(root->right); // recursively go to right subtree
}


int main()
{
    int size = 6;                        // size of the array
    int inOrder[] = {4, 2, 5, 1, 6, 3};  // inOrderTraversal sequence
    int preOrder[] = {1, 2, 4, 5, 3, 6}; // preOrderTraversal sequence
    int preIndex = 0;                    // pre order traversal index to keep track of subtree root nodes


    for (int i = 0; i < size; ++i) //store the indices of elements in the map
        mp[inOrder[i]] = i;


    //root Node of constructed binary tree
    Node *root = constructBinaryTree(inOrder, preOrder, 0, size - 1, &preIndex, size);


    //check if the inOrderTraversal matches with the given traversal
    cout << "The inOrderTraversal of the binary tree  is: ";
    inOrderTraversal(root);
    return 0;
}

Output

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 a recursive stack, builds the whole binary tree and the space consumed in maintaining a map.

Frequently Asked Questions

1. How can we find the inOrder traversal?
   Answer)  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.
2. How can we find the preOrder traversal?
   Answer) 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.
3. How can we find the postOrder traversal?
   Answer) 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.

Key Takeaways

This article taught us how to Construct a Binary Tree from a given Preorder and Inorder traversal by approaching the problem using a brute force approach to the most optimal approach finally. We discussed their implementation using a recursive method using illustrations, pseudocode, and then proper code.

We hope you could 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, which simplifies the results to a greater extent.

Now, 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.