Deletion Operations

▶

Deletion is one of the three fundamental operations on a Binary Search Tree (BST), alongside insertion and search. While insertion and search follow relatively straightforward recursive paths, deletion is more nuanced because removing a node must not break the BST ordering property — the invariant that every node's left subtree contains only values strictly less than that node, and its right subtree contains only values strictly greater. To handle this cleanly, deletion is decomposed into three distinct cases based on the structural role of the node being removed. Understanding which case applies — and why each strategy works — is the key to implementing correct and efficient BST deletion.

Before any pointers are changed, the first step is always to locate the target node using a standard BST search: start at the root, go left if the target is smaller than the current node, go right if it is larger, and stop when the target is found (or confirm it is absent). Once found, the node's structure is assessed: does it have zero children, one child, or two children? That assessment determines the entire strategy for removal.

Overview of the Three Cases

At a high level, the three cases are:

Case 1 — Leaf node: The target has no children. It can be removed immediately, and the parent simply nullifies the pointer that was pointing to it.
Case 2 — One child: The target has exactly one subtree (left or right). The parent is rewired to point directly to that subtree, bypassing and discarding the target node.
Case 3 — Two children: The target has both a left and a right subtree. It cannot be simply removed without leaving two disconnected subtrees. Instead, its value is replaced with a suitable substitute — the in-order successor or in-order predecessor — and then that substitute node is deleted from its original position, which always reduces to Case 1 or Case 2.

Each case is examined in depth below.

Case 1: Deleting a Leaf Node

A leaf node is one with no left child and no right child. Because it is at the fringe of the tree, its removal has no downstream consequences — there are no subtrees to reconnect. The operation is as simple as it gets: find the parent of the leaf, determine whether the leaf is the parent's left or right child, and set that pointer to null.

Consider this BST:

Deleting 20: Node 20 is a leaf (no children). Its parent is 30, and 20 is 30's left child. The deletion simply sets 30.left = null. The result:

The BST property is trivially maintained because no existing relationships have changed — only a null reference was introduced where there was previously a pointer to a node with no descendants.

In code terms, a recursive deletion function that returns the updated subtree root handles this naturally:

def delete(node, key):
    if node is None:
        return None                    # key not found
    if key < node.value:
        node.left = delete(node.left, key)
    elif key > node.value:
        node.right = delete(node.right, key)
    else:
        # Found the node to delete
        if node.left is None and node.right is None:
            return None                # Case 1: leaf — remove it
        # Cases 2 and 3 handled below...
    return node

Returning None effectively detaches the leaf from its parent when the parent assigns the return value back to its child pointer.

Case 2: Deleting a Node with One Child

When the target node has exactly one child (either a left subtree or a right subtree, but not both), the solution is a bypass: the parent of the target is rewired to point directly to the target's single child. The target node itself is discarded.

Why does this preserve the BST property? Because the subtree rooted at the single child was already correctly positioned relative to the target's parent. If the target was the parent's left child, then every node in the target's subtree was already less than the parent (the BST property guaranteed this). Promoting the child one level up does not change any of those relationships.

Using the previous tree, now delete 30 (which has one child — the right child 40):

Before:          After:
    50               50
   /  \             /  \
  30   70          40   70
    \
    40

