Construct tree from in-order and pre-order traversal

Companies:
  • Amazon Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions

Problem Statement

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

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

Sample Test Case

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

Problem Solution

Preorder traversal starts at the root, goes to the left subtree and then to the right subtree. 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 preorder and inorder arrays, we can be sure that the root of the binary tree would be the same as the first element in the preorder 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 preorder 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 preorder 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. Preorder array start index would simply be the next incremental value to the current preorder 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. Preorder array start index would now be equal to the sum of current preorder 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;

/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node
{
    public:
    int data;
    node* left;
    node* right;
};

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

node* buildTree(int in[], int pre[], int inStrt, int inEnd)
{
    static int preIndex = 0;

    if (inStrt > inEnd)
        return NULL;

    /* Pick current node from Preorder
    traversal using preIndex
    and increment preIndex */
    node* tNode = newNode(pre[preIndex++]);

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

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

    /* Using index in Inorder traversal, construct left and
    right subtress */
    tNode->left = buildTree(in, pre, inStrt, inIndex - 1);
    tNode->right = buildTree(in, pre, inIndex + 1, inEnd);

    return tNode;
}

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

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return (Node);
}

/* This funtcion is here just to test buildTree() */
void printInorder(node* node)
{
    if (node == NULL)
        return;

    /* first recur on left child */
    printInorder(node->left);

    /* then print the data of node */
    cout<<node->data<<" ";

    /* now recur on right child */
    printInorder(node->right);
}

/* Driver code */
int main()
{
    int in[] = { 9,3,15,20,7 };
    int pre[] = { 3,9,20,15,7 };
    int len = sizeof(in) / sizeof(in[0]);
    node* root = buildTree(in, pre, 0, len - 1);

    /* Let us test the built tree by
    printing Insorder traversal */
    cout << "Inorder traversal of the constructed tree is \n";
    printInorder(root);
}



 

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