Delete Node: Finding Successor

The tricky case is when the node has two children. You need a replacement that maintains BST property.

The inorder successor (smallest node in right subtree) works perfectly:

• It's larger than everything in the left subtree (since it was in the right subtree)
• It's smaller than everything else in the right subtree (since it's the minimum there)

To find the successor:

def findMin(node):
    while node.left:
        node = node.left
    return node

Alternatively, use the inorder predecessor (largest in left subtree).

Both approaches maintain the BST property. Time: $O(h)$. Space: $O(h)$.