Why search trees need to stay balanced

Trees Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

Inserting sorted keys into a plain search tree. What does this print?

Python 3.13
def height_after_inserts(keys: list[int]) -> int:
    tree: dict[int, list[int | None]] = {}
    root: int | None = None
    best = 0
    for k in keys:
        if root is None:
            root, tree[k], best = k, [None, None], 1
            continue
        cur, d = root, 1
        while True:
            side = 0 if k < cur else 1
            nxt = tree[cur][side]
            d += 1
            if nxt is None:
                tree[cur][side] = k
                tree[k] = [None, None]
                break
            cur = nxt
        best = max(best, d)
    return best

chain = height_after_inserts(list(range(10)))
bushy = height_after_inserts([5, 2, 8, 1, 3, 7, 9, 0, 4, 6])
print(chain, bushy)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 10 4

Right: sorted inserts make a chain of 10, a good order gives height 4.

The same ten keys give very different heights depending on insert order, which is why balancing matters.

Why not the others?
  • B 4 4. Sorted inserts always go right, building a chain.
  • C 10 10. The mixed order spreads keys on both sides.

30-second answer

Search, insert and delete in a search tree cost O(h), the height. A balanced tree has h about log₂ n, so the operations are O(log n). Insert sorted keys into a plain search tree and it degenerates into a chain with h = n, so every operation becomes O(n). Self-balancing trees (AVL, red-black) rotate nodes to keep h = O(log n).

Practise saying it · 45 s. No recording, just a timer

Explain why balance matters in search trees.

Say your answer out loud, then check which of these points you covered:

  • Cost is O(height)
  • Sorted inserts make a chain
  • Rotations keep O(log n)

Deep dive

Python has no built-in balanced search tree; bisect on a sorted list gives O(log n) search but O(n) inserts.

Java's TreeMap (also used from Kotlin) is a red-black tree: O(log n) for get, put and floor or ceiling queries.

Databases use B-trees: very wide nodes that keep the height tiny and match disk pages.

Common mistakes

  • Quoting O(log n) for an unbalanced search tree.
  • Forgetting that hash maps give O(1) average lookups but no ordering or range queries.

Senior take & follow-ups

Name the degenerate case (sorted inserts) and how balancing prevents it.

Follow-up questions

Think of your answer first, then open the hint.

  1. When would you pick a search tree over a hash map?

    Show hint

    When you need ordered iteration, range queries, or nearest-key lookups.

  2. What is a treap or skip list?

    Show hint

    Randomised structures with O(log n) expected operations and simpler code.

Similar on Backend: How a B-tree index speeds up a query Database indexes use B-trees: the same ordered-search idea, but each node holds hundreds of keys so the tree stays only a few levels deep on disk.

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.