Unit 2 · Lesson 620 minAcademic review pending

Removing a node without breaking the rule

Deleting a leaf is trivial. Deleting a node with two children is the hardest thing in this unit — and it has one clean answer: borrow the next value in sorted order.

Choose explanation

After this lesson

You should be able to

Identify which of the three deletion cases applies to a given node.
Explain why the inorder successor is the safe replacement for a two-child node.
Write a recursive BST deletion function.

Try it before you read

Try it live

bst.c0 node(s)

Empty tree — insert a value to begin.

Three cases, in order of difficulty

If the node to delete is a leaf, just remove it — nothing else in the tree references it. If it has exactly one child, the node is a single link in a chain; bypass it by connecting its parent directly to its one child. Neither case can break the BST property, because neither moves any other value out of place.

Two children is the hard case, because you cannot simply promote either child — the left child's whole subtree is smaller than the right child's whole subtree, and both need a single node to take the deleted one's place in sorted order.

The inorder successor, and why it always works

The inorder successor of a node is the next value after it in sorted order — from Lesson 3, that is the leftmost node of its right subtree. It is bigger than everything in the deleted node's left subtree, and smaller than everything else in the right subtree, because it is the smallest thing the right subtree has.

Copy the successor's value into the node being deleted, then delete the successor from its original spot in the right subtree. That second deletion is guaranteed to be a leaf or one-child case — the leftmost node of any subtree can never have a left child, or it would not be the leftmost.

Three branches, one for each case

struct Node *find_min(struct Node *node)
{
    while (node->left != NULL)
        node = node->left;
    return node;
}

struct Node *delete_node(struct Node *node, int value)
{
    if (node == NULL) return NULL;

    if (value < node->data) {
        node->left = delete_node(node->left, value);
    } else if (value > node->data) {
        node->right = delete_node(node->right, value);
    } else {
        if (node->left == NULL)  return node->right;   /* leaf or one child */
        if (node->right == NULL) return node->left;    /* one child        */

        struct Node *successor = find_min(node->right); /* two children */
        node->data = successor->data;
        node->right = delete_node(node->right, successor->data);
    }
    return node;
}

Try it yourself

Build the tree from Lesson 5's practice (45, 20, 70, 10, 30, 60, 80), then delete 20 (two children), 10 (leaf), and 70 (two children) in that order, predicting each result before clicking Delete.

Need a hint?

20's inorder successor is 30 — the leftmost node of its right subtree.

Check the worked solution

Deleting 20 copies 30 into its place and removes the original 30, which was itself a leaf — a two-child case that immediately resolves into the easiest case for its second step. Deleting 10 is a plain leaf removal. Deleting 70 copies 80 into its place. Watch the status message after each click name the exact case — that message is the same reasoning this lesson's code performs.

Quick check

When deleting a node with two children, why is it always safe to replace it with its inorder successor?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

BST Operations- Deletion

Maps to course outcomes CO1, CO4.