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

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]"""

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        # if preorder is empty, return none
        if not preorder:
            return None
        # set root to first val in preorder
        root = TreeNode(preorder[0])
        # loop through preorder and if value is less than root node, add it to left list
        left = [node for node in preorder if node < preorder[0]]
        # loop through preorder and if value is more than root node, add it to right list
        right = [node for node in preorder if node > preorder[0]]
        # recurse through rest of list for right and left nodes
        root.left = self.bstFromPreorder(left)
        root.right = self.bstFromPreorder(right)
        
        # return tree
        return root

"""Runtime: 32 ms, faster than 96.33% of Python3 online submissions for Construct Binary Search Tree from Preorder Traversal.
Memory Usage: 14.3 MB, less than 49.25% of Python3 online submissions for Construct Binary Search Tree from Preorder Traversal."""