BST Insert, Search and Delete, in depth: the invariant, iterative code, all three delete cases traced by hand, height analysis and testing

The invariant, and why everything costs O(h)

Each node holds a key, an optional value, and pointers to a left and a right child. The BST invariant: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. Note subtree, not just child. A tree where each child is correctly ordered relative to its parent can still be invalid if a deep descendant violates an ancestor's bound, which is the classic bug that BST validation checks for.

At every node one comparison rules out an entire subtree, so search, insert and delete each follow a single root-to-leaf path with constant work per level. Their cost is O(h), the tree's height, which for n keys lies between about log2(n), perfectly balanced, and n, a chain. BST performance is entirely about which end you are at.

A second consequence: an in-order traversal (left, node, right) visits keys in sorted order, which gives range queries, floor, ceiling and sorted iteration for free.

Search, floor and insert

Search starts at the root and, at each node, either finds the key, goes left because the key is smaller, or goes right because it is larger. Reaching an empty pointer proves the key is absent, because that empty pointer is exactly where the key would have to be.

Insert is the same descent. The empty pointer it reaches is the unique place where the new key preserves the invariant, so the new node is attached there as a leaf. Inserts never restructure a plain BST, which is why its shape is determined entirely by insertion order. Decide what equal keys mean: the code below treats the tree as a map and overwrites the value; a multiset can store a count per node instead.

class Node:
    __slots__ = ("key", "val", "left", "right")
    def __init__(self, key, val):
        self.key, self.val, self.left, self.right = key, val, None, None

def search(root, key):
    node = root
    while node is not None:
        if key == node.key:
            return node.val
        node = node.left if key < node.key else node.right
    return None                                   # fell off the tree: absent

def insert(root, key, val):
    """Returns the (possibly new) root. Equal keys overwrite: the tree is a map."""
    if root is None:
        return Node(key, val)
    node = root
    while True:
        if key == node.key:
            node.val = val
            return root
        side = "left" if key < node.key else "right"
        child = getattr(node, side)
        if child is None:
            setattr(node, side, Node(key, val))   # new keys always become leaves
            return root
        node = child

def floor(root, key):
    """Largest key <= key, or None. Same descent, remembering the best candidate."""
    best, node = None, root
    while node is not None:
        if node.key == key:
            return node.key
        if node.key < key:
            best, node = node.key, node.right
        else:
            node = node.left
    return best

floor shows the general pattern for ordered queries: walk the same path, remembering the best candidate seen. ceiling is its mirror image, and a range query is an in-order walk that skips subtrees lying wholly outside the range.

Delete: the three cases

Deletion is the only operation that has to repair structure, and it splits into three cases by the number of children the target node has.

1. No children (a leaf). Set the parent's pointer to it to empty. Nothing else changes.
2. One child. Splice the child into the node's place. Every key in that child's subtree was already on the correct side of every ancestor, because it was inside the deleted node's subtree, so the invariant holds.
3. Two children. You cannot splice two subtrees into one pointer. Instead, find the node's in-order successor, the smallest key in its right subtree, reached by going right once and then left as far as possible. Copy the successor's key and value into the node, then delete the successor from its old position. The successor is larger than everything on the left and smaller than everything else on the right, so it is a valid replacement. And because it is leftmost, it has no left child, so removing it is always case 1 or case 2. The in-order predecessor, the largest key on the left, works symmetrically.

def delete(root, key):
    """Returns (new_root, deleted?). Iterative: no recursion-depth limit on tall trees."""
    parent, node = None, root
    while node is not None and node.key != key:
        parent, node = node, (node.left if key < node.key else node.right)
    if node is None:
        return root, False

    if node.left is not None and node.right is not None:
        # Case 3: two children. The in-order successor is the leftmost node of the right
        # subtree; it has no left child, so removing it is case 1 or case 2.
        succ_parent, succ = node, node.right
        while succ.left is not None:
            succ_parent, succ = succ, succ.left
        node.key, node.val = succ.key, succ.val
        parent, node = succ_parent, succ

    # Cases 1 and 2: zero or one child. Splice the child (possibly None) into the parent.
    child = node.left if node.left is not None else node.right
    if parent is None:
        return child, True
    if parent.left is node:
        parent.left = child
    else:
        parent.right = child
    return root, True

The code reduces case 3 to cases 1 and 2 by retargeting parent and node at the successor, so there is only one splice. One subtle case: when the successor is the node's immediate right child, succ_parent is the node itself and the splice correctly updates its right pointer.

Worked example, traced by hand

Insert 50, 30, 70, 20, 40, 60, 80, 35, 45, 65 into an empty tree. 50 is the root; 30 and 70 become its children; 20 and 40 go under 30, 60 and 80 under 70. 35 and 45 go left and right of 40, and 65 right of 60. The tree has four levels and the in-order walk reads 20, 30, 35, 40, 45, 50, 60, 65, 70, 80.

Delete 20. Search reaches 20 under 30; it is a leaf, so 30's left pointer becomes empty.

Delete 60. 60 has only a right child, 65. Splice 65 into 70's left pointer. 65 is larger than 50 and smaller than 70, as it must be, because it was already in that position's subtree.

