juniorTrees

What is the difference between a balanced and unbalanced tree?

Updated Feb 20, 2026

Short answer

A balanced tree keeps its height proportional to log n, so every root-to-leaf path is short and operations stay O(log n). An unbalanced tree can have height up to n — in the worst case a straight chain — turning every operation into an O(n) linear scan. Since operations cost is proportional to height, balance is the difference between logarithmic and linear performance.

Deep explanation

Balance is usually defined per node: the heights of its two subtrees differ by at most a small constant, recursively.

TypeScript
Balanced (height 3, n=7)        Unbalanced (height 7, n=7)
        4                        1
      /   \                           2       6                      2
   / \     / \                        1   3   5   7                      3 ... down to 7
  every path: 3 steps               path to 7: 7 steps

Both hold seven nodes. Searching the first takes at most 3 comparisons; the second takes 7. At a million nodes that becomes 20 against 1,000,000 — the unbalanced tree has silently become a linked list with extra pointer overhead.

How trees become unbalanced. Inserting sorted or nearly-sorted data into a plain BST. Every key is larger than the last, so every insertion goes right, and the tree grows into a chain. This is not a rare pathological case: exported data, autoincrement IDs, and timestamps are all naturally ordered.

How balance is maintained. Rotations — local restructurings that reduce height while preserving the ordering invariant:

TypeScript
3              2
   /              /   2      -->     1   3
 /
1        right rotation
  • AVL — strict, height difference at most 1. More rotations on write, shallower tree, faster reads.
  • Red-black — looser, longest path at most twice the shortest. Fewer rotations, slightly taller, better for write-heavy use. This is what std::map and Java's TreeMap use.
  • B-tree — many keys per node to match disk and page sizes; the basis of nearly every database index.

The trade-off. Rebalancing costs work on every insertion and deletion. You pay a constant factor on writes to avoid an asymptotic collapse on reads — almost always the right trade, which is why self-balancing trees are the default in standard libraries rather than plain BSTs.

Real-world example

Loading a million records ordered by ID into a plain BST:

Python
for record in records:            # ids 1, 2, 3, ... in order
    root = insert(root, record.id)

Every key exceeds the previous, so each insertion walks the entire right spine. Building the tree is O(n²) — roughly 500 billion operations — and every later lookup is O(n).

Two fixes: shuffle before inserting, which makes the expected height O(log n), or use a self-balancing tree so input order stops mattering. In production, the second is the reliable answer; you rarely control the order data arrives in.

Common mistakes

  • - Assuming a BST is balanced by default. Nothing enforces it, and ordered input reliably produces the worst case.
  • - Defining balance by comparing only the two subtrees of the root
  • the property must hold recursively at every node.
  • - Overlooking that rebalancing costs write throughput — for a write-heavy workload with rare reads, that trade may not pay.
  • - Confusing a complete tree with a balanced one. A heap is complete by construction but is not a search tree
  • balance and completeness are different properties.
  • - Building a tree from sorted input without shuffling or self-balancing, producing O(n²) construction.

Follow-up questions

  • What is a tree rotation?
  • Why do databases use B-trees rather than binary trees?
  • Is a complete tree the same as a balanced tree?
  • How does a treap or skip list achieve balance differently?

More Trees interview questions

View all →