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