The parent (50) previously had 50.left = 30. After deletion, 50.left = 40. Node 40 steps into the position formerly held by 30, and since 40 was already less than 50 (it lived in 50's left subtree), the BST property is intact.

It makes no difference whether the surviving child is a left child or a right child of the deleted node; the bypass logic is identical in both cases:

    else:
        if node.left is None:
            return node.right          # Case 2a: only right child
        if node.right is None:
            return node.left           # Case 2b: only left child

Returning the surviving child causes the parent's pointer to be updated automatically by the recursive assignment.

Case 3: Deleting a Node with Two Children

This is the most complex case. When the target node has both a left subtree and a right subtree, there is no single child to promote — promoting either subtree root would leave the other subtree stranded. Instead, the strategy is:

Find a replacement value that can legally occupy the target node's position without violating BST order.
Copy that replacement value into the target node (overwriting the value that was there).
Delete the replacement node from its original position in the tree (a recursive call that will resolve to Case 1 or Case 2).

The two valid replacement candidates are the in-order successor and the in-order predecessor. Both are guaranteed to fit legally into the target's position, and both have at most one child, making their own deletion straightforward.

Example — delete 50 from:

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

Node 50 has two children. Using the in-order successor (60): copy 60 into the target position, then delete 60 from the right subtree. Since 60 is a leaf, that is a Case 1 deletion.

Result:
        60
       /  \
     30    70
    /  \     \
  20   40    80

Every BST invariant is satisfied: 60's left subtree (30, 20, 40) contains values less than 60; 60's right subtree (70, 80) contains values greater than 60.

The In-Order Successor

The in-order successor of a node is the node with the smallest value that is still greater than the target. In a BST, if the target node has a right subtree, the in-order successor is the leftmost node in that right subtree — reached by going right once, then following left pointers until the left child is null.

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

Why is the in-order successor a legal replacement?

It is greater than every value in the target's left subtree — because it comes from the right subtree, which already contained values greater than the target, and the target was greater than the entire left subtree.
It is less than every other value in the target's right subtree — because it is the minimum of that right subtree; all other nodes there are larger.
It has at most one child (a right child only). If it had a left child, that left child would be smaller and would have been the leftmost node instead — a contradiction. So the in-order successor's own deletion is always Case 1 (no children) or Case 2 (only a right child).

The full Case 3 logic using the in-order successor:

    else:
        # Case 3: two children
        successor = find_min(node.right)
        node.value = successor.value          # overwrite with successor's value
        node.right = delete(node.right, successor.value)  # remove successor
    return node

The In-Order Predecessor

The in-order predecessor is the mirror image: the node with the largest value that is still less than the target. It is found by going left once from the target, then following right pointers to the rightmost node.

def find_max(node):
    while node.right is not None:
        node = node.right
    return node

Like the successor, the predecessor satisfies the BST property at the target position:

It is greater than every other node in the left subtree — because it is the maximum of that subtree.
It is less than every node in the right subtree — because it lived in the left subtree, and all left-subtree values are less than the target, which is less than all right-subtree values.
It has at most one child (a left child only), so its own deletion is Case 1 or Case 2.

Using the in-order predecessor to delete 50 from the same tree:

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

40 (the in-order predecessor of 50) is copied to the root position; then 40 is deleted from its original location — it was a leaf, so Case 1 applies.

Both the in-order successor and in-order predecessor are equally valid replacements. Implementations often default to one convention (commonly the successor), but alternating between them can produce more balanced trees in practice when deletions are frequent.

Comparing the Three Cases Side by Side

Case	Condition	Strategy	Pointer changes	BST property
Case 1	No children (leaf)	Remove directly	Parent's pointer → null	Trivially preserved
Case 2	Exactly one child	Bypass the target	Parent's pointer → target's child	Preserved — subtree was already ordered correctly relative to parent
Case 3	Two children	Replace value with in-order successor or predecessor, then delete that node	Value overwrite + recursive delete of replacement	Preserved — replacement value legally fits in target position

Preserving BST Integrity After Deletion

The overriding concern throughout every deletion case is maintaining the BST invariant: for any node N, all values in N's left subtree are strictly less than N's value, and all values in N's right subtree are strictly greater. Deletion is the operation most likely to violate this if implemented carelessly — for example, by simply overwriting a two-child node's value with an arbitrary neighbor rather than the strict in-order successor or predecessor.

A few verification strategies are valuable after implementing deletion:

In-order traversal check: An in-order traversal of a valid BST always produces values in strictly ascending order. Running this traversal after each deletion confirms the tree's integrity end-to-end.
Test all structural positions: Deleting the root node (always Case 3 if the tree has more than two levels), deleting internal nodes with one or two children, and deleting leaves should all be tested independently, since each exercises different code paths.
Edge cases: Deleting the only node in the tree (the root with no children), deleting a node from a tree with a single left or right spine (degenerate/skewed tree), and attempting to delete a value not present in the tree (should leave the tree unchanged).

The beauty of the in-order successor/predecessor approach is that it avoids any need to restructure or rebalance the tree. The replacement node slots into the target's position naturally, the subtrees remain connected exactly as before (minus the one node that was physically removed), and the BST property is guaranteed to hold globally — not just locally — because of the mathematical relationship between the in-order successor/predecessor and every other node in the tree.

In summary, BST deletion elegantly reduces a seemingly complex problem to three manageable cases. Cases 1 and 2 are simple pointer adjustments. Case 3 leverages the BST's own ordering structure — the in-order successor or predecessor — to reduce itself to Case 1 or 2. Together these cases cover every possible structural configuration of a BST node, ensuring that deletion can always be performed correctly and efficiently in O(h) time, where h is the height of the tree.

NotesCovers the three cases of node deletion in a BST: removing a leaf, a node with one child, and a node with two children. Explains how the in-order successor or predecessor is used to preserve BST integrity.