When we are given a root,left and right subtree :
Inorder : Left Root Right
Preorder : Root Left Right
We can get the root from the Preorder traversal, and the first element from the Preorder traversal is Root.If we locate the root, we can find the left and right side of the tree easily. We can follow the similar fashion and construct the whole tree.
Here is the code of the solution
class Solution{
public:
int order=0;
Node* build(int in[],int pre[],int s,int e){
if(s>e){
return NULL;
}
Node* root=new Node(pre[order++]);
int index=0;
for(int i=s;i<=e;i++){
if(in[i]==root->data){
index=i;
break;
}
}
root->left=build(in,pre,s,index-1);
root->right=build(in,pre,index+1,e);
return root;
}
Node* buildTree(int in[],int pre[], int n)
{
return build(in,pre,0,n-1);
// Code here
}
};
Top comments (0)