Why is a binary search tree O(log n) in theory and O(n) on real data?

The Answer

• A BST lookup costs the height of the tree, not log n. Those are the same number only when the tree is balanced.
• Nothing in a plain BST maintains balance. The shape is decided entirely by the order the keys arrive in.
• Ascending or descending input is the worst case: every key is larger than everything before it, so it becomes a right child. Height n. You have built a linked list that costs two pointers per node.
• Sorted input is not exotic — it is what you get from a database ORDER BY, an auto-increment id, or a timestamp.
• TreeMap is a red-black tree: it rotates on insert to keep height within 2·log₂(n+1), so it cannot degenerate whatever order you feed it.
• The lesson is not "avoid trees". It is that the O(log n) in the textbook is conditional, and the condition has a name: balance.

Understand It

The cost is the height, and the height is up to the input

A lookup walks from the root to at most a leaf, one comparison per level. So the cost is the height — full stop. Everything about "O(log n)" is an assumption that the height is log n, which is true when each level is full and false otherwise.

insert(root, key):
    if root is empty:  return new Node(key)

    if key < root.key:  root.left  ← insert(root.left, key)
    if key > root.key:  root.right ← insert(root.right, key)

    return root                  # note what is MISSING: no rotation,
                                 # no height check, no rebalancing.
                                 # The shape is whatever the input makes it.

That is the whole insert, and the comment is the point. There is no step in which the tree considers its own shape.

Feed it keys in ascending order and each new key, being larger than every existing one, walks right until it falls off the bottom:

insert 1, 2, 3, 4 into an empty BST:

    1              1              1              1
                    \              \              \
                     2              2              2
                                     \              \
                                      3              3
                                                      \
                                                       4

    height 1       height 2       height 3       height 4

Measured, on the two input orders

for (int n : new int[] {1000, 2000, 4000}) {
    int sortedHeight = height(treeOf(ascending(n)));
    int shuffledHeight = height(treeOf(shuffled(n)));
    System.out.printf("n=%-5d height: ascending input %5d   shuffled input %3d   log2(n)=%.0f%n",
        n, sortedHeight, shuffledHeight, Math.log(n) / Math.log(2));
}

n=1000  height: ascending input  1000   shuffled input  25   log2(n)=10
n=2000  height: ascending input  2000   shuffled input  30   log2(n)=11
n=4000  height: ascending input  4000   shuffled input  29   log2(n)=12

Three things worth reading off that:

• Ascending input gives height exactly n. Not "worse than log n" — literally one node per level. Every lookup is a linear scan.
• Shuffled input gives 25 to 30, against a log₂(n) of 10 to 12. Random insertion gives expected height about 4.3 · ln n, which is a constant multiple of log n — so it is O(log n), just with a factor of two or three.
• Shuffled height barely grows: 25 → 30 → 29 while n quadruples. That non-monotonic 30 → 29 is the randomness; the trend is logarithmic.

So a plain BST is fine on random data and catastrophic on ordered data, and nothing in its code distinguishes the two cases.

What a red-black tree does instead

TreeMap measures nothing about the input. It performs rotations and recolours on every insert to preserve invariants that bound the height at 2·log₂(n+1). Give it the input that destroyed the naive tree:

for (int n : new int[] {1000, 2000, 4000}) {
    TreeMap<CountedKey, Integer> map = new TreeMap<>();
    for (int i = 0; i < n; i++) map.put(new CountedKey(i), i);   // ascending!

    comparisons = 0;
    for (int i = 0; i < n; i++) map.get(new CountedKey(i));

    System.out.printf("n=%-5d TreeMap: %,7d comparisons for %,5d lookups  = %.1f each (log2 n = %.1f)%n",
        n, comparisons, n, (double) comparisons / n, Math.log(n) / Math.log(2));
}

n=1000  TreeMap:   9,406 comparisons for 1,000 lookups  = 9.4 each (log2 n = 10.0)
n=2000  TreeMap:  20,800 comparisons for 2,000 lookups  = 10.4 each (log2 n = 11.0)
n=4000  TreeMap:  45,586 comparisons for 4,000 lookups  = 11.4 each (log2 n = 12.0)

9.4, 10.4, 11.4 comparisons per lookup against a log₂ n of 10, 11, 12. It tracks the logarithm almost exactly, on the same ascending keys that gave the naive tree height 4,000. Quadrupling n adds two comparisons per lookup.

Rebalancing is not free — each insert may rotate — but rotations are O(1) and at most a couple per insert, so insert stays O(log n) while the guarantee becomes unconditional.

The second reason degeneration hurts

A degenerate tree is not only slow. Recursive traversal of it is a recursion whose depth is n:

