Construct a BST from preorder traversal

You are given a preorder traversal, you need to construct a binary search tree.

Input: {10, 5, 1, 7, 40, 50} is the preorder traversal.
Output:
     10
   /   \
  5     40
 /  \      \
1    7      50

Algorithm

We know that the first element of a preorder traversal if the root of the tree. Leveraging this knowledge, we can derive the following algorithm.

  1. Create a root node with value equal to the first element of the preorder traversal. We initialize a variable right_index = -1. We set the variable right_index with the index value of the first element in the preorder array which is greater than the starting element or the root element.
  2. If the value of right_index is not equal to -1, it means that the root node has both left and right subtree. We recur for left subtree with modified preorder array from (start + 1) to (right_index – 1). And we recur for right subtree with modified preorder array from (right_index) to end.
  3. If right_index = -1, it means that the root has only left subtree. Hence, we set right pointer of root to NULL and recur for left subtree with modified preorder array from (start + 1) to end.
  4. If start > end, we return NULL.

Look at the code below 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;

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

Node* traverse(vector<int> & preorder, int start, int end){
    if(start <=end){
        Node* curr_root = createNode(preorder[start]);
        int rIndex = -1;
        for (int i = start+1;i<=end;i++){
            if(preorder[i] > curr_root->data){
                rIndex = i;
                break;
            }
        }
        if(rIndex!=-1){
            curr_root->left = traverse(preorder, start+1, rIndex-1);
            curr_root->right = traverse(preorder, rIndex, end);
        }
        else{
            curr_root->left = traverse(preorder, start+1, end);
            curr_root->right = nullptr;
        }
        return curr_root;
    }
    return nullptr;
}


Node* bstFromPreorder(vector<int>& preorder) {
    return traverse(preorder, 0, preorder.size()-1);
}

int main()
{
    vector<int> preorder = {10, 5, 1, 7, 40, 50};
    root = bstFromPreorder(preorder);
    inorder(root);
    return 0;
}

Also, take a look at another popular interview problem Left View of a Binary Tree.

One comment

Leave a Reply

Your email address will not be published.