Why trees need balancing

Sorted input turns a BST into a linked list — and the structures invented to stop it.

Lesson 49 of 75 · Intermediate 3 min read

Insert 1, 2, 3, 4, 5 into a plain BST in order. Every value is larger than the last, so every insert goes right:

That is a linked list wearing a tree's type. Search is O(n), and the input that causes it — already-sorted data — is the input you are most likely to receive.

Self-balancing trees

The fix is to detect imbalance during insertion and repair it with rotations, local pointer rearrangements that preserve the BST ordering while reducing height.

AVL trees keep the heights of a node's subtrees within one of each other. Strictly balanced, so lookups are as fast as possible; more rotations on write.

Red-black trees relax the rule — the longest path is at most twice the shortest — and rebalance less often. That trade makes them the default in standard libraries: Java's TreeMap, C++'s std::map, and the Linux kernel's scheduler all use them.

B-trees and B+ trees hold many keys per node so that one node fits a disk page or a cache line. With a branching factor of a few hundred, a billion rows sit four levels deep — which is why every relational database index is a B+ tree, not a binary tree.

Structure	Lookup	Insert	Where you meet it
Unbalanced BST	O(n) worst	O(n) worst	Textbooks, and bugs
AVL	O(log n)	O(log n), more rotations	Read-heavy in-memory indexes
Red-black	O(log n)	O(log n), fewer rotations	Language standard libraries
B+ tree	O(log n)	O(log n)	Databases, filesystems

What you are expected to know

Interviewers rarely ask you to implement a red-black tree — it is long, fiddly, and tests memory rather than thinking. What they do expect:

that an unbalanced BST degrades to O(n), and why sorted input causes it;
that rotations restore height without breaking the ordering;
that a balanced tree is the right answer when you need order and logarithmic operations;
that a hash map beats it whenever ordering is not required.

The pragmatic alternative

A skip list reaches the same O(log n) expected bounds using randomised levels instead of rotations, and is far easier to implement correctly. Redis uses one for sorted sets. If you ever genuinely need to build an ordered structure by hand, reach for that before a red-black tree.