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.

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

*Related*

## One comment