4
      /   \
     2     5
    / \
   1   3

left subtree of 4:  {1, 2, 3}  all < 4
right subtree of 4: {5}        all > 4

DFS in-order visit: 1 → 2 → 3 → 4 → 5

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    
        # Lowest Common Ancestor:
        # Lowest node height/depth wise in a tree that has both p and q above it 

        # BST Traversal: (root -> left or right)
        # BST property (left < root < right) guides us toward the LCA at each node
        #   - If both p and q are smaller, LCA must be in left subtree
        #   - If both p and q are larger, LCA must be in right subtree
        #   - Otherwise root is the split point — root is the LCA

        # Both p and q are smaller: LCA in left subtree
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        # Both p and q are larger: LCA in right subtree
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        # p and q are on different sides: root is the LCA
        else:
            return root

        # Guaranteed to have the lowest point:
        # The moment p and q are on different sides, 
        # any node deeper would only contain one of them, not both.
        # So the split node is the lowest node that 
        # still has both p and q as descendants

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(log n) for balanced / O(n) for skewed trees

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # BST Traversal: (root -> left or right) using Iteration
        #   - BST property guides us toward the LCA at each node
        #   - If both p and q are smaller, LCA must be in left subtree
        #   - If both p and q are larger, LCA must be in right subtree
        #   - Otherwise root is the split point — root is the LCA

        # Tree Iterator
        # sc: O(1)
        node = root

        # Traverse until LCA is found
        while node:

            # Both p and q are smaller — LCA in left subtree
            if p.val < node.val and q.val < node.val:
                node = node.left

            # Both p and q are larger — LCA in right subtree
            elif p.val > node.val and q.val > node.val:
                node = node.right

            # p and q are on different sides — node is the LCA
            else:
                return node

            # Guaranteed to have the lowest point:
            # The moment p and q are on different sides, 
            # any node deeper would only contain one of them, not both.
            # So the split node is the lowest node that 
            # still has both p and q as descendants

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(1)

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        
        # Binary Search Tree:
        # BST property: For any node:
        #    left subtree nodes < node.val < right subtree nodes

        # Recursive DFS:
        #   1. Compare val with root.val
        #   2. If val < root.val, recurse left
        #   3. If val > root.val, recurse right
        #   4. If reached None, insert node here
        
        # Base case: reached a leaf, insert new node here
        if root == None:
            # tc O(1), sc O(1) for node creation
            return TreeNode(val)
        
        # Decide whether to insert left or right
        if val < root.val:
            # Insert into left subtree
            root.left = self.insertIntoBST(root.left, val)
        else:
            # Insert into right subtree
            root.right = self.insertIntoBST(root.right, val)
        
        # Return root node to maintain BST structure upwards
        # tc: O(h) for traversing height of tree
        # sc: O(h) recursion stack (O(log n) balanced, O(n) skewed)
        return root

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        
        # Iterative BST insertion:
        # Traverse tree from root iteratively to avoid recursive stack
        #   - At each node, compare node.val with val
        #   - Move left or right to maintain the BST property
        #   - When reached a 'None' child, have found insertion point for val
        

        # Empty Case:
        # If tree is empty, new node becomes root
        if not root:
            return TreeNode(val)
        
        # Tree Traversal
        # sc: O(1)
        current = root
        
        # Iterate until we have reached insertion point for val
        while True:

            # Check left
            if val < current.val:
                
                # Go left if left child exists
                if current.left:
                    current = current.left

                # Reached 'None', insert val here  
                else:
                    current.left = TreeNode(val)
                    break

            # Check right
            else:

                # Go right if right child exists
                if current.right:
                    current = current.right
                
                # Reached 'None', insert val here  
                else:
                    current.right = TreeNode(val)
                    break
        
        # Return original root to maintain BST structure

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc: O(1) 
        return root

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        
        # BST property: left < node.val < right
        
        # Binary Search Tree Deletion: 3 main cases

        # 1. Node to delete has no children:
        #       a. remove directly

        # 2. Node has one child:
        #       a. replace node with child

        # 3. Node has two children: 
        #       a. find inorder successor (smallest node in right subtree)
        #       b. replace node value with successor
        #       c. delete successor node recursively
        
        # Base case: 
        # Reached 'None' child, key was not found
        if root == None:
            return None
        
        # Traverse left or right depending on BST property
        
        if key < root.val:
            # Key may be in left subtree
            root.left = self.deleteNode(root.left, key)
        
        elif key > root.val:
            # Key may be in right subtree
            root.right = self.deleteNode(root.right, key)
        
        # Key matches current node,
        # check 3 BST deletion cases
        else:

            # Case 1: Node has no children
            #   - remove by returning 'None' up the recursion calls
            if root.left == None and root.right == None:
                return None

            # Case 2: Node only has 1 child
            #   - remove by returning the 1 child
            elif root.left == None:
                return root.right
            elif root.right == None:
                return root.left

            # Case 3: Node has 2 children
            #   - find inorder successor (smallest node in right subtree)
            #   - replace node value with successor
            #   - delete successor node recursively
            else:

                # Grab right subtree
                successor = root.right

                # Find smallest node in right subtree
                # tc O(h) worst case
                while successor.left:
                    successor = successor.left
                
                # Replace key successor's value
                root.val = successor.val
                
                # Delete successor node from right subtree recursively
                # tc: O(h) for deletion path
                root.right = self.deleteNode(root.right, successor.val)
                 
        # Return original root to maintain BST structure

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return root

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:

        # Iterative BST Deletion
        # Use pointers to track current node and parent to avoid recursive calls

        # BST property: left < node.val < right
        
        # Binary Search Tree Deletion: 3 main cases

        # 1. Node to delete has no children:
        #       a. remove directly

        # 2. Node has one child:
        #       a. replace node with child

        # 3. Node has two children: 
        #       a. find inorder successor (smallest node in right subtree)
        #       b. replace node value with successor
        #       c. delete successor node recursively

        # Base case: 
        # Reached 'None' child, key was not found
        if not root:
            return None
        
        # Dummyhead to keep track of original  parent for convenience
        # sc: O(1)
        dummyHead = TreeNode(0)
        dummyHead.left = root
        parent = dummyHead

        # BST Iterator
        # sc: O(1)
        current = root

        # BST Info:
        # Track whether current is left or right child of parent,
        # to validate 3 edge cases
        # sc: O(1)
        is_left_child = True
        
        # Step 1: Iterate over BST to find node to delete
        while current and current.val != key:
            parent = current
            if key < current.val:
                current = current.left
                is_left_child = True
            else:
                current = current.right
                is_left_child = False
        
        # Early Exit: 
        # Key was not found, return original root
        if not current:
            return root
        
        
        # Step 2: Node has two children
        if current.left and current.right:
            # Find inorder successor (leftmost node of right subtree)
            successor_parent = current
            successor = current.right
            while successor.left:
                successor_parent = successor
                successor = successor.left  # tc O(h)
            
            # Replace current value with successor value
            current.val = successor.val
            
            # Prepare to delete successor node
            parent = successor_parent
            current = successor
            is_left_child = (successor_parent.left == successor)
        
        # Step 3: Node has at most one child
        child = current.left if current.left else current.right  # could be None
        
        # Attach child to parent
        if is_left_child:
            parent.left = child
        else:
            parent.right = child
        
        # Return root original root

        # overall: tc O(h)
        # overall: sc O(1)
        return dummyHead.left

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    validate order
        # 2. Process -> left -> right : 
        # Result: validated BST
        
        def dfs(node, low, high):

            # Process root -> : 
            if not node:
                return True

            # Process root -> : validate order
            if not (low < node.val < high):
                return False

            # Process -> left -> right :
            left_valid = dfs(node.left, low, node.val)
            right_valid = dfs(node.right, node.val, high)

            # Process -> left -> right :
            subtreeValid = left_valid and right_valid

            return subtreeValid

        # Start with infinite bounds
        treeValid = dfs(root, float('-inf'), float('inf'))

        # overall: time complexity
        # overall: space complexity
        return treeValid

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # Note:
        # BFS pre order: process level: root -> left -> right
        # 1. Process level: 
        #      Process root -> :
        #        validate range limits
        # 2. Process -> left -> right : 
        # Result: validated BST

        # iterative queue
        queue = deque([(root, float('-inf'), float('inf'))])

        while queue:

            # Process root -> :
            node, low, high = queue.popleft()

            # Process root -> : 
            if not node:
                continue

            # Process root -> : validate order
            if not (low < node.val < high):
                return False

            # Process -> left -> right :
            queue.append((node.left, low, node.val))
            queue.append((node.right, node.val, high))

        # overall: time complexity
        # overall: space complexity
        return True

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # Note:
        # DFS in order: left -> root -> right
        # 1. Process left -> : 
        # 2. Process -> root -> :
        #    if reached kth node, return
        # 3. Process -> right :
        # Result: kth smallest found

        # global counter
        k = k
        # global pointer
        result = None
        
        def inorder(node):
            nonlocal k
            nonlocal result

            # Process left -> :
            if not node or result is not None:
                return
            
            # Process left -> :
            inorder(node.left)
            
            # Process root -> : 
            # if kth node, return
            k -= 1
            if k == 0:
                result = node.val
                return
            
            # Process right -> : 
            inorder(node.right)
        
        inorder(root)

        # overall: time complexity
        # overall: space complexity
        return result

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # Note:
        # DFS in order: left -> root -> right
        # 1. Process left -> : 
        # 2. Process -> root -> :
        #    if reached kth node, return
        # 3. Process -> right :
        # Result: kth smallest found

        # iterative stack
        stack = []
        
        while True:

            # Process left -> :
            while root:
                stack.append(root)
                root = root.left
            
            # Process -> root -> :
            root = stack.pop()

            # Process -> root -> : 
            # if kth node, return
            k -= 1
            if k == 0:
                return root.val
            
            # Process -> right :
            root = root.right

        # overall: time complexity
        # overall: space complexity

    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        
        # DFS + BST Optimization
        #
        # We can use the BST property to prune entire subtrees, instead of exploring invalid subtrees.
        # 
        #   1. If node.val < low:
        #        - the entire left subtree is invalid
        #        - return trimmed right subtree
        #
        #   2. If node.val > high:
        #        - the entire right subtree is invalid
        #        - return trimmed left subtree
         
        #   3. Otherwise:
        #        - node is valid
        #        - recursively into both left and right subtrees to trim

        if not root:
            return None

        # Node too small:
        # discard left + trim right
        if root.val < low:
            return self.trimBST(root.right, low, high)

        # Node too large:
        # discard right + trim left
        if root.val > high:
            return self.trimBST(root.left, low, high)

        # Node is valid:
        # trim left and right
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)

        # overall: O(n)
        # overall: O(log(n)) for balanced / O(n) for skewed
        return root