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


Output:

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

  • fatih tekin

    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;
    }

%d bloggers like this: