Deleting from a BST

Deletion is the trickiest operation. We need to remove a node while keeping the BST property intact. There are three cases to handle.

Three Cases

1. No children (leaf node): Just remove it
2. One child: Replace with the child
3. Two children: Replace with in-order successor

Let’s see each case:

Case 1: Leaf Node

The easiest case. Just remove it:

Before:         After:
    50             50
   /  \           /  \
  30   70        30   70
 / \  / \       / \  /
20 40 60 80    20 40 60

Deleting 80: it has no children, so we just set its parent’s right pointer to null.

Case 2: One Child

Replace the node with its child:

Before:         After:
    50             50
   /  \           /  \
  30   70        30   70
 / \  / \       / \  /
20 40 60 80    20 40 60

Deleting 80: it has one child (null), so we replace 80 with null. Actually, let’s use a better example:

Before:         After:
    50             50
   /  \           /  \
  30   70        30   70
 / \  /         / \  /
20 40 60       20 40 60
     \
     65

Deleting 60: it has one child (65), so we replace 60 with 65.

Case 3: Two Children

This is the complex case. We need to find the in-order successor and replace the node with it.

In-order successor: The smallest value in the right subtree.

The Algorithm

Here’s the complete deletion algorithm:

Why In-Order Successor?

The in-order successor maintains the BST property. It’s:

• Larger than all left subtree values (it’s from right subtree)
• Smaller than all other right subtree values (it’s the minimum)

This makes it the perfect replacement.

Step-by-Step Example

Delete 50 from this tree:

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

1. Find 50 (it’s the root)
2. It has two children, so find successor
3. Successor is 60 (min in right subtree)
4. Replace 50 with 60
5. Delete original 60 (it’s a leaf, easy)

Result:

    60
   /  \
  30   70
 / \    \
20 40   80

Alternative: In-Order Predecessor

You can also use the in-order predecessor (max in left subtree). Both work:

              // Find minimum in right subtree
function findMin(node) {
while (node.left !== null) {
  node = node.left;
}
return node;
}

// Use successor
const successor = findMin(root.right);
root.value = successor.value;
root.right = deleteNode(root.right, successor.value);
            

              // Find maximum in left subtree
function findMax(node) {
while (node.right !== null) {
  node = node.right;
}
return node;
}

// Use predecessor
const predecessor = findMax(root.left);
root.value = predecessor.value;
root.left = deleteNode(root.left, predecessor.value);
            

Both maintain the BST property. Successor is more common.

Time Complexity

• Average case: O(log n) - find node + find successor
• Worst case: O(n) - if tree is unbalanced

Common Mistakes

1. Forgetting to update parent: Must update parent’s pointer
2. Wrong successor: Must find min in right subtree, not max
3. Not handling all cases: Must check for 0, 1, and 2 children
4. Memory leaks: In languages without GC, free the deleted node

What’s Next?

Deletion is complex, but you’ve got it. Now let’s learn different ways to traverse a BST and visit all nodes.