def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Note:
        # BST traversal: root -> either -> left or -> right
        # 1. Process -> root : 
        #    determine if LCA is in left or right
        # 2. Process -> left or -> right :
        # Result: find LCA node
        
        # process root -> :
        # p and q are smaller, LCA in left subtree 
        if p.val < root.val and q.val < root.val:

            # process -> left :
            return self.lowestCommonAncestor(root.left, p, q)

        # process root -> :
        # p and q are larger, LCA in right subtree
        elif p.val > root.val and q.val > root.val:

            # process -> right :
            return self.lowestCommonAncestor(root.right, p, q)
        
        # process root -> :
        # p and q are in different subtrees, root is LCA
        else:
            return root

        # overall: time complexity
        # overall: space complexity

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Note:
        # BST traversal: root -> either -> left or -> right
        # 1. Process -> root : 
        #    determine if LCA is in left or right
        # 2. Process -> left or -> right :
        # Result: find LCA node

        # iterative root
        while root:

            # process root -> :
            # p and q are smaller, LCA in left subtree 
            if p.val < root.val and q.val < root.val:

                # process -> left :
                root = root.left

            # process root ->
            # p and q are larger, LCA in right subtree
            elif p.val > curr.val and q.val > curr.val:

                # process -> right :
                curr = curr.right

            # process root -> :
            # p and q are in different subtrees, root is LCA
            else:
                return curr
        
        # overall: time complexity
        # overall: space complexity

    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
        #
        # Example:
        #        4
        #       / \
        #      2   7
        #     / \
        #    1   3
        #
        # Inserting val = 5:
        #        4
        #       / \
        #      2   7
        #     / \  /
        #    1   3 5

        # 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 not root:
            # 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:
        # Idea:
        #   1. Traverse tree from root iteratively
        #   2. At each node, compare val with node.val
        #   3. Move left or right based on BST property
        #   4. When a None child is found, insert the new node
        
        if not root:
            # If tree is empty, new node becomes root
            # tc O(1), sc O(1)
            return TreeNode(val)
        
        current = root
        
        while True:
            if val < current.val:
                # Go left if left child exists
                if current.left:
                    current = current.left
                else:
                    # Insert new node as left child
                    current.left = TreeNode(val)
                    # tc O(1), sc O(1) for node creation
                    break
            else:
                # Go right if right child exists
                if current.right:
                    current = current.right
                else:
                    # Insert new node as right child
                    current.right = TreeNode(val)
                    # tc O(1), sc O(1) for node creation
                    break
        
        # Return root to maintain BST structure
        # tc: O(h) traversal along height
        # sc: O(1) iterative → no recursion stack
        return root

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        
        # Binary Search Tree Deletion:
        # BST property: left < node.val < right
        #
        # Deletion has 3 main cases:
        # 1. Node to delete has no children -> remove directly
        # 2. Node has one child -> 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
        
        if not root:
            # Base case: key not found
            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)
        else:
            # Found the node to delete
            if not root.left and not root.right:
                # Case 1: No children
                return None  # tc O(1), sc O(1)
            elif not root.left:
                # Case 2a: Only right child
                return root.right  # tc O(1), sc O(1)
            elif not root.right:
                # Case 2b: Only left child
                return root.left  # tc O(1), sc O(1)
            else:
                # Case 3: Two children
                # Find inorder successor: leftmost node in right subtree
                successor = root.right
                while successor.left:
                    successor = successor.left  # tc O(h) worst case
                
                # Replace root value with successor's value
                root.val = successor.val
                
                # Delete successor node in right subtree recursively
                root.right = self.deleteNode(root.right, successor.val)
                # tc: O(h) for deletion path
                
        # Return root to maintain BST structure
        # overall: tc O(h), sc O(h) recursion stack (O(log n) balanced, O(n) skewed)
        return root

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

        # Iterative BST Deletion
        # Idea:
        #   1. Use pointers to track current node and parent
        #   2. Traverse the tree to find the node with the key
        #   3. Once found, handle three deletion cases:
        #       a. No children -> just remove
        #       b. One child -> replace node with child
        #       c. Two children -> find inorder successor (smallest in right subtree),
        #          replace value, then remove successor
        
        if not root:
            return None  # tc O(1), sc O(1)
        
        # Dummy parent for convenience
        dummy = TreeNode(0)
        dummy.left = root
        parent = dummy
        current = root
        is_left_child = True  # Track whether current is left or right child of parent
        
        # Step 1: 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
        
        # Key not found
        if not current:
            return root  # tc O(h), sc O(1)
        
        # 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 might not change)
        # overall: tc O(h), sc O(1) iterative
        return dummy.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