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: . Space: .