Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

&nbsp;
Example 1:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]


Example 2:

Input: preorder = [1,3]
Output: [1,null,3]


&nbsp;
Constraints:


	1 &lt;= preorder.length &lt;= 100
	1 &lt;= preorder[i] &lt;= 1000
	All the values of preorder are unique.


class Solution:
	def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
		if not preorder:
			return None
		node = preorder.pop(0)
		root = TreeNode(node)
		l = []
		r = []

		for val in preorder:
			if val < node:
				l.append(val)
			else:
				r.append(val)

		root.left = self.bstFromPreorder(l)
		root.right =  self.bstFromPreorder(r)
		return root
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        return bst(preorder, 0, preorder.length-1);
    }

    public TreeNode bst(int[] preorder, int start, int end){
        if(start > end) return null;

        TreeNode root = new TreeNode(preorder[start]);
        int breakPoint = start+1;
        while(breakPoint <= end && preorder[breakPoint] < preorder[start]){
            breakPoint++;
        }

        root.left = bst(preorder, start+1, breakPoint-1);
        root.right = bst(preorder, breakPoint, end);
        return root;
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* help(int &i,vector<int>& preorder, int bound ){
        if(i==preorder.size() || preorder[i] > bound)
            return NULL;
         TreeNode* root = new TreeNode(preorder[i++]);
         root->left = help(i,preorder,root->val);
         root->right = help(i,preorder,bound);
        return root;
    }
    TreeNode* bstFromPreorder(vector<int>& preorder) {
     
        int i=0;
        return help(i,preorder,INT_MAX);
    }
};
var bstFromPreorder = function(preorder) {
  let head = new TreeNode(preorder[0]);
  for (let i = 1, curr; i<preorder.length; i++) {
     curr = head;
     while (1) {
        if (preorder[i]>curr.val) 
          if (curr.right !=null) { curr = curr.right; }
          else { curr.right = new TreeNode(preorder[i]); break; }
        else
          if (curr.left !=null) { curr = curr.left; }
          else { curr.left = new TreeNode(preorder[i]); break; }
     } 
  } 
  return head;  
};
Construct Binary Search Tree from Preorder Traversal