walk(node):
    if node is null: return
    walk(node.left)       # depth = the tree's HEIGHT
    visit(node)
    walk(node.right)

On a balanced tree that is log n frames — about 12 at n = 4,000. On the degenerate tree it is 4,000 frames, and at a few tens of thousands of ascending keys a recursive walk throws StackOverflowError. The same input that made lookups linear also turned a safe traversal into a crash.

Reference

What to use, and the honest reason:

If you do write your own tree, the things to get right:

// 1. Insert iteratively, so the tree's height does not become your stack depth.
static Node insert(Node root, int key) {
    if (root == null) return new Node(key);
    Node current = root;
    while (true) {
        if (key < current.key) {
            if (current.left == null) { current.left = new Node(key); return root; }
            current = current.left;
        } else if (key > current.key) {
            if (current.right == null) { current.right = new Node(key); return root; }
            current = current.right;
        } else {
            return root;                       // already present
        }
    }
}

// 2. Traverse with an explicit stack for the same reason.
static void inorder(Node root, Consumer<Node> visit) {
    Deque<Node> stack = new ArrayDeque<>();
    Node current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) { stack.push(current); current = current.left; }
        current = stack.pop();
        visit.accept(current);
        current = current.right;
    }
}

Checking whether a tree you have is actually balanced:

// Height alone is not the test — compare it against the ideal.
int ideal = (int) Math.ceil(Math.log(size + 1) / Math.log(2));
// A red-black tree stays within 2x ideal. Much past that and it is degenerating.

Do not "fix" a degenerate tree by shuffling the input. It works, and it means your data structure's performance depends on nobody ever handing it ordered data again. Use a balanced tree.

Scenarios

A cache keyed by auto-increment id, in a hand-rolled BST. Ids arrive ascending forever, so the tree is a linked list from the first insert and never recovers. Lookups degrade linearly with the number of rows loaded, and the symptom is a report that gets slower every week with no code change.

Loading reference data with ORDER BY name. The ORDER BY was added to make a log readable. It also made the insert order sorted, which turned the tree it feeds into a list. This is the most common accidental version, because the two lines are in different files.

Timestamps as keys. Monotonic by nature. Any hand-written BST keyed by time degenerates by construction — there is no unlucky case, it is the only case.

Where a plain BST is genuinely fine. Keys that are hashes, UUIDs, or otherwise arrive in random order, with a known bound on n. Expected height is about 4.3 · ln n, which the measurement above confirms. Worth stating as an assumption in a comment, because the next person will feed it sorted data.

Interviewer's Next Move

1. "Why is sorted input the worst case rather than the best?" Because each key is larger than every key already present, so the insert walk always goes right and the new node always becomes a leaf one level deeper. Height grows by one per insert. Sortedness helps searching a sorted array and destroys building an unbalanced tree.

2. "How does a red-black tree keep the height down?" Invariants on node colours — no red node has a red child, and every path from a node to its descendant leaves contains the same number of black nodes. Together those bound the longest path at twice the shortest, so height stays within 2·log₂(n+1). Insert restores them with O(1) rotations and recolours.

3. "Is TreeMap ever worse than HashMap?" For plain key lookup, yes — O(log n) against O(1) average, and it has to call compareTo rather than hashing. You pay that for ordering: firstKey, lastKey, headMap, subMap and iteration in key order, none of which a HashMap can do at any price.

4. "Your BST works in tests and is slow in production. How do you diagnose it?" Measure the height against log₂(size). A ratio near 1–3 is healthy; a ratio near n means it has degenerated, and the next question is what order the keys arrive in. It is a shape problem, not a code problem, so profiling shows only that lookups are slow.

5. "Why does a degenerate tree also break recursive traversal?" Because traversal depth equals the tree's height. Balanced, that is log n — a dozen frames. Degenerate, it is n, and past roughly twenty thousand keys a recursive walk overflows the stack. One bad input order causes both failures.

Check Yourself

Inserting 4,000 ascending keys gave a height of exactly 4,000. Why exactly, rather than approximately? Because every key is larger than all its predecessors, so it becomes the right child of the deepest node on the rightmost path — adding precisely one level per insert. There is no branching at all.

Shuffled input gave height 29 where log₂(4000) is 12. Is that still O(log n)? Yes. Expected height for random insertion is about 4.3 · ln n, a constant multiple of log n, and big-O ignores constants. The evidence is the growth: height barely moved while n quadrupled.

TreeMap used 11.4 comparisons per lookup at n = 4,000 on ascending keys. What would a naive BST have used on the same input? About 2,000 — half the height of 4,000, on average. The red-black rotations are the entire difference, and they are why the guarantee holds regardless of input order.