Lc1008

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstFromPreorder(self, A: List[int]) -> TreeNode:
        # O(N^2)
        # termination case: current sub arr is empty
        if not A: return None
        root = TreeNode(A[0])
        i = bisect.bisect_right(A,A[0])
        root.left = self.bstFromPreorder(A[1:i])
        root.right = self.bstFromPreorder(A[i:])
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstFromPreorder(self, A: List[int]) -> TreeNode:
        """tc O(N) sc O(H)
        main idea: to use a global i to keep idx stateful, each recursion compare current val with bound, if reaches bound,return 
        """
        self.i = 0
        def helper(A,bound):
            if self.i == len(A) or A[self.i] > bound:
                return None
            root = TreeNode(A[self.i])
            self.i += 1
            root.left = helper(A,root.val)
            root.right = helper(A,bound)
            
            return root
        return helper(A,float('inf'))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstFromPreorder(self, A: List[int]) -> TreeNode:
        """tc O(N) sc O(H)
        main idea: to use a global i to keep idx stateful, each recursion compare current val with bound, if reaches bound,return 
        """
        def helper(A,bound):
            if not A or A[-1] > bound:
                return None
            root = TreeNode(A.pop())
            root.left = helper(A,root.val)
            root.right = helper(A,bound)
            
            return root
        return helper(A[::-1],float('inf'))