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

Objec­tive: - Given a pre­order tra­ver­sal, con­struct BST from that.

Input: Pre­order traversal

Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the — Con­struct Binary Search Tree from a given Pre­order Tra­ver­sal Using Stack (With­out Recursion)

Approach:

Solu­tion to the prob­lem is sim­i­lar to isBST Max-Min Solu­tion.

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

So the idea is Pass the min­i­mum and max­i­mum val­ues between which the node’s value must lie.

• Exam­ple: int[] pre­Order = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 };
• First ele­ment in the pre­order[] will def­i­nitely be the root, which is 20 here.
• we start with the range min­i­mum = Integer.MIN_VALUE and max­i­mum = Interger.MAX_VALUE, so your root can take any value between this range.
• So when putting the left node of 20(root), it must lie within the range to min­i­mum = Integer.MIN_VALUE and max­i­mum = 20, so check the next ele­ment in the pre­order[], 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 fig­ure for bet­ter under­stand­ing. ( see the exe­cu­tion sequence)
• Solve it recursively.

Time Com­plex­ity: O(n)

Preorder-Traversal-To-Tree

Com­plete Code:

Out­put:

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

#### You may also like...

• fatih tekin

if we put the ele­ments into a stack cant we solve it with below algo­rithm also. I think we dont have to return the min val­ues since the pre­order is always needs to be assumed as cor­rect. What do you think

pub­lic 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;
}