Deleting a Node from a Binary Search Tree: The Three Cases

Introduction

Deleting a tree node is mostly a reference-update problem. The program first finds the node, checks how many children it has, and then reconnects the remaining nodes. The difficult part is not removing the value itself. The difficult part is keeping the rest of the tree connected and correctly ordered.

For example, removing a node with no children is simple because its parent can point to null. Removing a node with one child means the parent must point to that child instead. A node with two children requires one additional step because either child might not fit directly into the removed node's position.

Deletion is a reference problem

Searching a binary search tree follows comparisons until it finds a value. Deletion begins along the same path, but then it must reconnect the surrounding nodes without breaking the BST ordering rule. This rule is sometimes called the BST invariant. It means that values on the left must be smaller than the current node and values on the right must be larger, according to the tree's comparison policy.

The value is not the only thing being removed. One or more child references must also change. A subtree is a node together with all of the nodes below it. During deletion, a subtree may receive a different root node, so the parent must update its reference to that subtree.

The Binary-Search-Tree repository stores each node as { data, left, right }, with null for an absent child. Its delete(value) method assigns the result of a recursive deletion to this.root. That assignment is important when the root itself is removed.

The repository ignores duplicate values, so the tree contains at most one node for a given numeric value. The descriptions below separate documented source behavior, demonstrated examples, and design reflection.

The decision at the target node

Once the recursive search reaches the node whose data equals the requested value, the implementation chooses one of three cases:

Decision flow for the three BST deletion cases

The recursive function returns the root that should occupy the current subtree's position. The caller assigns that returned node to either left or right; at the top level, delete assigns it to tree.root. This allows the same logic to work when the deleted node is deep in the tree and when it is the root.

Case 1: deleting a leaf

A leaf is a node with no children. Its parent can simply stop pointing at it. In a recursive implementation, returning null expresses that replacement directly:

parent.left = deleteRecursive(parent.left, target)
                         ↓
                       null

If the leaf is the root, the same return makes the whole tree empty. No separate parent variable is needed.

Case 2: deleting a node with one child

When the target has exactly one child, the parent should point around the target to that child. Returning the non-null child preserves the entire remaining subtree. The child is not copied; the parent simply receives a reference to the existing child.

before:  parent -> target -> child
after:   parent ------------> child

Deleting a root with one child follows the same rule: the returned child becomes the new tree.root. This is why returning updated subtree roots is safer than changing only a local variable; every ancestor receives the replacement through its own assignment.

Case 3: deleting a node with two children

A node with two children cannot be replaced by either child arbitrarily. The repository chooses the inorder successor. This is the smallest node in the target's right subtree. Because it is the next value after the target in sorted order, it can occupy the target's position without breaking the BST ordering rule.

The operation has two parts:

Walk right once, then left repeatedly to locate the successor.
Copy the successor's data into the target, then recursively delete the successor from its original position in the right subtree.

The second step is easy to miss. Otherwise the successor would exist twice. The repository performs the recursive removal first in its two-child branch, then assigns the saved successor value to the current node.

Before and after deleting 20 using the minimum value from its right subtree

The successor has no left child by definition, so its eventual deletion is a leaf or one-child case. The separate predecessor-versus-successor choice is explored in the next article; this one follows the repository's successor strategy.

Root deletion and recursive returns

Deleting the root is not a special algorithmic case, but it is a useful test of the interface. The top-level method does this conceptually:

tree.root = deleteRecursive(tree.root, value)

At each recursive level, the same pattern reconnects a child:

node.left  = deleteRecursive(node.left, value)
node.right = deleteRecursive(node.right, value)

These snippets are intentionally structural rather than a full solution. The key idea is that a subtree can change its root after deletion, and the parent must receive that new root.

A small trace

Start with this tree and delete 20:

The target has two children. The successor search enters the right subtree at 30, then follows left to 25. The current node takes the value 25; the old 25 node is then removed from under 30. The result is a valid tree with one 25 and no 20.

This trace is a demonstrated example of the current algorithm's control flow, not a benchmark or a claim about all BST implementations.

Invariant checklist

After each deletion, a focused test can check:

Every value in a node's left subtree is lower according to the project's numeric comparison policy.
Every value in its right subtree is higher.
Every node that should remain is reachable from tree.root.
The requested value is absent.
A leaf deletion does not remove its siblings.
A one-child deletion preserves the complete child subtree.
A two-child deletion leaves exactly one copy of the replacement value.

The repository's duplicate policy makes the last check especially straightforward: there should not have been multiple equal values to choose between.

Cost and shape

Let h be the tree height. Finding the target costs O(h). Finding the successor adds at most another downward walk, still O(h), so deletion is O(h) overall. A balanced tree makes that roughly O(log n); a skewed tree can make it O(n). The method uses recursion, so its call stack is also O(h).

Reflection

The most helpful mental shift was to describe deletion as “return the subtree that should replace this position,” rather than “find a parent and mutate several pointers.” That framing handles leaves, children, and the root with one recursive shape. It also makes the two-child case less mysterious: replacing a value is only half the job; the old successor position must be repaired too.

Key takeaways

A leaf returns null, while a one-child node returns its only child.
A two-child node uses the repository's inorder successor and then removes that successor from its old position.
Recursive subtree-root returns update parent links and make root deletion work naturally.
A valid deletion preserves ordering, reachability, and absence of the removed value.
The cost is O(h), not automatically O(log n).