Construct binary tree from inorder and postorder traversal

Companies:
  • Amazon Interview Questions
  • Microsoft Interview Questions

Problem Statement

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Sample Test Case

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
  3
   / \
  9  20
    /  \
   15   7

Problem Solution

Postorder traversal starts at the left subtree then right subtree and then goes to the root. Inorder traversal starts at the left subtree, then goes through the root and then the right subtree.

So in order to construct a binary tree from postorder and inorder arrays, we can be sure that the root of the binary tree would be the same as the last element in the postorder array.

In order to construct the left subtree of this root, the next intuitive step is to locate this root node within the inorder array. Then in that case, all the node values to the left of that root node’s value would form it’s left subtree, while all the node values to the right of that root node’s value would form it’s right subtree.

Since solution to a larger problem (the entire tree) requires us to solve an incrementally smaller problem (the entire tree sans the previous level), recursion makes best intuitive sense to apply. With recursion, the foremost interest is to identify base conditions 

Base conditions in this problem: ensure that start index of both the postorder and inorder arrays do not exceed the last index of the respective arrays; return null in either case.

With the base conditions in place, next the motive is to find the inIndex within the inorder array whose node value is equal to the root node’s value that corresponds to the current iterating index of the postorder array.

Once the inorder array index is found, recursive calls to construct the left subtree of this root node shall involve passing the (start, end) indexes of the inorder array as (inStart, inIndex — 1), in addition to the two arrays in question. Postorder array start index would simply be the next decremental value to the current postorder index.

Recursive calls to construct the right subtree of this root node shall involve passing the (start, end) indexes of the inorder array as (inIndex+1, inEnd), in addition to the two arrays in question. Postorder array start index would now be equal to the difference of current postorder index and the length of the left subtree, to account for the by now constructed left subtree.

At reach recursion, the root of the tree constructed is returned back to the calling function.

Complexity Analysis

Time Complexity: In order to construct the entire tree, we end up visiting each node in both the arrays, so the time complexity is O(n).

Space Complexity: due to the stack space incurred due to recursion would amount to O(n).

Code Implementation

#include <bits/stdc++.h>

using namespace std;


class Node {
public:
    int data;
    Node *left, *right;
};

// Utility function to create a new node
Node* newNode(int data);

/* Prototypes for utility functions */
int search(int arr[], int strt, int end, int value);


Node* buildUtil(int in[], int post[], int inStrt,
                int inEnd, int* pIndex)
{
    // Base case
    if (inStrt > inEnd)
        return NULL;

    /* Pick current node from Postorder traversal using
    postIndex and decrement postIndex */
    Node* node = newNode(post[*pIndex]);
    (*pIndex)--;

    /* If this node has no children then return */
    if (inStrt == inEnd)
        return node;

    /* Else find the index of this node in Inorder
    traversal */
    int iIndex = search(in, inStrt, inEnd, node->data);

    /* Using index in Inorder traversal, construct left and
    right subtress */
    node->right = buildUtil(in, post, iIndex + 1, inEnd, pIndex);
    node->left = buildUtil(in, post, inStrt, iIndex - 1, pIndex);

    return node;
}

// This function mainly initializes index of root
// and calls buildUtil()
Node* buildTree(int in[], int post[], int n)
{
    int pIndex = n - 1;
    return buildUtil(in, post, 0, n - 1, &pIndex);
}

/* Function to find index of value in arr[start...end]
The function assumes that value is postsent in in[] */
int search(int arr[], int strt, int end, int value)
{
    int i;
    for (i = strt; i <= end; i++) {
        if (arr[i] == value)
            break;
    }
    return i;
}

/* Helper function that allocates a new node */
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

/* This funtcion is here just to test */
void preOrder(Node* node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

// Driver code
int main()
{
    int in[] = {9,3,15,20,7};
    int post[] = { 9,15,7,20,3};
    int n = sizeof(in) / sizeof(in[0]);

    Node* root = buildTree(in, post, n);

    cout << "Preorder of the constructed tree : \n";
    preOrder(root);

    return 0;
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]