CodeLudo 🔥 Daily Guides

The Same Seven Numbers, Two Trees: Why Insert Order Decides Lookup Cost

✓ numbers produced by the code on this page · Published 2026-08-19

A binary search tree is usually introduced with a tidy picture: a root, two children, everything smaller on the left, everything larger on the right. The picture is correct, and it hides the most important thing about the structure.

A binary search tree has no say in its own shape. It stores what it is given, in the order it is given, and that order decides what the tree costs to use for the rest of its life. The same seven numbers can be a three-level tree or a seven-level one. The data did not change. The insert code did not change. Only the sequence.

Build one, then break it

Insert the values in any order you like. The tree redraws after each one.

Build a search tree same values, a different order, a different cost

A binary search tree holds these 7 values: 1, 2, 3, 4, 5, 6, 7. Each new value starts at the root and moves left or right until it finds an empty spot, so the ORDER they arrive in decides the shape of the tree — and the contents never change.

Inserting them in sorted order gives a tree 7 levels deep: every node has one child and no left children at all, which is a linked list. Inserting 4, 2, 6, 1, 3, 5, 7 gives one 3 levels deep. Same values, same insert code, but finding something costs up to 7 comparisons in the first tree and at most 3 in the second — 2.3× worse at its worst, on every lookup for the rest of the tree's life, and the gap widens sharply as the tree grows. Building them costs 21 comparisons versus 10.

Try 1 through 7 in order first. Then press Reset and start from 4 instead. The values are identical in both trees — only the sequence you clicked them in is different.

Two things are worth noticing before reading on.

The in-order row never changes. Whatever shape you produce, reading the tree left to right gives the values in sorted order every single time. That is what the structure is for — and it is also why a badly shaped tree gets away with it. Shape does not buy correctness. It buys speed.

Sorted input is the worst possible input. Insert 1, then 2, then 3, and each value is larger than everything already there, so each one goes right, forever. You get a staircase: a linked list with tree-shaped code wrapped around it. The most natural way to load data — in whatever order it already happens to be in, which is very often sorted — is the one that destroys the tree.

Why the shape moves at all

Insertion never reorganises anything. It walks down from the root, going left when the new value is smaller and right when it is not, and hangs the new node on the first empty spot it finds. Where a node lands is decided entirely by which nodes are already there.

So the first value inserted becomes the root permanently, and everything after it is filed relative to that choice. Insert 4 first and roughly half the remaining values go left, half go right. Insert 1 first and every remaining value goes right.

Here is that walk with the cost counted. One comparison means one existing node visited — the same unit a lookup is measured in later, which is what makes the two numbers comparable.

python 
def insert(root, value):
    """Insert value; return (root, comparisons). One comparison = one existing node visited."""
    node = {"value": value, "left": None, "right": None}
    if root is None:
        return node, 0
    cur, comparisons = root, 0
    while True:
        comparisons += 1
        if value < cur["value"]:
            if cur["left"] is None:
                cur["left"] = node
                return root, comparisons
            cur = cur["left"]
        else:
            if cur["right"] is None:
                cur["right"] = node
                return root, comparisons
            cur = cur["right"]


def build(order):
    root, total = None, 0
    for value in order:
        root, spent = insert(root, value)
        total += spent
    return root, total


def height(root):
    levels, stack = 0, [(root, 1)]
    while stack:
        node, depth = stack.pop()
        if node is None:
            continue
        levels = max(levels, depth)
        stack.append((node["left"], depth + 1))
        stack.append((node["right"], depth + 1))
    return levels


def balanced_order(values):
    """Medians first, breadth-first: the order that builds the shallowest possible tree."""
    order, queue = [], [(0, len(values) - 1)]
    while queue:
        lo, hi = queue.pop(0)
        if lo > hi:
            continue
        mid = (lo + hi) // 2
        order.append(values[mid])
        queue.append((lo, mid - 1))
        queue.append((mid + 1, hi))
    return order


values = list(range(1, 8))

for name, order in [("sorted", values), ("medians", balanced_order(values))]:
    root, comparisons = build(order)
    print(f"{name}: insert {order}")
    print(f"  height {height(root)} levels, {comparisons} comparisons to build")
Output 
sorted: insert [1, 2, 3, 4, 5, 6, 7]
  height 7 levels, 21 comparisons to build
medians: insert [4, 2, 6, 1, 3, 5, 7]
  height 3 levels, 10 comparisons to build

Edit values to list(range(1, 16)) and run it again to watch the gap widen.

Seven levels against three is the figure the widget reports, and it is a worst-case number: the deepest node takes seven comparisons to reach instead of three. That is the right thing to say about one unlucky lookup and the wrong thing to say about the tree as a whole, because most nodes are not the deepest one.

What the shape actually costs

The honest measure is the total cost of finding every key once. At seven values it is a smaller ratio than the worst case suggests. As the tree grows it becomes a far larger one.

python 
def insert(root, value):
    node = {"value": value, "left": None, "right": None}
    if root is None:
        return node
    cur = root
    while True:
        if value < cur["value"]:
            if cur["left"] is None:
                cur["left"] = node
                return root
            cur = cur["left"]
        else:
            if cur["right"] is None:
                cur["right"] = node
                return root
            cur = cur["right"]


def lookup_cost(root, value):
    """Comparisons needed to FIND value - the cost this tree charges forever after."""
    cur, steps = root, 0
    while cur is not None:
        steps += 1
        if value == cur["value"]:
            return steps
        cur = cur["left"] if value < cur["value"] else cur["right"]
    return steps


def balanced_order(values):
    order, queue = [], [(0, len(values) - 1)]
    while queue:
        lo, hi = queue.pop(0)
        if lo > hi:
            continue
        mid = (lo + hi) // 2
        order.append(values[mid])
        queue.append((lo, mid - 1))
        queue.append((mid + 1, hi))
    return order


print(f"{'values':>7}  {'sorted order':>13}  {'medians first':>14}  {'ratio':>6}")
for n in (7, 63, 1023):
    values = list(range(1, n + 1))
    results = []
    for order in (values, balanced_order(values)):
        root = None
        for value in order:
            root = insert(root, value)
        results.append(sum(lookup_cost(root, v) for v in values))
    slow, fast = results
    print(f"{n:>7}  {slow:>13,}  {fast:>14,}  {slow / fast:>5.1f}x")
Output 
 values   sorted order   medians first   ratio
      7             28              17    1.6x
     63          2,016             321    6.3x
   1023        523,776           9,217   56.8x

At seven values the badly built tree costs 1.6 times as much in total. At 1023 it costs nearly fifty-seven times as much, and the gap keeps widening — because these are not two similar structures with different constants. They are different complexity classes wearing the same type name. A balanced tree costs about log2(n) per lookup; a chain costs about n. At 1023 values that is 10 against 1023, and the table’s ratio is below 100 only because the average node in a chain sits halfway down it rather than at the end.

That is the practical shape of the danger. A merely lopsided tree is a small tax. A tree built from sorted input has quietly stopped being a tree, while the code around it still compiles, still returns correct answers, and still passes its tests — on small inputs.

What real systems do about it

Nothing on this page fixes the problem; it only makes it visible. The fixes have names worth knowing, and each is a different answer to the question who is responsible for the shape:

How those work is a different article. This one exists to establish why they are needed at all, which is the part that usually gets skipped.

What this page simplifies