BST Deletion: Two Children Case
What you'll learn: How to delete a node that has two children by replacing it with its inorder successor or predecessor.
When you need to delete a node with two children from a Binary Search Tree, you can't simply remove it like a leaf or single-child node—there are two subtrees that need to remain connected. The solution is elegant: replace the node's value with either its inorder successor (the smallest value in its right subtree) or inorder predecessor (the largest value in its left subtree), then delete that replacement node instead.
Why This Works
The inorder successor is the next larger value in the BST, while the inorder predecessor is the next smaller value. Either one can take the deleted node's place while maintaining the BST property. Think of it like succession planning: when a manager with two teams leaves, you promote someone who can naturally fit into that position—either the most senior person from the "higher" team or the most advanced from the "lower" team.
The Strategy
- Find the replacement: Navigate to the right subtree's minimum (successor) or left subtree's maximum (predecessor)
- Copy the value: Replace the target node's value with the successor/predecessor's value
- Delete the replacement node: The successor/predecessor will have at most one child, making it an easier deletion case you've already learned
The beauty of this approach is that it reduces the two-children problem to a simpler case (leaf or one child), which you already know how to handle.
Key Takeaway: Deleting a BST node with two children is solved by replacing its value with its inorder successor or predecessor, then recursively deleting that simpler replacement node.