Construct a binary tree from preorder and postorder traversals

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

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

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

Algorithm

We know that the first element of a preorder traversal and last element of a post order traversal gives us the root element of the tree. Using this, we can derive the algorithm as follows.

  1. Create a root node with value equal to the first element of the preorder traversal. Find the index of the 2nd element of the preorder traversal in the postorder traversal. This element is the starting element of the left subtree. Store it in a variable L.
  2. We create 4 different arrays from the given postorder and preorder traversals as follows.
    a) leftPost = {post.begin() …… post.begin() + L}. In the given example, this array becomes {8, 9, 4, 5, 2}.
    b) leftPre = {pre.begin()+1 ……. pre.begin() + L + 1}. In the given example, this array becomes {2, 4, 8, 9, 5}.
    c) rightPost = {post.begin() + L …… post.begin() + N}, where N is the size of the preorder array. In the given example, this array becomes {6, 7, 3, 1}.
    d) rightPre = {pre.begin()+L+1 ……. pre.end()}. In the given example, this array becomes {3, 6, 7}.
  3. We then recur to create left and right subtrees using the modified preorder and postorder traversals computed above.
  4. To create left subtree, we recur using leftPre and leftPost arrays. To create right subtree, we recur using rightPre and rightPost arrays.

For better understanding, look at the code below.

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

void inorder(Node* root){
    if(root == nullptr){
        return;
    }
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

Node* constructFromPrePost(vector<int>& pre, vector<int>& post) {
    if(pre.size()==0){
        return nullptr;
    }
    Node* curr_root = createNode(pre[0]);
    if(pre.size()==1){
        return curr_root;
    }
    int L=0;
    for(int i=0; i<post.size();i++){
        if(post[i]==pre[1]){
            L = i+1;
        }
    }
    int N = pre.size();
    vector<int> leftPost(post.begin(), post.begin()+L);
    vector<int> leftPre(pre.begin()+1, pre.begin()+L+1);
    vector<int> rightPost(post.begin()+L, post.begin()+N);
    vector<int> rightPre(pre.begin()+L+1, pre.end());
    curr_root->left = constructFromPrePost(leftPre, leftPost);
    curr_root->right = constructFromPrePost(rightPre, rightPost);
    return curr_root;
}

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

Also, take a look at another popular interview problem Construct a binary tree using inorder and preorder traversals.

One comment

Leave a Reply

Your email address will not be published.