Part 3 · 2 chapters · ~12 min

Trees and Balancing

Tree vocabulary and traversals, binary search trees, degeneration under sorted input, rotations and self-balancing (AVL, red-black), B-trees and why databases use them, tries, segment and Fenwick trees for range queries, and union-find.

Binary search trees

code

// traversals: the three orders and level order
function inorder(n: Node | null, out: number[] = []) { if (n) { inorder(n.left, out); out.push(n.key); inorder(n.right, out); } return out; }   // sorted for a BST
function levelOrder(root: Node | null) { const out: number[][] = []; let q = root ? [root] : [];
  while (q.length) { out.push(q.map(n => n.key)); q = q.flatMap(n => [n.left, n.right].filter(Boolean) as Node[]); } return out; }

BINARY SEARCH TREES AND BALANCE

ordered data with O(log n) operations, if the tree stays balanced

swipe the figure sideways, or tap expand for full screen

1/5

the invariant

Every node's left subtree holds smaller keys and its right subtree larger keys. Searching compares and goes left or right: one level per step.

left smaller, right largerone comparison per level

B-trees, tries, range trees and union-find

structure	makes cheap	where you meet it
B-tree / B+tree	ordered lookups with few disk reads (hundreds of keys per node)	every relational database index (MySQL and Postgres courses)
trie	prefix lookups	autocomplete, routers (Fastify's radix tree), IP lookups
segment tree	range sums, minimums, updates in O(log n)	analytics over ranges, competitive programming
Fenwick (binary indexed) tree	prefix sums with updates in O(log n), tiny code	running balances over changing data
union-find (disjoint set)	"are these connected?" with near-O(1) merges	Kruskal's MST, grouping accounts linked by shared devices (fraud)

code

// union-find with path compression and union by size: near-constant per operation
class DSU { p: number[]; s: number[];
  constructor(n: number) { this.p = Array.from({ length: n }, (_, i) => i); this.s = Array(n).fill(1); }
  find(x: number): number { while (this.p[x] !== x) { this.p[x] = this.p[this.p[x]]; x = this.p[x]; } return x; }
  union(a: number, b: number) { a = this.find(a); b = this.find(b); if (a === b) return false;
    if (this.s[a] < this.s[b]) [a, b] = [b, a]; this.p[b] = a; this.s[a] += this.s[b]; return true; } }