Construct a Binary Tree from a given Postorder and Inorder Traversal

Approach

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

Post-order Traversal: 4 5 2 6 3 1

In-order Traversal:   4 2 5 1 6 3

Now, we know that a post-order sequence can be recursively defined as:

Left Subtree--> Right Subtree--> Root

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

Left Subtree --> Root --> Right Subtree

So using the above postorder definition, we can find the root first and the last element in the sequence. If one tries to observe, the first thing we will do is find the root. After finding the root, we can split the inorder traversals into 3 parts:

• the left subtree
• the root
• the right subtree
   

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

1. Find the root node using the postorder 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 right and left subtrees, i.e., right subarray and left 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: 4 5 2 6 3 1

In-order Traversal:   4 2 5 1 6 3

Step-1 

In the first step, we will create the tree's root, and initially, the index will be at the last of the post-order array. 

Step-2

In the second step, we will first create the right subtree, and our postIndex will be decremented, and point to 3, and 3 will be the root of the right subtree.

Step-3

In the third step, the left and right child of the right subtree will be created since there is no right child, so we will create only a left child, postIndex will be decremented here. It will point to 6, so a node will a value of 6 will be created.

Step-4

Since we have created the right subtree, it is time to create the left subtree of the root node. So we will create the root node of the left subtree, i.e., 2, so here, the postIndex will decrease and point to 2.

Step-5

Now, again we will repeat the above steps. We will create the right subtree first, and after that, we will create the left subtree (In the left subtree of the root node). So the right subtree consists of only a single node, so only 5 will be created, and postIndex will be decremented.

Step-6

In the last step, we will create the left subtree, consisting of only a single node. In this step, postIndex will be decremented, now pointing to the first element.

Now our binary tree has been completely formed

Implementation in C++

// C++ program to create the binary tree from the inOrder and postOrder 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 = NULL;
        this->right = NULL;
    }
};

// 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 postOrder Traversals
Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int &postIndex, int size)
{
    // base case
    if (startIndex > endIndex || postIndex < 0)
        return NULL;

    // subtree root Index
    int rootIndex = findIndex(inOrder, postOrder[postIndex], size);

    // create a tree with this root Node
    Node *root = new Node(postOrder[postIndex]);

    // decrement the postIndex pointer maintained
    postIndex = postIndex - 1;

    // construct right subtree
    root->right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex, size);

    // construct left subtree
    root->left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex - 1, postIndex, 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};

    // postOrderTraversal sequence
    int postOrder[] = {4, 5, 2, 6, 3, 1};

    // post order traversal index to keep track of subtree root nodes
    int postIndex = n - 1;

    // root Node of constructed binary tree
    Node *root = constructBinaryTree(inOrder, postOrder, 0, n - 1, postIndex, n);

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

You can also try this code with Online C++ Compiler

Run Code

Output

The inOrder Traversal of the binary tree  is: 4 2 5 1 6 3 

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity

O(n²) because we traverse the inOrder array again in each iteration to create a subtree's root node, 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 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.

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

1. Find the root node using the postorder traversal.
2. Find the left and right subtrees using in-order traversal by finding the root node index of respective subtrees. The root node index will be found using unodered_map.
3. Once the root node is found, we can recurse down on the right and left subtrees, i.e., right subarray and left 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 postOrder 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 = NULL;
        this->right = NULL;
    }
};

// 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 the index of the given data
    return mp[val];
}

// function to constructBinaryTree from inOrder and postOrder Traversals
Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int &postIndex)
{
    // base case
    if (startIndex > endIndex || postIndex < 0)
        return NULL;

    // subtree root Index
    int rootIndex = mp[postOrder[postIndex]];

    // create a tree with this root Node
    Node *root = new Node(postOrder[postIndex]);

    // decrement the postIndex pointer maintained
    postIndex = postIndex - 1;

    // construct right subtree
    root->right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex);

    // construct left subtree
    root->left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex - 1, postIndex);

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

    // postOrderTraversal sequence
    int postOrder[] = {4, 5, 2, 6, 3, 1};

    // post order traversal index to keep track of subtree root nodes
    int postIndex = n - 1;

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

    // root Node of constructed binary tree
    Node *root = constructBinaryTree(inOrder, postOrder, 0, n - 1, postIndex);

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

You can also try this code with Online C++ Compiler

Run Code

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

Must Read Recursive Binary Search.

Frequently Asked Questions

How can we find the left view of a binary tree?

If you followed this blog, you would get to know how we can traverse a binary tree. If we want to find the left view of a binary tree, we will go to the left whenever possible, but when no node is present, the only possibility will be that the right node is visible. Hence using this approach, we can solve this problem.

What is the worst-case Time complexity if we want to search in a binary tree?

So the worst case in a binary tree would be when it is skewed, and in that case, we have the worst-case time complexity, i.e., O(n), where n is the number of nodes in the binary tree.

How can we find the level order traversal?

The level order traversal is a basic algorithm used extensively in various tree problems, which uses a queue and adds the nodes present at each level. In the case of a binary tree, we will add the children of all the nodes in the queue and visit the nodes in it. Also, pop the nodes once visited. 

Can inorder traversal be used to reconstruct a binary tree?

Yes, inorder traversal along with either preorder or postorder traversal, can be used to reconstruct a binary tree.

Is inorder traversal unique for a given binary tree?

No, inorder traversal is not unique for a given binary tree. Two different binary trees can have the same inorder traversal sequence.

Conclusion

This article taught us how to Construct a Binary Tree from a given postorder 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 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, simplifying the results to a greater extent.

We recommend you practice problem sets based on binary trees to master your fundamentals. 

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal