Deleting a Node with Two Children from a BST

Deleting from a binary search tree has three cases, distinguished by how many children the target node $x$ has:

The two-children rule

The only key that may take $x$'s place without breaking the BST ordering is an immediate in-order neighbour of $x$. There are exactly two choices:

• the in-order predecessor — the largest key in the left subtree, found by going left once and then right as far as possible (the rightmost node of the left subtree); or
• the in-order successor — the smallest key in the right subtree, found by going right once and then left as far as possible (the leftmost node of the right subtree).

Why these work: the predecessor is the value just below $x$ in sorted order, so every key in the left subtree stays $\le$ it and every key in the right subtree stays $>$ it — the BST invariant is preserved. Crucially, both the predecessor and the successor have at most one child (the predecessor has no right child; the successor has no left child), so once you copy the key up, removing the original node falls into the easy 0- or 1-child case.

How to apply it

1. Locate the node $x$ to delete and confirm it has two children.
2. Pick a strategy — say, the in-order successor $s$ = leftmost node of $x$'s right subtree.
3. Copy $s$'s key into $x$ (overwrite $x$'s key; structure of the tree is unchanged so far).
4. Recursively delete $s$ from the right subtree. Since $s$ is leftmost, it has no left child, so this is a 0- or 1-child deletion.

The whole operation walks one root-to-leaf path to find $x$ and another to find the predecessor/successor, so it costs $O(h)$ time, where $h$ is the height ($\Theta(\log n)$ if balanced, $\Theta(n)$ in the worst case).

Worked mini-example

Delete the root $50$ from:

        50
       /  \
     30    70
    /  \   /  \
  20   40 60   80

• Predecessor route: largest key in the left subtree = rightmost of $\{20,30,40\}$ = $40$. Replace $50$ with $40$, then delete the old $40$ (a leaf).
• Successor route: smallest key in the right subtree = leftmost of $\{60,70,80\}$ = $60$. Replace $50$ with $60$, then delete the old $60$ (a leaf).

Either replacement keeps the tree a valid BST. So the candidates that can replace the deleted root are exactly the predecessor ($40$) and the successor ($60$) — no other node qualifies.

Exam trick: when a question asks "which element can replace the deleted (two-child) node?", the answer is always one of just two nodes: the rightmost node of the left subtree (predecessor) or the leftmost node of the right subtree (successor). Any other node in the tree is a distractor. Remember: predecessor = left-then-all-right; successor = right-then-all-left.