Untitled

/************************************************************
   
   Following is the TreeNode class structure
   
   class TreeNode<T>
   { 
   public:
        T data; 
        TreeNode<T> *left;
        TreeNode<T> *right;
   
        TreeNode(T data) 
  		{ 
            this -> data = data; 
            left = NULL; 
            right = NULL; 
        }
   };
   
   
 ************************************************************/

 int findpos(int element,vector<int>&inOrder,int n){
     for(int i=0;i<n;i++) {
          if(inOrder[i]==element) return i;
     }
     return -1;
 }


TreeNode<int>* solve(vector<int>& postOrder,vector<int>&inOrder,int &i,int s,int e,int n){
     if(i<0 || s>e) return NULL;

     int element=postOrder[i--];
     int pos=findpos(element,inOrder,n);

     TreeNode<int>* node =new TreeNode<int>(element);

     node->right= solve(postOrder,inOrder,i,pos+1,e,n);  //why this order matters?
     node->left = solve(postOrder,inOrder,i,s,pos-1,n);
     return node;

}


TreeNode<int>* getTreeFromPostorderAndInorder(vector<int>& postOrder, vector<int>& inOrder){
     int n=postOrder.size();
	int postindex=n-1;
     return solve(postOrder,inOrder,postindex,0,n-1,n);
}