BST Deletion — Three Cases of Node Removal

BST Deletion: Three Cases

Deleting a node from a BST is more complex than insertion because you must maintain the BST property while removing a node that may have subtrees attached to it.

Case 1: Deleting a Leaf Node

The simplest case. The node has no children, so you simply remove it by setting the parent's pointer to null.

Before:     After deleting 4:
    5           5
   / \         / \
  3   7       3   7
 / \           \
1   4           1  (was leaf, just removed)

Case 2: Deleting a Node with One Child

Replace the node with its only child. The child takes the position of the deleted node.

Before:     After deleting 3 (has one child 1):
    5           5
   / \         / \
  3   7       1   7
 /
1

Case 3: Deleting a Node with Two Children

This is the complex case. You find the in-order successor (the smallest node in the right subtree), copy its value to the node being deleted, then recursively delete the in-order successor.

Before:     After deleting 5 (in-order successor is 6):
    5           6
   / \         / \
  3   8       3   8
     / \         \
    6   9         9

Why In-Order Successor?

The in-order successor is the smallest value that is still greater than all values in the left subtree. Replacing the deleted node with this value preserves the BST property. Alternatively, you could use the in-order predecessor (largest in the left subtree) — both approaches are valid.

Time Complexity

• Average: O(log n) — finding the node and successor both take O(h) time
• Worst: O(n) — in a degenerate tree where height equals the number of nodes