Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal. [Form Binary Search Tree from Preorder Traversal]

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if(preorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        for(int i = 1; i < preorder.length; i++){
            constructBinarySearchTree(root, preorder[i]);
            System.out.println(root.val);
        }
        return root;
   
    }
   
    public TreeNode constructBinarySearchTree(TreeNode root, int val){
        if(root == null){
            return new TreeNode(val);
        }
        if(val < root.val){
            TreeNode left = constructBinarySearchTree(root.left, val);
            root.left = left;
            return root;
        }else{
            TreeNode right = constructBinarySearchTree(root.right, val);
            root.right = right;
            return root;
        }
       
    }
}



 Try it on Leetcode

Here, the input is given as pre-order traversal of a BST(Binary Search Tree). We have to construct a BST from those inputs.

A BST is a tree with having value less than a root node to its left and having values greater than root node to its right.

1) If root node is null we have to create a new node by adding the value.
2) If value is less than the root value, then.
     Do recursion on left subtree to find exact position of current value.
3)If value is greater than the root value, then.
     Do recursion on right subtree to find exact position of current value.

Example:

[8,5,1,7,10,12]

8 becomes root node

5 passed as value,after recursion then tree becomes

                8

              /

            5 

1 passed as value,after recursion then tree becomes

                8

              /

            5 

           /

          1 

7 passed as value,after recursion then tree becomes

                8

              /

            5 

           /  \

          1     7

10 passed as value, after recursion then tree becomes

                8

              /   \

            5      10

          /   \

         1      7

12 passed as value, after recursion then tree becomes

                8

              /   \

            5       10

           /   \       \

          1      7       12

Finally output  should be as follows, root, root.left, root.right.

[8,5,10,1,7,null,12]