Given inorder and postorder traversals of a Binary Tree in the arrays in[] and post[] respectively. The task is to construct the binary tree from these traversals.

Given inorder and postorder traversals of a Binary Tree in the arrays in[] and post[] respectively. The task is to construct the binary tree from these traversals.

Here is a simple and easy approach with using the hash map and recursion.

 

/* Tree node structure
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;

    Node(int x){
        data = x;
        left = right = NULL;
    }
};*/

// Function should construct tree and return
// root of it.  in[] stores inorder traversal
// post[] stores postorder traversal.  n is
// size of these arrays
// int inde;

Node * Tbuild(int post[], int l, int h, unordered_map < int, int > & mp, int & inde) {

    if (l > h) return NULL;

    Node * root = new Node(post[inde--]);

    if (l == h) return root;

    int i = mp[root - > data];

    root - > right = Tbuild(post, i + 1, h, mp, inde);
    root - > left = Tbuild(post, l, i - 1, mp, inde);
    return root;
}

Node * buildTree(int in [], int post[], int n) {
    // Your code here
    int inde = n - 1;
    unordered_map < int, int > mp;
    for (int i = 0; i < n; ++i)
        mp[ in [i]] = i;

    return Tbuild(post, 0, n - 1, mp, inde);

}