Construct Binary Search Tree from Preorder Traversal

We are now solving a problem which is asked by many of the product based companies. An interviewer will ask you to construct a binary search tree using a preorder traversal array.
Before we proceed with this problem, let's recall the binary search tree with below-mentioned points:-

• The right subtree of a node contains only nodes with keys that are greater than the node's key.
• The left subtree of a node contains only nodes with keys that are lesser than the node's key.
• We have to check on each node with the above conditions.

Quadratic Solution O(n²)

    public static TreeNode bstFromPreorder(int[] preorder) { 
//      Initialize the treenode        

        TreeNode treeNode = new TreeNode();
//      Check if the preorder array does contain value        

        if (preorder.length > 0)
            treeNode.val = preorder[0];
//      Iterate over the 1 to preorder length        

        for (int i = 1; i < preorder.length; i++) {
            TreeNode currNode = treeNode;
            TreeNode prevNode = null;
            Boolean leftNode = false;
//          Iterate over the new binary search tree

//          check leftNode needs to be added in left or right node

//          prevNode will store the last element.

            while (currNode != null) {

                prevNode =  currNode;
                if (currNode.val > preorder[i]) {
                    currNode = currNode.left;
                    leftNode = true;
                } else {
                    currNode = currNode.right;
                    leftNode = false;
                }
            }
//          Adding a new node into the binary tree            

            TreeNode temp = new TreeNode();
            temp.val = preorder[i];
            if (leftNode) {
                prevNode.left = temp;
            } else                

                prevNode.right = temp;
        }
//      Final result of the binary search tree.        
        return treeNode;
    }

Linear Solution O(n)

//      Initialize the i and increment on the every new tree node 

//      in existing tree or root.   

        static  int i = 0        

        public static TreeNode bstRecursion(int[] preOrder, int rootValue) {
//          Base condition i increase the array length and root value is greater 

//          than the new node.        

            if (i > preOrder.length-1 || preOrder[i] > rootValue)
                return null;
//          Create a new node with element and increment i.        

            TreeNode root = new TreeNode(preOrder[i++]);
//          Add element in the last node to left and call recursively 

//          until base condition false.

            root.left = bstRecursion(preOrder, root.val);
//          Add element in the last node to right and call recursively 

//          until base condition false.

            root.right = bstRecursion(preOrder, rootValue);
//         completion of the recursion stack, it will return the root node.       

            return root;
    }