https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

ConstructBinarySearchTreefromPreorderTraversal.py

# First pass. Clunky but works in O(n)
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        
        i = 0
        
        def insert(gt, lt):
            nonlocal i
            if i >= len(preorder): return None
            
            root = TreeNode(preorder[i])
            i+=1
                
            if i >= len(preorder): return root
            
            greaterThan = max(gt if gt != None else -float("inf"), root.val)
            lessThan    = min(lt if lt != None else  float("inf"), root.val)
            
            nextVal = preorder[i]
            if nextVal < root.val: # should go to the left
                if gt == None or nextVal > gt: # if we can legally insert it to the left
                    root.left = insert(gt, lessThan) # insert it
    
            if i >= len(preorder): return root
            
            nextVal = preorder[i]
            if nextVal > root.val: # should go to the right
                if lt == None or nextVal < lt: # if we can legally insert it to the right
                    root.right = insert(greaterThan, lt) # insert it
                
            return root
            
        return insert(None, None)
      
# much more tidily refactored after looking for inspo
# Same idea. Same O(n)
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        i = 0
        
        def insert(gt=float("-inf"), lt=float("inf")):
            nonlocal i
            
            if i >= len(preorder): return None
            
            if gt < preorder[i] < lt:
                root = TreeNode(preorder[i])
                i+=1
                root.left = insert(gt, root.val)
                root.right = insert(root.val, lt)
                return root
            return None
            
        return insert()