01 / The idea
Find a name in a few comparisons.
A conference desk has a badge for every registered attendee. Someone walks up and says their name; staff need that badge now, walk-ins register all morning, badges leave as people collect them, and at any moment the desk may want the next dozen names in order to lay out.
A binary search tree keeps every name smaller than a node on its left and every larger name on its right. To find a name, start at the top and go left or right until it matches. To add one, go the same way until there is nowhere to go, and attach it there. Reading the left side, then the node, then the right side lists every name in order.
The idea dates to 1960, found independently by several people. The kernel’s rbtree notes
list its users: I/O schedulers, high-resolution timers, “Virtual memory areas (VMAs) are
tracked with red-black trees, as are epoll file descriptors.” C++ maps are “typically
implemented as binary search trees,” and TreeMap “provides guaranteed log(n) time
cost” for its lookups and changes.
02 / Name the rule
Smaller left, larger right, and keep it short.
A search costs one comparison per level, so the tree’s height is the price of every call. Nine names can sit in four levels. But names that arrive in order each go right of everything before them, and nine names make nine levels: a list on its side. A registration export sorted by family name does exactly that.
A balanced tree refuses to let that happen. After each change it walks back up, and wherever one side of a node is two levels taller than the other, it rotates: the taller child moves up, the node moves down on the other side, and one subtree changes parent. Names stay in order; the height shrinks by one.
This lesson uses the first such rule, the AVL tree, published by Georgy Adelson-Velsky and Evgenii Landis in 1962: at every node, the two sides differ in height by at most one. That keeps a tree of n names within about 1.44 log₂ n levels.
Why do libraries use red-black trees instead?Looser balance, fewer rotations
A red-black tree colors each node and keeps a weaker promise: no path is more than twice as long as another. The kernel’s notes put the trade plainly: red-black trees “provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.”
AVL keeps the stricter promise, which makes lookups a little shorter and changes a little busier. Both keep every call to O(log n); the rotations are the same moves. AVL’s rule is simpler to see, which is why it is the one here.
03 / Follow one operation
Nine names, in export order.
The export lists nine attendees alphabetically, from Chidi Abara to Sora Ito. The animation imports them into a plain tree, then into a balanced one, and runs the desk: a search, a walk-in, a pickup, and the next badges.
Before you watch, predict how tall each tree ends, and who takes Camille Dubois’s place when she collects her badge from the top of the balanced tree. The animation replays what the TypeScript example recorded. Try it lets you run the desk yourself.
Go left or right. Keep it short.
Search tree · L holds smaller names, R larger; h is the height below and including a name
Plain tree · 9 names imported in export order
- Abara, Chidih9
- RBergström, Linneah8
- RCastillo, Mateoh7
- RDubois, Camilleh6
- REndo, Harukih5
- RFischer, Jonash4
- RGupta, Priyah3
- RHaddad, Laylah2
- RIto, Sorah1
- RHaddad, Laylah2
- RGupta, Priyah3
- RFischer, Jonash4
- REndo, Harukih5
- RDubois, Camilleh6
- RCastillo, Mateoh7
- RBergström, Linneah8
Waiting 9 Height 9 Compared 0 Rotations 0
One long branch, nine tall.
The export arrives sorted, so every name is larger than all the names before it and goes to the right of them. The plain tree is a list on its side: height 9.
Reduced motion: choose a scene to see its completed state.
Read this scene
The export arrives sorted, so every name is larger than all the names before it and goes to the right of them. The plain tree is a list on its side: height 9.
The export arrives sorted, so every name is larger than all the names before it and goes to the right of them. The plain tree is a list on its side: height 9.
Waiting: 9. Compared so far: 0. Rotations so far: 0.
Watch restarts when you return. Step through keeps your selected step. Try it starts from the imported export each time you open it.
04 / Read the shape
One tree, one badge desk.
Basic form is SearchTree: insert, find, remove, and entries in
key order, balanced by default and able to switch balancing off so the lesson can measure
both. In the wild wraps it in BadgeDesk, which checks names,
files badges by family then given name, refuses a second registration, and lists the next
badges to lay out.
A search tree over string keys that balances itself with AVL rotations, or not, so the two can be compared. Insert, find, remove with a successor, and read entries in key order, recording every comparison, attachment, rotation, and removal.
export type Step = {
/**
* left or right: the key is smaller or larger than this node's, so go that way. found: the
* keys match. attach: add the key as a node under `other`, or as the root. rotate-left or
* rotate-right: turn the subtree at this node to restore balance. detach: take out a node
* with at most one child, which moves up. successor: a node with two children takes the key
* of `other`, the smallest key to its right, detached just before. visit: read a node in
* key order.
*/
kind:
| 'left'
| 'right'
| 'found'
| 'attach'
| 'rotate-left'
| 'rotate-right'
| 'detach'
| 'successor'
| 'visit';
at: string;
other?: string;
};
export type Entry<V> = { key: string; value: V };
export type Outline = { key: string; left: Outline | null; right: Outline | null };
type Node<V> = {
key: string;
value: V;
left: Node<V> | null;
right: Node<V> | null;
height: number;
};
type Link<V> = { node: Node<V>; side: 'left' | 'right' };
const heightOf = <V>(node: Node<V> | null) => node?.height ?? 0;
const update = <V>(node: Node<V>) => {
node.height = 1 + Math.max(heightOf(node.left), heightOf(node.right));
};
/** Compare by code point, as Go compares strings, not by UTF-16 unit as `<` does. */
export function compareKeys(a: string, b: string): number {
for (let i = 0; i < Math.min(a.length, b.length); i++) {
const x = a.charCodeAt(i);
const y = b.charCodeAt(i);
if (x === y) continue;
// A surrogate unit belongs to a code point above U+FFFF, which sorts after every other unit.
const xHigh = x >= 0xd800 && x <= 0xdfff;
const yHigh = y >= 0xd800 && y <= 0xdfff;
return xHigh === yHigh ? x - y : xHigh ? 1 : -1;
}
return a.length - b.length;
}
// A binary search tree keeps every key smaller than a node on its left and every larger key
// on its right, so a search follows one path down. The path is as long as the tree is tall.
// Keys that arrive in order make one long branch, so a balanced tree measures the heights of
// each node's two sides and rotates whenever they differ by more than one (an AVL tree).
export class SearchTree<V> {
#root: Node<V> | null = null;
#size = 0;
readonly balanced: boolean;
constructor({ balanced = true }: { balanced?: boolean } = {}) {
this.balanced = balanced;
}
// Returns false, and changes nothing, when the key is already there.
insert(key: string, value: V, steps?: Step[]): boolean {
const path: Link<V>[] = [];
for (let node = this.#root; node;) {
const order = compareKeys(key, node.key);
if (order === 0) {
steps?.push({ kind: 'found', at: node.key });
return false;
}
const side = order < 0 ? 'left' : 'right';
steps?.push({ kind: side, at: node.key });
path.push({ node, side });
node = node[side];
}
const fresh: Node<V> = { key, value, left: null, right: null, height: 1 };
const parent = path.at(-1);
if (parent) {
steps?.push({ kind: 'attach', at: key, other: parent.node.key });
parent.node[parent.side] = fresh;
} else {
steps?.push({ kind: 'attach', at: key });
this.#root = fresh;
}
this.#size++;
this.#fix(path, steps);
return true;
}
find(key: string, steps?: Step[]): V | undefined {
for (let node = this.#root; node;) {
const order = compareKeys(key, node.key);
if (order === 0) {
steps?.push({ kind: 'found', at: node.key });
return node.value;
}
const side = order < 0 ? 'left' : 'right';
steps?.push({ kind: side, at: node.key });
node = node[side];
}
return undefined;
}
// Returns false when the key is not there.
remove(key: string, steps?: Step[]): boolean {
const path: Link<V>[] = [];
let node = this.#root;
while (node && compareKeys(key, node.key) !== 0) {
const side = compareKeys(key, node.key) < 0 ? 'left' : 'right';
steps?.push({ kind: side, at: node.key });
path.push({ node, side });
node = node[side];
}
if (!node) return false;
steps?.push({ kind: 'found', at: node.key });
if (node.left && node.right) {
// Two children: the smallest key on the right moves into this node.
steps?.push({ kind: 'right', at: node.key });
path.push({ node, side: 'right' });
let next = node.right;
while (next.left) {
steps?.push({ kind: 'left', at: next.key });
path.push({ node: next, side: 'left' });
next = next.left;
}
steps?.push({ kind: 'detach', at: next.key });
const above = path.at(-1)!;
above.node[above.side] = next.right;
steps?.push({ kind: 'successor', at: node.key, other: next.key });
node.key = next.key;
node.value = next.value;
} else {
steps?.push({ kind: 'detach', at: node.key });
const child = node.left ?? node.right;
const parent = path.at(-1);
if (parent) parent.node[parent.side] = child;
else this.#root = child;
}
this.#size--;
this.#fix(path, steps);
return true;
}
/** Up to `limit` entries in key order. */
entries(limit: number, steps?: Step[]): Entry<V>[] {
if (!Number.isInteger(limit) || limit < 1 || limit > 100_000)
throw new RangeError('limit must be a whole number from 1 to 100000');
const found: Entry<V>[] = [];
const stack: Node<V>[] = [];
let node = this.#root;
while ((node || stack.length) && found.length < limit) {
for (; node; node = node.left) stack.push(node);
node = stack.pop()!;
steps?.push({ kind: 'visit', at: node.key });
found.push({ key: node.key, value: node.value });
node = node.right;
}
return found;
}
/** The tree's shape, for drawing. Copied with an explicit stack, like every other walk. */
outline(): Outline | null {
if (!this.#root) return null;
const top: Outline = { key: this.#root.key, left: null, right: null };
const pending: [Node<V>, Outline][] = [[this.#root, top]];
while (pending.length) {
const [node, copy] = pending.pop()!;
if (node.left) {
copy.left = { key: node.left.key, left: null, right: null };
pending.push([node.left, copy.left]);
}
if (node.right) {
copy.right = { key: node.right.key, left: null, right: null };
pending.push([node.right, copy.right]);
}
}
return top;
}
get size(): number {
return this.#size;
}
/** Nodes on the longest path from the root; 0 when empty. */
get height(): number {
return heightOf(this.#root);
}
// Walk back up the path, updating heights and, when balancing, rotating any node whose
// sides differ in height by more than one.
#fix(path: Link<V>[], steps?: Step[]) {
for (let i = path.length - 1; i >= 0; i--) {
const fixed = this.#rebalance(path[i].node, steps);
if (i === 0) this.#root = fixed;
else path[i - 1].node[path[i - 1].side] = fixed;
}
}
#rebalance(node: Node<V>, steps?: Step[]): Node<V> {
update(node);
if (!this.balanced) return node;
const lean = heightOf(node.left) - heightOf(node.right);
if (lean > 1) {
if (heightOf(node.left!.left) < heightOf(node.left!.right))
node.left = this.#rotateLeft(node.left!, steps);
return this.#rotateRight(node, steps);
}
if (lean < -1) {
if (heightOf(node.right!.right) < heightOf(node.right!.left))
node.right = this.#rotateRight(node.right!, steps);
return this.#rotateLeft(node, steps);
}
return node;
}
#rotateRight(node: Node<V>, steps?: Step[]): Node<V> {
steps?.push({ kind: 'rotate-right', at: node.key });
const up = node.left!;
node.left = up.right;
up.right = node;
update(node);
update(up);
return up;
}
#rotateLeft(node: Node<V>, steps?: Step[]): Node<V> {
steps?.push({ kind: 'rotate-left', at: node.key });
const up = node.right!;
node.right = up.left;
up.left = node;
update(node);
update(up);
return up;
}
}// Step is one move. Kind is "left" or "right" (the key is smaller or larger than this
// node's, so go that way), "found" (the keys match), "attach" (add the key as a node under
// Other, or as the root), "rotate-left" or "rotate-right" (turn the subtree at this node to
// restore balance), "detach" (take out a node with at most one child, which moves up),
// "successor" (a node with two children takes the key of Other, the smallest key to its
// right, detached just before), or "visit" (read a node in key order).
type Step struct {
Kind string `json:"kind"`
At string `json:"at"`
Other string `json:"other,omitempty"`
}
type Entry[V any] struct {
Key string
Value V
}
// Outline is the tree's shape, for drawing.
type Outline struct {
Key string
Left, Right *Outline
}
type node[V any] struct {
key string
value V
left, right *node[V]
height int
}
func heightOf[V any](n *node[V]) int {
if n == nil {
return 0
}
return n.height
}
func (n *node[V]) update() { n.height = 1 + max(heightOf(n.left), heightOf(n.right)) }
// link is a node on the way down and the side taken from it.
type link[V any] struct {
node *node[V]
left bool
}
func (l link[V]) set(child *node[V]) {
if l.left {
l.node.left = child
} else {
l.node.right = child
}
}
func record(steps *[]Step, kind, at, other string) {
if steps != nil {
*steps = append(*steps, Step{kind, at, other})
}
}
// Tree is a binary search tree: every key smaller than a node is on its left and every
// larger key on its right, so a search follows one path down, as long as the tree is tall.
// Keys that arrive in order make one long branch, so a balanced tree measures the heights of
// each node's two sides and rotates whenever they differ by more than one (an AVL tree).
type Tree[V any] struct {
root *node[V]
size int
balanced bool
}
func NewTree[V any](balanced bool) *Tree[V] { return &Tree[V]{balanced: balanced} }
// Insert returns false, and changes nothing, when the key is already there.
func (t *Tree[V]) Insert(key string, value V, steps *[]Step) bool {
var path []link[V]
for n := t.root; n != nil; {
switch c := strings.Compare(key, n.key); {
case c == 0:
record(steps, "found", n.key, "")
return false
case c < 0:
record(steps, "left", n.key, "")
path = append(path, link[V]{n, true})
n = n.left
default:
record(steps, "right", n.key, "")
path = append(path, link[V]{n, false})
n = n.right
}
}
fresh := &node[V]{key: key, value: value, height: 1}
if len(path) == 0 {
record(steps, "attach", key, "")
t.root = fresh
} else {
parent := path[len(path)-1]
record(steps, "attach", key, parent.node.key)
parent.set(fresh)
}
t.size++
t.fix(path, steps)
return true
}
func (t *Tree[V]) Find(key string, steps *[]Step) (V, bool) {
for n := t.root; n != nil; {
switch c := strings.Compare(key, n.key); {
case c == 0:
record(steps, "found", n.key, "")
return n.value, true
case c < 0:
record(steps, "left", n.key, "")
n = n.left
default:
record(steps, "right", n.key, "")
n = n.right
}
}
var zero V
return zero, false
}
// Remove returns false when the key is not there.
func (t *Tree[V]) Remove(key string, steps *[]Step) bool {
var path []link[V]
n := t.root
for n != nil && n.key != key {
if key < n.key {
record(steps, "left", n.key, "")
path = append(path, link[V]{n, true})
n = n.left
} else {
record(steps, "right", n.key, "")
path = append(path, link[V]{n, false})
n = n.right
}
}
if n == nil {
return false
}
record(steps, "found", n.key, "")
if n.left != nil && n.right != nil {
// Two children: the smallest key on the right moves into this node.
record(steps, "right", n.key, "")
path = append(path, link[V]{n, false})
next := n.right
for next.left != nil {
record(steps, "left", next.key, "")
path = append(path, link[V]{next, true})
next = next.left
}
record(steps, "detach", next.key, "")
path[len(path)-1].set(next.right)
record(steps, "successor", n.key, next.key)
n.key, n.value = next.key, next.value
} else {
record(steps, "detach", n.key, "")
child := n.left
if child == nil {
child = n.right
}
if len(path) == 0 {
t.root = child
} else {
path[len(path)-1].set(child)
}
}
t.size--
t.fix(path, steps)
return true
}
// Entries returns up to limit entries in key order.
func (t *Tree[V]) Entries(limit int, steps *[]Step) ([]Entry[V], error) {
if limit < 1 || limit > 100_000 {
return nil, errors.New("limit must be a whole number from 1 to 100000")
}
found := []Entry[V]{}
var stack []*node[V]
n := t.root
for (n != nil || len(stack) > 0) && len(found) < limit {
for ; n != nil; n = n.left {
stack = append(stack, n)
}
n = stack[len(stack)-1]
stack = stack[:len(stack)-1]
record(steps, "visit", n.key, "")
found = append(found, Entry[V]{n.key, n.value})
n = n.right
}
return found, nil
}
func (t *Tree[V]) Outline() *Outline {
var copyOf func(n *node[V]) *Outline
copyOf = func(n *node[V]) *Outline {
if n == nil {
return nil
}
return &Outline{n.key, copyOf(n.left), copyOf(n.right)}
}
return copyOf(t.root)
}
func (t *Tree[V]) Size() int { return t.size }
// Height counts nodes on the longest path from the root; 0 when empty.
func (t *Tree[V]) Height() int { return heightOf(t.root) }
// fix walks back up the path, updating heights and, when balancing, rotating any node whose
// sides differ in height by more than one.
func (t *Tree[V]) fix(path []link[V], steps *[]Step) {
for i := len(path) - 1; i >= 0; i-- {
fixed := t.rebalance(path[i].node, steps)
if i == 0 {
t.root = fixed
} else {
path[i-1].set(fixed)
}
}
}
func (t *Tree[V]) rebalance(n *node[V], steps *[]Step) *node[V] {
n.update()
if !t.balanced {
return n
}
switch lean := heightOf(n.left) - heightOf(n.right); {
case lean > 1:
if heightOf(n.left.left) < heightOf(n.left.right) {
n.left = rotateLeft(n.left, steps)
}
return rotateRight(n, steps)
case lean < -1:
if heightOf(n.right.right) < heightOf(n.right.left) {
n.right = rotateRight(n.right, steps)
}
return rotateLeft(n, steps)
}
return n
}
func rotateRight[V any](n *node[V], steps *[]Step) *node[V] {
record(steps, "rotate-right", n.key, "")
up := n.left
n.left, up.right = up.right, n
n.update()
up.update()
return up
}
func rotateLeft[V any](n *node[V], steps *[]Step) *node[V] {
record(steps, "rotate-left", n.key, "")
up := n.right
n.right, up.left = up.left, n
n.update()
up.update()
return up
}Reading the TypeScriptA path array, not recursion
insert and remove push each node and the side taken onto a path, then #fix walks it backward, updating heights and rotating.
Recursion would be shorter, but a plain tree of a 10,000-name export is 10,000 deep, deeper
than a JavaScript stack allows.
compareKeys compares by code point. JavaScript’s < compares UTF-16
units, which puts some characters above U+FFFF before others below it, and would order names
differently from Go.
Reading the GoGenerics and a link type
Tree[V any] holds values of any type, and link records a node
and whether the path went left, with a set method that relinks that side. strings.Compare compares bytes, and UTF-8 bytes sort in code point order, so
no helper is needed.
Find returns the value and a boolean, and errors are values: Register returns error for a bad name or a second registration.
What would I normally use in application code?Often not a hand-written tree
Neither TypeScript nor Go ships a sorted map. For a list that rarely changes, a sorted
array with binary search finds a name in the
same number of comparisons with far less memory. A database index is a B-tree, and so is
Rust’s BTreeMap, whose documentation explains that a binary search tree
allocates every node separately, and “every comparison is a potential cache-miss.”
Reach for a balanced tree when keys change often and you also need them in order: Java’s TreeMap, C++’s std::map, or a well-tested package. Writing one
yourself is for learning, or for a structure the libraries do not offer.
05 / Try a decision
A sorted export, all day.
The desk is slow and the cause is the export’s order. Decide which fix survives a full day, noon’s day passes included, before the feedback tells you.
06 / Follow the cost
2,000 comparisons, or 11.
Here is every operation at a glance, with n waiting badges and a tree of height h. The rest of this section measures a conference of 2,000.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Find a name | O(h) | O(1) | h is the height: about log₂ n when balanced, up to n when not. |
| Register a name | O(h) | O(h) | Walk to an empty place and attach. A balanced tree needs at most one single or double rotation. |
| Pick up a badge | O(h) | O(h) | With two children, the smallest name on the right takes the place. Balancing may rotate at each level. |
| Next k badges in order | O(h + k) | O(h) | Walk left to the smallest name, then read in order, keeping a stack of the way back. |
| Plain tree, sorted export | O(n) per call | O(n) | Every name goes right of the last, so the height is n. |
| Sorted array instead | O(log n) find, O(n) insert | O(n) | Binary search finds a name; a walk-in in the middle shifts every name after it. |
| Hold n waiting badges | — | O(n) | One node per badge: the name key, the badge, two child links, and a stored height. |
In the animation, nine names in export order made a plain tree nine tall and a balanced tree four tall, and finding the last name took nine comparisons against four. At 2,000 names in export order, the plain tree was 2,000 tall: importing took 1,999,000 comparisons, and looking up every attendee once averaged 1,000.5 comparisons each. The balanced tree was 11 tall: the import took 19,953 comparisons and 1,989 rotations, and a lookup averaged 9.98.
Random order is kinder but not a plan. Shuffled first, the plain tree was 21 to 30 tall over 20 shuffles, and one run averaged 13.97 comparisons a lookup; the balanced tree built from the same shuffle was 13 tall and averaged 10.19. Collecting every badge in random order from the balanced tree of the sorted export took 517 rotations.
A sorted array finds any of the 2,000 in at most 11 probes, the same as the balanced tree, and stores nothing but the names. Its weakness is change: a walk-in placed at random shifts 1,000 names on average, and so does each pickup. The tree pays a few pointer changes instead. These are counts from the lesson’s TypeScript example, not timings.
07 / Give it a real job
File names carefully.
BadgeDesk files each badge under “family, given” with capital letters A to Z
folded to lowercase, so staff can type ito or ITO. Everything else
compares by code point, which is not any language’s alphabet: Ødegård sorts after Zhou, and
a Swedish desk would expect Å, Ä, and Ö at the end while a German one files Ö with O. A real
desk sorts with a collator for its locale, and keeps it the same for every comparison, or
the tree’s order breaks.
Two attendees can share a name, and this desk refuses the second registration rather than guess. A production desk adds a tie-breaker to the key, such as the registration number, and shows both badges when staff search. Like this desk, it remembers collected badges and refuses a second pickup.
08 / Make the call
Ask whether order and change both matter.
Reach for a balanced search tree when keys keep arriving and leaving and you still need them in order: the next few, the smallest, everything in sequence. Every call stays O(log n) whatever order the keys come in.
Look elsewhere when one of those needs goes away. For lookups by exact name only, a hash map answers in one step. For a list that rarely changes, a sorted array and binary search are smaller. If you only ever need the smallest, a binary heap is simpler. If the question is every name starting with some letters, a trie walks the prefix. And ranges, such as every badge from Castillo to Fischer, are what an ordered map answers.
09 / Take the idea with you
Explain it without saying “binary search tree.”
“Each name has smaller names hanging to its left and larger ones to its right. To find a name I compare from the top and go left or right, one comparison per level. When one side of a name gets two levels taller than the other, I lift the taller child up and move the name down, so the order stays and the levels shrink. To take out a name with names on both sides, I move in the smallest name from its right.” That describes the mechanism. The name is what you call it in a review.
Before moving on, explain three things without the name: why a sorted export made nine levels out of nine names, what one rotation changes, and why Haruki Endo took Camille Dubois’s place. Then look at a list your code keeps sorted by inserting into an array, and decide whether it changes often enough to need a tree.
Connections to follow nextRelated lessons
- Binary search halves a sorted array the way a balanced tree halves its names, without the pointers.
- Binary heap keeps only the smallest within reach, in an array, with no rotations.
- Hash map finds a name in one step when order does not matter.
- Trie branches on each character instead of each comparison, for questions about prefixes.
- Ordered map answers floor, ceiling, and range questions over sorted keys, with a skip list instead of rotations.