Construct Binary Tree from preorder and inorder | Data Structure

Introduction:

In this tutorial we are going to see how we can construct the binary tree from given preorder and inorder.

Prerequisites: you should know about binary tree traversal and on paper you can draw binary tree from given preorder and inorder traversal.

Inorder:left->root->right;

Preorder:root->left->right;

Problem Statement:

we have given two arrays. one for preorder and another for inorder. by using these two array we have to built a binary tree.

eg:

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

solution:
 
Solution:
We will follow recursive approach to solve this question.let's discuss how we can 
solve it.

Trick: In the given preorder the very first element will be the root of the tree.
then we will find root element in inorder  also. and we know in inorder
traversal we have left part then root and then right part of the tree. by using 
preorder we can get the root of the main tree and by using inorder and root we can
get the left part and right part of the tree.

So basically everytime we will get the root from preorder array and left and right part of the
 root  from inorder array.

As now we have left part and right part of tree, we will do same thing on left part.
and then on right part.

Basically what i want to say is, in first iteration we will get the root of the tree
as well as left and right part of the tree. in second iteration we will get the root
of left part of the tree as well as left and right part of the left part of the main
tree and so on. and same thing we will follow with the right part of the main tree.

Full Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTreeHelper(vector<int>preorder,vector<int>inorder,int inS,int inE,int preS,int preE){
        if(inS > inE){
            return NULL;
        }
        int rootdata=preorder[preS];
        int rootindex=-1;
        for(int i=inS;i<=inE;i++){
            if(inorder[i]==rootdata){
                rootindex=i;
                break;
            } 
        }
        int lIns=inS;
        int lIne=rootindex-1;
        int lPres=preS+1;
        int lPree=lIne-lIns+lPres;
        int rIns=rootindex+1;
        int rIne=inE;
        int rPres=lPree+1;
        int rPree=preE;
        
        TreeNode *root= new TreeNode(rootdata);
        root->left=buildTreeHelper(preorder,inorder,lIns,lIne,lPres,lPree);
        root->right=buildTreeHelper(preorder,inorder,rIns,rIne,rPres,rPree);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int m=preorder.size();
        int n=inorder.size();
        return buildTreeHelper(preorder,inorder,0,n-1,0,m-1);
    }
};

Conclusion: 
We are maintaining eight variables which will keep track of both array. and in each
recursive call we are basically updating these eight variables. first we are building
left part of the tree then right part of the tree.

This problem is from leetcode and this is a very popular interview problem.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/