BST Deletion — All Three Cases

How it works

1. Search for the key, remembering the parent of each node you pass. If you fall off the tree, the key is absent and nothing changes.
2. Case 1 — leaf: set the parent's pointer to it to null.
3. Case 2 — one child: point the parent straight at that child; the child's whole subtree moves up one level.
4. Case 3 — two children: go right once, then left as far as possible, to find the in-order successor s.
5. Splice s out of its old spot (its right child, if any, takes its place), then put s where the deleted node was, adopting both of its subtrees.
6. If the deleted node was the root, whatever replaces it becomes the new root.

Worked example: three deletions on one tree

This page opens on the tree built from 50, 30, 70, 20, 40, 60, 80, 35, 45, 90: root 50; then 30 and 70; then 20, 40, 60 and 80; and 35 and 45 under 40, 90 under 80.

• Delete 20 (leaf). 20 has no children, so 30's left pointer becomes null. Nothing else moves.
• Delete 80 (one child). 80's only child is 90, so 70's right pointer now points at 90. Every key in 90's subtree was already in 70's right subtree, so it is still larger than 70 and the order holds.
• Delete 30 (two children). Its successor is found by going right once (to 40) and then left as far as possible (to 35). 35 leaves its spot — 40's left pointer takes 35's right child, which is empty — and 35 moves into 30's place with 20 as its left child and 40 as its right.

Replay each case with the Deletion cases buttons above, or delete the root 50 and watch its successor 60 take over the top of the tree.

Why the in-order successor is the right replacement

The node being removed, z, separates two groups of keys: everything in its left subtree is smaller and everything in its right subtree is larger. Its replacement has to be larger than the whole left group and smaller than everything that remains in the right group. The in-order successor — the minimum of the right subtree, the very next key in sorted order — is exactly such a key. The in-order predecessor (the maximum of the left subtree) works just as well by symmetry.

The successor can never have a left child: that child would be smaller and would itself be the minimum. So removing the successor from its old position is always case 1 or case 2, and the two-children case never needs more than one extra step.

Successor or predecessor?

Both are correct. Thomas Hibbard's 1962 deletion algorithm, and textbooks such as CLRS, always use the successor — and that is what the visualizer animates.

Always choosing the same side has a cost, though. Over a long run of random insertions and deletions, the right subtrees keep losing their smallest keys while the left subtrees never do, and the tree drifts out of shape: experiments starting with Eppinger's in 1983 showed the average search path growing well beyond the 1.39·log₂ n of a random tree. Alternating between successor and predecessor, or picking one at random, keeps the tree closer to balanced. Self-balancing trees remove the problem altogether by repairing the shape after every delete.

Implementation details that trip people up

• Copying keys instead of moving nodes. The shortest code copies the successor's key into z and then deletes the successor from the right subtree. That is fine for bare integers, but if nodes carry other data, or outside code holds pointers to nodes, move the successor node itself — as the code below and CLRS's TRANSPLANT do.
• Deleting the root. There is no parent pointer to fix, so the replacement must become the new root. Returning the (possibly new) root from the function handles this cleanly.
• The successor is z's right child. When z.right has no left child, z.right itself is the successor; it keeps its own right subtree and only gains z's left subtree.
• Missing keys. Decide whether deleting an absent key is an error or a no-op; this code treats it as a no-op.
• Recursive deletion returns the new subtree root from every call (node.left = delete(node.left, key)), which removes the parent bookkeeping but uses O(h) stack space.

Deletion in balanced trees

In a plain BST a deletion never restructures anything beyond the three cases. Balanced trees reuse the same cases and then repair the shape: an AVL tree walks back up recomputing heights and may rotate at several levels (O(log n) rotations in the worst case), a red-black tree fixes colours with at most three rotations, and a B-tree borrows a key from a sibling or merges two nodes when one becomes too empty.

Time and space complexity

BST Deletion in Python

def replace(root, parent, old, new):
    """Put `new` where `old` hangs under `parent`; returns the root."""
    if parent is None:
        return new                     # old was the root
    if parent.left is old:
        parent.left = new
    else:
        parent.right = new
    return root


def delete(root, key):
    # z <- search(root, key), remembering z's parent
    parent, z = None, root
    while z is not None and z.key != key:
        parent = z
        z = z.left if key < z.key else z.right
    if z is None:
        return root                            # absent
    if z.left is None and z.right is None:     # case 1: leaf
        root = replace(root, parent, z, None)
    elif z.left is None or z.right is None:    # case 2: one child
        child = z.left if z.left is not None else z.right
        root = replace(root, parent, z, child)
    else:                                      # case 3: two children
        s_parent, s = z, z.right               # successor: right once,
        while s.left is not None:              # then all the way left
            s_parent, s = s, s.left
        if s is not z.right:
            s_parent.left = s.right            # s.right takes s's old place
            s.right = z.right
        s.left = z.left
        root = replace(root, parent, z, s)
    return root

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.
• Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level OrderVisualize inorder, preorder, postorder and level-order tree traversal on one tree: the visit order, the call stack or queue, the code, and when to use each.
• AVL Tree VisualizerAVL tree visualizer: insert and delete keys, watch heights and balance factors update and LL, RR, LR, RL rotations keep every operation O(log n).
• AVL Rotations — LL, RR, LR, RLAVL tree rotations explained: spot the LL, RR, LR and RL cases from balance factors and fix each with a single or double rotation — animated step by step.
• B-Tree Deletion — Borrow & MergeB-tree deletion step by step: remove from a leaf or swap in the predecessor, then fix underflow by borrowing from a sibling or merging nodes. Animated.
• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.