Delete a Node in a BST

Delete a Node in a BST is the classic test of whether you really understand binary search trees. Searching and inserting are easy; deletion is where the ordering invariant fights back — especially when the node you remove has two children.

The slow way first

A tempting hack: collect every value with an in-order traversal, drop the key, and rebuild a fresh BST. That works but it is O(n) time and space and throws away the structure you already have. It also rebalances the tree in ways the problem does not ask for. We want a surgical edit that touches only the path to the key.

The question to ask: once I have found the node, how do I remove it without breaking the left-smaller / right-larger rule?

The idea: find it, then handle three cases

First search down the tree like a normal lookup: go left when key is smaller, right when it is larger, until the value matches. Once found, there are three cases:

• No children — just return None; the node vanishes.
• One child — return that child; it slides up to take the node's place.
• Two children — the hard case. Replace the node's value with its in-order successor (the smallest key in the right subtree), then delete that successor. Since the successor is a minimum, it has no left child, so deleting it falls into one of the two easy cases.

The reason the successor works: it is larger than everything in the left subtree and smaller than everything else in the right subtree, so dropping it into the deleted node's slot keeps the BST ordering perfectly intact.

Walk through it

Step through the animation. The cur pointer searches down and lands on 5. Because 5 has two children, we dive into its right child 8 and walk left to the minimum — 6, the in-order successor. We copy 6 up into the node, then recurse to delete the original 6, which is a childless leaf and simply disappears. The final tree is a valid BST with 5 gone.

Pseudocode

delete(node, key):
    if node is None: return None
    if key < node.val:  node.left  = delete(node.left, key)
    elif key > node.val: node.right = delete(node.right, key)
    else:                                  # found the node
        if node.left is None:  return node.right     # 0 or 1 child
        if node.right is None: return node.left      # 1 child
        succ = node.right                  # two children
        while succ.left: succ = succ.left  # min of right subtree
        node.val = succ.val                # copy successor up
        node.right = delete(node.right, succ.val)  # delete successor
    return node

The Python solution

def delete_node(root, key):
    if root is None:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None: return root.right
        if root.right is None: return root.left
        succ = root.right
        while succ.left: succ = succ.left
        root.val = succ.val
        root.right = delete_node(root.right, succ.val)
    return root

• Lines 4-7 are the search: recurse left or right and reattach the returned subtree, so a deletion deeper down is wired back into the tree.
• Line 9 handles the zero-or-left-missing case: returning root.right works whether the right child exists or is itself None.
• Line 10 handles the only-left-child case.
• Lines 11-12 find the in-order successor — start at the right child and walk left as far as possible.
• Line 13 copies the successor value up into the current node.
• Line 14 deletes the successor from the right subtree. It has no left child, so this recursion terminates in an easy case.

Complexity

The work follows a single root-to-leaf path plus a left-spine walk, so it is proportional to the tree height h. Space is O(h) for the recursion stack — O(log n) when balanced, O(n) when skewed.

When this pattern shows up

Practice