A binary search tree delete replaces a two-child node with its right child — what breaks?

## The three cases of delete Deleting from a binary search tree splits into cases by how many children the doomed node has. - **No children.** Detach it. Nothing below it needs a home. - **One child.** Splice: the child takes the node's place under its grandparent. This is safe because the whole child subtree already sits on the correct side of every ancestor — removing an intermediate node does not change any key's relationship to anything above it. - **Two children.** Neither child can simply be promoted, and this is the only interesting case. ## Why promoting a child is wrong A node has one slot in its parent. It has two subtrees. Promoting the right child hands that slot to the right subtree, and the left subtree — every key in it — is dropped on the floor. In a reference-counted or garbage-collected setting the memory quietly goes away; in a manually managed one it leaks. Either way the keys are gone from the structure. What makes this bug hard to see is that **the surviving tree is still perfectly valid**. Every remaining key is still in the right relationship to every ancestor, because deleting keys never breaks the ordering rule. So an ordering check over the tree passes. A shape or height check passes. A debugger view looks unremarkable. The only observable symptom is that a lookup for a key from the discarded subtree reports 'not present' — and if the caller treats absence as a legitimate answer, the corruption can sit in production indefinitely. The tests that catch it are behavioural: insert a known set, delete a middle key, assert the count and assert every other key is still retrievable. ## The inorder successor, and why it is the right replacement The key you want in the vacated position is one that is simultaneously **greater than everything in the left subtree** and **less than everything remaining in the right subtree**. Exactly one key in the tree satisfies that: the smallest key in the right subtree — the inorder successor of the node being deleted. Find it with a leftmost walk starting at the right child. The procedure is then: 1. Locate the node to delete by the usual descent. 2. If it has two children, walk to the leftmost node of its right subtree — the successor. 3. Copy the successor's key (and payload) into the node. 4. Delete the **successor** from the right subtree. Step 4 is not a recursion into the same hard case. The successor is leftmost in its subtree, so by definition it has no left child, which means it falls into the no-child or one-child case and terminates immediately. That is why the algorithm is only ever "one hard case plus one easy case", never an unbounded chain. The mirror-image choice is equally correct: take the **inorder predecessor**, the largest key in the left subtree, found by a rightmost walk. It satisfies the same betweenness condition from the other side and is just as cheap to remove, since being rightmost it has no right child. Implementations pick one and stick to it; some deliberately alternate between successor and predecessor so that long delete-heavy runs do not repeatedly thin the same side of the tree. ## A worked check Take a tree with root `50`, left subtree holding `30, 20, 40` and right subtree holding `70, 60, 80`. Delete `50`. The successor is the leftmost node of the right subtree, `60`. Copy `60` into the root, then delete the old `60` from the right subtree — it is a leaf, so it just detaches. The result has root `60`, left subtree `30, 20, 40`, right subtree `70` with only `80` under it. Check the invariant: everything on the left is below `60`, everything on the right is above it, and all seven remaining keys are still present. Now compare with the buggy version: promoting the right child would have made `70` the root and silently vaporised `30`, `20` and `40`. ## Cost, and a note on what is copied Deletion is `O(h)`: one descent to find the node, plus at most one further descent down the right subtree's leftmost spine, and those two paths together are still bounded by the height. Nothing scans. One practical wrinkle: copying the successor's *key* into the surviving node means the node object holding the deleted key survives while the node object holding the successor's key is destroyed. If anything outside the tree holds a reference to a node — an iterator, an index, a cached handle — that reference now points at a node whose key changed under it. Implementations that must keep node identity stable therefore relink pointers instead of copying contents: the successor node is unhooked from its position and spliced in as the actual replacement, adopting both subtrees. Same algorithm, more pointer surgery, no key copying. ## What a strong answer sounds like Say that promoting a child loses a whole subtree, stress that the corruption is invisible to an ordering check and only shows up as a missing key, then give the successor rule and the reason it is the unique correct replacement — and finish with why removing the successor is the easy case.