Create a Binary Search Tree from Array

You are given an array representing the preorder traversal of a tree. From this array, construct the original BST.

for.eg. 

              { 60 40 30 28 35 42 70 65 62 68 72 }

 

Approach
Remember the property of a BST - parent is greater than its left and less than its right.
Now 60 is the root of the BST. Search for the possible right child. For this, scan the array from position 2 onwards till you encounter a bigger number than 60. So end up with 70. That is the right node. The left node is 40, the immediate number.
Next take 40 (the left child of root). Find its right child - the number greater than 40 and less than 70. It is 42. And the left child is 30.
Now take 72 (the right child of root). Fin its right child - the number greater than 70. We will find 72. Similarly, left child is 65.
For 30 the right child should be anywhere between numbers 28 and 35. So it is 35. Hence 28 is the left child.
For 42 there is no right child or left child as there are no numbers between 42 and 70.
And so on....

Solution