Construct a binary tree from inorder and preorder traversals.

You are given inorder and preorder traversals, you need to construct the binary tree.

Input:
Inorder = {4, 2, 5, 1, 3, 6}
Preorder = {1, 2, 4, 5, 3, 6}

Output:
         1
      /    \    
     2       3
   /   \      \
  4     5      6

Algorithm:

We know that, the first index of a preorder traversal contains the root node of the corresponding tree. Taking this into advantage, we derive the following algorithm. The problem is similar to Construct a binary tree using postorder and inorder traversal.

  1. We create a root node with value equal to the first element in the preorder traversal. This also becomes the root node of our tree.
  2. We then find the index of that element in the given inorder traversal. The left part of the index gives us the left subtree and the right part of the index gives us right subtree. In the given example, the root’s value is 1.
  3. We then recur the same process with updated arrays as :
    a) Recur for inorder = {4, 2, 5} and preorder = {2, 4, 5}. The returned tree becomes the left subtree.
    b) Recur for inorder = {3, 6} and preorder = {3, 6}. The returned tree becomes the right subtree.

Check out the code for better understanding.

#include <bits/stdc++.h>
using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(Node* root){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}


Node* helper(int preStart, int inStart, int inEnd, vector<int>& preorder, vector<int>& inorder){
    if(preStart >= preorder.size() || inStart > inEnd){
        return nullptr;
    }
    Node* curr_root = createNode(preorder[preStart]);
    int inIndex = 0;
    for(int i=inStart; i<=inEnd; i++){
        if(inorder[i]==preorder[preStart]){
            inIndex=i;
        }
    }
    curr_root->left = helper(preStart+1, inStart, inIndex-1, preorder, inorder);
    curr_root->right = helper(preStart + inIndex-inStart+1, inIndex+1, inEnd, preorder, inorder);
    return curr_root;
}

Node* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return helper(0,0,inorder.size()-1, preorder, inorder);
}

int main()
{
    vector<int> inorder = {4, 2, 5, 1, 3, 6};
    vector<int> preorder = {1, 2, 4, 5, 3, 6}; 
    root = buildTree(preorder, inorder);
    levelOrderTraversal(root);
    return 0;
}

Also, check out another popular interview problem Construct a binary tree using inorder and postorder traversal.

One comment

Leave a Reply

Your email address will not be published.