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)


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

  • 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 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 element in the preorder[], 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 understanding. ( see the execution sequence)
  • Solve it recursively.

Time Complexity: O(n)

Preorder Traversal To Tree Using Recursion

Complete Code:


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

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

1 Response

  1. fatih tekin says:

    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){

    return true;

    if(max != null){
    if(nodes.peek().data > max){
    return false;

    Node pop = nodes.pop();
    if( <{
    pNode.left = pop;
    pNode.right = pop;
    boolean result = buildBSTFromPreOrder(pop,,nodes);
    return buildBSTFromPreOrder(pop, max, nodes);
    return result;

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: