Course contentsShow
← Computer Science
Lesson 510 of 2,87212. Binary Search TreesFree lesson

BST Deletion: Two Children Case

Delete a node with two children using inorder successor or predecessor replacement strategy.

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

  1. Find the replacement: Navigate to the right subtree's minimum (successor) or left subtree's maximum (predecessor)
  2. Copy the value: Replace the target node's value with the successor/predecessor's value
  3. 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.