Binary Trees: Construct Binary Tree from preorder and inorder traversal

Problem Statement:

You are given 2 arrays with inorder and pre-order.

You need to construct a binary tree with the given array.

Example

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Solution

We know that in pre-order traversal starts from root, goes to the left sub tree and then to right sub tree.

Inorder traversal will start from left sub tree, then goes through root and then right sub tree.

So from the pre-order[0] will give us the root of the binary tree.

Then we need to construct left and right sub tree of that root node. For that we need to locate the root within the inorder array.

Then in that case, all the node values to the left of that root will form a left sub tree, then all the nodes to the right will be right sub tree.

Like this we recursively call to construct the right sub tree and left sub tree.

Example:

Let us construct a binary tree for the given array below:

Pre-Order [50, 30, 10, 40, 70, 60, 90]

In-Order [10, 30, 40, 50, 60, 70, 90]

We know that 50 is the root node from pre order traversal array.

Now find 50 in in-order and divide the tree into left and right sub tree.

Resultant tree will be as below:

           50
          /  \
 10, 30, 40  60, 70, 90

Now take the left sub tree “10, 30, 40”. The pre-order traversal will be “30, 10, 40”.

It means, “30” will be the root, hence divide the tree into left and right sub tree.

        30
       /  \
      10  40

Similarly for “60, 70, 90”, pre-order traversal will be “70, 60, 90”. “70” will be root node.

        70
       /  \
      60  90

Final tree will be:

            50
          /   \
         30    70
        /  \  /  \
       10  40 60 90 

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;

struct node 
{ 
      int data; 
      node *left; 
      node *right; 

    node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
}; 

node* build(vector<int>& preorder, vector<int>& inorder, int& rootIdx, int left, int right) 
{
  if (left > right) return NULL;
  int pivot = left;  // find the root from inorder
  while(inorder[pivot] != preorder[rootIdx]) pivot++;
  
  rootIdx++;
  node* newNode = new node(inorder[pivot]);
  newNode->left = build(preorder, inorder, rootIdx, left, pivot-1);
  newNode->right = build(preorder, inorder, rootIdx, pivot+1, right);
  return newNode;
}

node* buildTree(vector<int>& preorder, vector<int>& inorder) 
{
  int rootIdx = 0;
  return build(preorder, inorder, rootIdx, 0, inorder.size()-1);
}



void printInorder(struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main()
{
   vector<int> preorder = {50, 30, 10, 40, 70, 60, 90};
   vector<int> inorder = {10, 30, 40, 50, 60, 70, 90};
  
   node* root = buildTree(preorder, inorder);

    cout << "Inorder traversal of the constructed tree is \n";
    printInorder(root);

}

Output:

Inorder traversal of the constructed tree is
10 30 40 50 60 70 90