# Construct Binary Search Tree from a given Preorder Traversal using Recursion

**Objective:** **– **Given a preorder traversal, construct BST from that.

**Input:** Preorder traversal

**Similar Problem** : This problem is similar to the – Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

**Approach: **

Solution to the problem is similar to *isBST Max-Min Solution.*

*“Your root value can have any value between -∞ to + ∞, say it is 30 here, When you validate the right child of 30, it can take any value between 30 and + ∞. When you validate the left child of 30, it can take any value between — ∞ and 30. likewise *

So the idea is *Pass the minimum and maximum values between which the node’s value must lie*.

- Example:
**int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 }**; - First element in the preorder[] will definitely be the root, which is 20 here.
- we start with the range
and**minimum = Integer.MIN_VALUE**, so your root can take any value between this range.**maximum = Interger.MAX_VALUE** - So when putting the left node of 20(root), it must lie within the range to
, so check the next element in the**minimum = Integer.MIN_VALUE and maximum = 20**, if it lies in this range, make it the left child to the root, else it must the the right chlid of the root and so on. See the figure for better understanding. (**preorder[]**)**see the execution sequence** - Solve it recursively.

**Time Complexity: O(n)**

**Complete Code:**

**Output**:

Inorder Traversal of Constructed Tree : 1 5 7 10 15 20 25 30 32 35 40

if we put the elements into a stack cant we solve it with below algorithm also. I think we dont have to return the min values since the preorder is always needs to be assumed as correct. What do you think

public boolean buildBSTFromPreOrder(Node pNode,Integer max,Stack nodes){

if(nodes.isEmpty()){

return true;

}

if(max != null){

if(nodes.peek().data > max){

return false;

}

}

Node pop = nodes.pop();

if(pop.data < pNode.data){

pNode.left = pop;

}else{

pNode.right = pop;

}

boolean result = buildBSTFromPreOrder(pop,pNode.data,nodes);

if(!result){

return buildBSTFromPreOrder(pop, max, nodes);

}

return result;

}