Deleting a node from a Binary Search Tree (BST) is where things get messy. If you're adding nodes, you just keep sliding right or left until you hit a NULL. But deletion? That's a different beast because we have to maintain the BST property: everything to the left is smaller, everything to the right is larger. If we just rip a node out of the middle, we leave a hole that could disconnect entire subtrees.

The "Simple" Cases

I usually start by trying to delete a leaf node—something at the very bottom of the tree. Let's imagine we have a tree with 50 at the root, 30 to the left, and 70 to the right. If I want to delete 30, it's easy. I just tell the root that its left child is now NULL and I free the memory. Done.

// My initial thought for a leaf
if (root->left == NULL && root->right == NULL) {
    free(root);
    return NULL;
}

But then I remember that nodes aren't always leaves. What if 30 had a child—say, 20? If I just delete 30, I lose 20 and everything below it. I can't just let 20 vanish into the void. Instead, I have to "promote" the child. If I'm deleting 30, and 30 only has a left child (20), I can just link the root directly to 20. It's like a corporate restructuring; the middle manager gets fired, and the subordinate reports directly to the VP.

The Wall: Two Children

Now, here is where I always hit a wall the first time I implement this. What happens if I try to delete the root (50) and it has both a left subtree and a right subtree? I can't just promote one child, because the other child would have nowhere to go. If I promote 30 to the root, where does 70 go? I can't just hang it off the side without potentially breaking the BST rule.

I tried a naive approach once where I just moved the entire left subtree under the right child, but that creates a weird, skewed tree that kills performance. The real trick is finding a replacement that is "just right"—someone who can step into the role of the deleted node without upsetting the balance of the rest of the tree.

Finding the Successor

If I'm deleting node 50, I need a value that is larger than everything in the left subtree but smaller than everything else in the right subtree. The perfect candidate is the in-order successor: the smallest value in the right subtree.

To find this, I go one step to the right, and then slide as far left as possible. Let's trace it: I'm at 50. I go right to 70. From 70, I go left as far as I can. If there's a 60 there, 60 is my man. Why? Because 60 is guaranteed to be larger than 30 (and everything left of 50) and smaller than 70 (and everything else right of 50).

The process I've found that works best is this: don't actually delete the node with two children. Instead, copy the successor's value into that node, and then delete the successor node itself. Since the successor is the leftmost node of the right subtree, it's guaranteed to either be a leaf or have only one child, which brings us back to the "simple" cases we already solved.

Putting the Logic Together

When I write this out in C, I use recursion because it handles the pointer updates much more cleanly than a while-loop would. I have to return the updated pointer back up the call stack so the parent knows who its new child is.

struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) return root;

    // 1. Navigate to the node
    if (key < root->key) 
        root->left = deleteNode(root->left, key);
    else if (key > root->key) 
        root->right = deleteNode(root->right, key);
    else {
        // 2. We found it! Handle the 3 cases:
        
        // Case A: Leaf or one child
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // Case B: Two children
        // Find the smallest in the right subtree
        struct Node* temp = root->right;
        while (temp->left != NULL) temp = temp->left;

        // Copy successor's data to this node
        root->key = temp->key;

        // Delete the successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

I like this approach because it's recursive. The line root->right = deleteNode(root->right, temp->key); is the "aha!" moment. I'm not writing a whole new function to delete the successor; I'm just calling my existing deleteNode function on the right subtree, knowing that the successor will fall into one of the simpler cases (Case A).

📋 Practical Task

Implementing a BST "Prune" Utility

You are tasked with writing a utility function called prune_value. This function should take a pointer to the root of a BST and an integer value. If the value exists in the tree, it should be deleted using the logic explored in the lesson. If the value does not exist, the tree should remain unchanged.

To verify your implementation, create a BST with the following sequence of insertions: [50, 30, 20, 40, 70, 60, 80]. Then, perform the following deletions in order:

1. Delete 20 (Leaf case)
2. Delete 30 (One-child case)
3. Delete 50 (Two-children case)

After each deletion, print the tree using an in-order traversal. If your logic is correct, the printed output should always be a sorted list of the remaining elements.