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