Loading learning content...
In the previous page, we encountered the fundamental challenge of two-child deletion: we need a replacement value that can legally occupy the deleted node's position. This value must be:
At first glance, this seems like an impossible constraint. How can we find such a value? Where does it come from?
The breakthrough insight comes from understanding inorder traversal. When you traverse a BST in inorder (left → root → right), you visit nodes in sorted ascending order. This property reveals exactly which nodes can serve as valid replacements.
In inorder traversal, the node immediately before a given node is its inorder predecessor, and the node immediately after is its inorder successor. These two nodes—and only these two—can replace any deleted node while preserving the BST property.
Before diving into successors and predecessors, let's solidify our understanding of inorder traversal. This traversal visits nodes in the following order:
For a BST, this produces nodes in sorted order. Consider this tree:
Inorder traversal sequence: 2 → 4 → 6 → 8 → 10 → 12 → 14 → 15 → 18 → 22 → 25
Notice this is perfectly sorted! The BST property guarantees this: since left < root < right at every node, inorder traversal naturally yields ascending order.
Now observe node 15 (the root) in this sequence. Its neighbors are:
If we delete node 15, we need a replacement that is: • Greater than all of {2, 4, 6, 8, 10, 12, 14} — the left subtree • Less than all of {18, 22, 25} — the right subtree
The predecessor (14) satisfies both! It's the largest value that's still less than 15, so it's greater than everything else in the left subtree. And since 14 < 15 < 18, it's definitely less than everything in the right subtree.
The successor (18) also works! It's the smallest value that's greater than 15, so it's less than everything else in the right subtree. And since 14 < 15 < 18, it's definitely greater than everything in the left subtree.
Definition: The inorder successor of a node N is the smallest value greater than N in the BST. Equivalently, it's the node that would be visited immediately after N in an inorder traversal.
Key Properties:
Location Rule: For a node with a right subtree, the successor is the leftmost node in the right subtree.
No Right Subtree Case: If the node has no right subtree, the successor is the nearest ancestor for which this node is in the left subtree.
The successor of the maximum element doesn't exist — there's no larger value in the tree.
Finding the Successor in the Two-Child Case:
When deleting a node with two children, we're guaranteed a right subtree exists. The successor is found by:
Walkthrough: To find the successor of 15:
Wait—18 has a left child (16). Let me revise the tree:
Correct Walkthrough: To find the successor of 15:
Successor = 16 — the leftmost node in the right subtree.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
interface TreeNode { value: number; left: TreeNode | null; right: TreeNode | null;} /** * Finds the inorder successor of a node (the smallest value greater than node). * For deletion purposes, we assume the node has a right child. * * @param node - The node whose successor we're finding (must have right child) * @returns The inorder successor node */function findInorderSuccessor(node: TreeNode): TreeNode { if (node.right === null) { throw new Error("Node must have a right child for this successor method"); } // Step 1: Go to right child (enter the right subtree) let successor = node.right; // Step 2: Go left as far as possible (find minimum of right subtree) while (successor.left !== null) { successor = successor.left; } return successor;} /** * Also returns the parent of the successor, needed for deletion. */function findInorderSuccessorWithParent( node: TreeNode): { successor: TreeNode; successorParent: TreeNode } { if (node.right === null) { throw new Error("Node must have a right child"); } let successorParent = node; let successor = node.right; while (successor.left !== null) { successorParent = successor; successor = successor.left; } return { successor, successorParent };}Definition: The inorder predecessor of a node N is the largest value smaller than N in the BST. Equivalently, it's the node that would be visited immediately before N in an inorder traversal.
Key Properties:
Location Rule: For a node with a left subtree, the predecessor is the rightmost node in the left subtree.
No Left Subtree Case: If the node has no left subtree, the predecessor is the nearest ancestor for which this node is in the right subtree.
The predecessor of the minimum element doesn't exist — there's no smaller value in the tree.
Finding the Predecessor in the Two-Child Case:
When deleting a node with two children, we're guaranteed a left subtree exists. The predecessor is found by:
Walkthrough: To find the predecessor of 15:
Predecessor = 14 — the rightmost node in the left subtree.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
interface TreeNode { value: number; left: TreeNode | null; right: TreeNode | null;} /** * Finds the inorder predecessor of a node (the largest value smaller than node). * For deletion purposes, we assume the node has a left child. * * @param node - The node whose predecessor we're finding (must have left child) * @returns The inorder predecessor node */function findInorderPredecessor(node: TreeNode): TreeNode { if (node.left === null) { throw new Error("Node must have a left child for this predecessor method"); } // Step 1: Go to left child (enter the left subtree) let predecessor = node.left; // Step 2: Go right as far as possible (find maximum of left subtree) while (predecessor.right !== null) { predecessor = predecessor.right; } return predecessor;} /** * Also returns the parent of the predecessor, needed for deletion. */function findInorderPredecessorWithParent( node: TreeNode): { predecessor: TreeNode; predecessorParent: TreeNode } { if (node.left === null) { throw new Error("Node must have a left child"); } let predecessorParent = node; let predecessor = node.left; while (predecessor.right !== null) { predecessorParent = predecessor; predecessor = predecessor.right; } return { predecessor, predecessorParent };}Notice that predecessor and successor finding are mirror images of each other:
• Successor: Go right once, then left as far as possible • Predecessor: Go left once, then right as far as possible
This symmetry makes them easy to remember and implement.
Let's rigorously prove why the inorder successor (or predecessor) is a valid replacement for a deleted node with two children.
Claim: If node N has two children and we replace N's value with its inorder successor S, the BST property is preserved.
Proof:
Let N be the node we're deleting. Let L be N's left subtree and R be N's right subtree.
Property 1: All values in L are less than N.value (BST property)
Property 2: All values in R are greater than N.value (BST property)
Property 3: S is the minimum value in R (by definition of inorder successor for a node with right child)
What we need to prove:
• All values in L < N.value (Property 1) • S is in R, so S.value > N.value (Property 2) • Therefore: All values in L < N.value < S.value • Conclusion: S.value > all values in L ✓
• S is the minimum of R (Property 3) • By definition of minimum, S.value ≤ all values in R • Since all values in BST are distinct, S.value < all other values in R • Conclusion: S.value < all values in R except S ✓
The Complete Picture:
After replacing N with S:
The BST property is maintained at N's position.
The same logic applies to the predecessor (symmetric proof with inequalities reversed).
This proof reveals why successor/predecessor are the ONLY valid replacement choices from within the tree:
• Any value between successor and predecessor (like the deleted node's value) works by definition • The successor is the smallest value greater than the deleted node — the tightest upper bound • The predecessor is the largest value smaller than the deleted node — the tightest lower bound
No other value in the tree can satisfy both constraints (greater than left, less than right) except these two boundary values.
Here's a crucial insight that makes two-child deletion tractable:
Theorem: The inorder successor (in the right subtree) has no left child.
Proof: The successor is the leftmost node in the right subtree. If it had a left child, that left child would be further left, contradicting that the successor is the leftmost.
Similarly: The inorder predecessor (in the left subtree) has no right child. If it had a right child, that right child would be further right, contradicting that the predecessor is the rightmost.
This means the successor/predecessor has at most one child!
This transforms two-child deletion into a solvable problem:
Step 3 is either a leaf deletion (no children) or a single-child deletion (has right child for successor, left child for predecessor). We already know how to handle both!
Two-child deletion reduces to the simpler cases.
In this example, successor 16:
To delete 15:
The tree restructures correctly, and the BST property is preserved throughout.
Both the inorder successor and inorder predecessor are valid replacement choices. In practice, which should you use?
Both approaches are correct. Most implementations default to using the inorder successor, but this is largely conventional rather than advantageous.
| Aspect | Inorder Successor | Inorder Predecessor |
|---|---|---|
| Definition | Smallest value greater than N | Largest value smaller than N |
| Location | Leftmost of right subtree | Rightmost of left subtree |
| At most has | Right child only | Left child only |
| Traversal to find | Right, then left-left-left... | Left, then right-right-right... |
| Convention | More commonly used | Equally valid alternative |
When might you choose one over the other?
Consistency: Pick one and stick with it. Mixing approaches can make debugging harder.
Tree Balance Considerations: If you always delete with successor, values shift leftward over many deletions (since we keep removing from the right subtree). Similarly, always using predecessor shifts values rightward. In heavily deletion-heavy applications, alternating could theoretically help maintain balance. In practice, self-balancing trees solve this properly.
Implementation Simplicity: Both require nearly identical code. The logic is symmetric.
Recommendation: Use the inorder successor by convention, unless you have a specific reason to prefer the predecessor. The algorithms are symmetric, so expertise in one transfers directly to the other.
Some implementations randomly choose between successor and predecessor for each deletion. This can help maintain tree balance in certain scenarios, as it avoids the systematic bias of always removing from one side. However, for standard applications, this complexity is rarely necessary.
We've established the complete theoretical foundation for two-child deletion. The key insights are:
In the next page, we put these concepts into action with a complete, production-ready implementation of BST deletion. We'll handle all three cases, track parent pointers, and ensure the BST property is maintained throughout. You'll walk away with code you can use in real applications.