DEV Community

Thivyaa Mohan
Thivyaa Mohan

Posted on

Construct a Binary Tree from Inorder and Postorder

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
    }
};

Enter fullscreen mode Exit fullscreen mode

Top comments (0)