Construct a binary tree from inorder and postorder traversals

You are given inorder and postorder traversals, you need to construct the binary tree.

Input : 
Inorder = {4, 8, 2, 5, 1, 6, 3, 7}
Postorder = {8, 4, 5, 2, 6, 7, 3, 1} 

Output : 
          1
       /     \
     2        3
   /    \   /   \
  4     5   6    7
    \
      8

Algorithm

We know that, the last index of a postorder traversal contains the root node of the corresponding tree. Taking this into advantage, we derive the following algorithm.

  1. We create a root node with value equal to the last element in the postorder traversal. This also becomes the root node of our tree.
  2. We then find the index of that element in the given inorder traversal. The left part of the index gives us the left subtree and the right part of the index gives us right subtree. In the given example, the root’s value is 1.
  3. We then recur the same process with updated arrays as :
    a) Recur for inorder = {4, 8, 2, 5} and postorder = {8, 4, 5, 2}. The returned tree becomes the left subtree.
    b) Recur for inorder = {6, 3, 7} and postorder = {6, 7, 3}. The returned tree becomes the right subtree.

Check out the code for better understanding.

#include <bits/stdc++.h>
using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(Node* root){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}


Node* helper(int postEnd, int inStart, int inEnd, vector<int> &inorder, vector<int> &postorder){
    if(postEnd < 0 || inStart>inEnd){
        return nullptr;
    }
    Node* curr_root = createNode(postorder[postEnd]);
    int inIndex=0;
    for(int i=inStart; i<=inEnd; i++){
        if(curr_root->data == inorder[i]){
            inIndex=i;
        }
    }
    curr_root->left = helper(postEnd-inEnd+inIndex-1, inStart, inIndex-1, inorder, postorder);
    curr_root->right = helper(postEnd-1, inIndex+1, inEnd, inorder, postorder);
    return curr_root;
}

Node* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return helper(postorder.size()-1, 0, inorder.size()-1, inorder, postorder);
}

int main()
{
    vector<int> inorder = {4, 8, 2, 5, 1, 6, 3, 7};
    vector<int> postorder = {8, 4, 5, 2, 6, 7, 3, 1}; 
    root = buildTree(inorder, postorder);
    levelOrderTraversal(root);
    return 0;
}

Also, take a look at another popular interview problem Path sum equal to k in trees.

One comment

Leave a Reply

Your email address will not be published.