/************************************************************
Following is the TreeNode class structure
template <typename T>
class TreeNode {
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T data) {
this->data = data;
left = NULL;
right = NULL;
}
};
************************************************************/
// preorder index
int findpos(vector<int>&inorder,int element,int n){
for(int i=0;i<n;i++){
if(inorder[i]==element) return i;
}
return -1;
}
TreeNode<int>* solve(int &i,vector<int> &inorder,vector<int> &preorder, int s,int e, int n){
if(i>=n || s>e) return NULL;
int element =preorder[i++];
TreeNode<int>* node=new TreeNode<int>(element);
int pos=findpos(inorder,element,n);
node->left = solve(i,inorder,preorder,s,pos-1,n);
node->right = solve(i,inorder,preorder,pos+1,e,n);
return node;
}
TreeNode<int> *buildBinaryTree(vector<int> &inorder, vector<int> &preorder)
{
// Write your code here //INORDER LNR....... PREORDER NLR
int n=inorder.size();
int pin=0;
TreeNode<int> *ans =solve(pin,inorder,preorder,0,n-1,n); //starting and ending index of inorder
return ans;
}