Delete 30. 30 now has no left child but still has a right child, 40, so this is case 2 again: 40 takes 30's place under 50. To see case 3, delete 50 next. Its successor is the leftmost node of its right subtree: go right to 70, then left to 65, which has no left child. Copy 65 into the root, then splice 65's empty right pointer into 70's left. The root is now 65, with 40 on the left and 70 on the right, and the in-order walk still reads in sorted order.

Tracing deletes on paper and checking the in-order sequence after each is the fastest way to debug your own implementation.

Height: the number that actually matters

Insert the same ten keys in sorted order, 20, 30, 35 and so on, and every key goes to the right of the previous one. The tree is a linked list of height 10, and every operation is O(n). This is not a corner case: sorted or nearly sorted input is extremely common in practice, from timestamps and auto-increment IDs to data loaded from a sorted file.

For keys inserted in uniformly random order the picture is good. The average depth of a node is about 2 ln n, roughly 1.39 log2 n, and the expected height is also logarithmic; Devroye showed it is about 4.31 ln n for large n. A million random keys give an average search path of about 28 comparisons.

Deletion complicates the analysis. Always replacing with the successor removes keys from the right subtrees preferentially, and experiments going back to Eppinger in 1983 found that long sequences of random insert and delete pairs make such trees measurably less balanced than random ones. Alternating between successor and predecessor, or choosing randomly, reduces the effect. The real answer, though, is that a production tree should not rely on input order at all.

From BST to balanced trees

Balanced trees keep all three operations described here and add a repair step after insert and delete. AVL trees store each node's height and rotate when the two subtrees differ by more than one, which is a property you can check with the balanced tree check. Red-black trees colour nodes and limit the longest path to twice the shortest. A rotation is a local pointer change that preserves the in-order sequence, so it never breaks the BST invariant; it only changes the shape.

This is why the plain BST is worth knowing in detail. Most production ordered maps, such as Java's TreeMap and typical C++ std::map implementations, are red-black trees, and when you debug or extend one, the search path, the leaf insert and the successor delete are exactly what you are reading.

Testing a tree properly

Hand-picked unit tests miss the cases that matter: deleting the root, deleting a node whose successor is its direct child, deleting from a one-node tree, deleting a key twice. A randomised test against a trusted reference finds all of them in seconds. Run thousands of random operations on both your tree and a dictionary, compare every answer, and check the invariant at the end with an in-order walk.

import random

def keys_in_order(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.key)
        node = node.right
    return out

def check(root):
    ks = keys_in_order(root)
    assert all(a < b for a, b in zip(ks, ks[1:])), "BST invariant broken"
    return ks

def fuzz(seed, ops=20_000, universe=300):
    rng, root, ref = random.Random(seed), None, {}
    for _ in range(ops):
        k = rng.randrange(universe)
        r = rng.random()
        if r < 0.45:
            root = insert(root, k, k * 10); ref[k] = k * 10
        elif r < 0.80:
            root, gone = delete(root, k)
            assert gone == (k in ref); ref.pop(k, None)
        else:
            assert search(root, k) == ref.get(k)
    assert check(root) == sorted(ref)

for seed in range(50):
    fuzz(seed)

A small key universe matters: with 300 possible keys, deletes hit present keys often, so every case gets exercised. Use a fixed list of seeds so failures are reproducible, and shrink a failing seed's operation list to the shortest sequence that still fails.

Failure modes in real code

• Recursion depth. Recursive insert and delete are elegant, but on a degenerate tree the recursion is n deep. CPython's default recursion limit is 1,000, so sorted input of a few thousand keys crashes. Write the operations iteratively, as above.
• Stale handles after a two-child delete. Copying the successor's key into the node means the object that used to hold the successor's key disappears. If callers kept references to nodes, as iterators or intrusive indexes do, splice the successor node into the deleted node's place instead of copying data.
• Mutable or inconsistent keys. Changing a key's sort-relevant fields after insertion, or a comparison that is not a strict total order, such as floats with NaN, silently breaks the invariant. Searches then miss keys that are present.
• Duplicate-key policy drift. Inserting equal keys to the left in one place and searching right in another loses data.
• Cache behaviour. Each level is a pointer dereference to a node that may be anywhere in memory. For large in-memory or on-disk data, wider nodes such as B-trees win because one cache line or disk page resolves many comparisons.
• Concurrency. A plain BST has no thread safety. A single lock is simple and serialises everything; lock-free and fine-grained variants are research-grade code, so prefer a library concurrent map.

What to do next

1. Implement search, insert and the iterative delete above, and run the randomised test until it passes for 50 seeds.
2. Trace the worked example on paper, including deleting the root, and compare with your code's in-order output after each step.
3. Insert 10,000 sorted keys and 10,000 shuffled keys, and measure the height of each tree.
4. Add floor, ceiling and a range query, and extend the randomised test to cover them.
5. Implement left and right rotations, then AVL rebalancing on top of your insert.
6. In production, use your platform's balanced ordered map rather than a hand-written plain BST.