Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

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