Trees and Graphs: Traversals and Applications

Trees and graphs are the connective tissue of working systems — file systems and B-tree indexes, build DAGs and package managers, schedulers and routers, virtual DOMs and union-find connectivity. This article is the senior-engineer mental model: which tree variant fits which workload, when adjacency lists beat matrices, why three colours are needed for directed cycle detection, what Kahn’s algorithm actually does in a build pipeline, when Dijkstra silently lies (negative weights), and why path-compressed union-find behaves like O(1) in practice. Each section pairs the mechanism with a diagram, a complexity row, and the production system that depends on it.

Mental model

Trees and graphs share a node-and-edge substrate. The distinction is structural: trees enforce a single parent and forbid cycles; graphs allow arbitrary connections, including cycles and multi-edges. Once you internalise that, the rest is engineering trade-offs:

• Tree variant = access-pattern fit. AVL trades insert/delete cost for tighter height (search-heavy). Red-black trees trade height for rotation budget (write-heavy and the default in standard libraries). B/B+ trees raise fanout so the working set fits fewer disk or SSD pages (databases, file systems). Tries amortise per-character work across shared prefixes (autocomplete, IP routing).
• Graph representation = density bet. Adjacency matrices give O(1) edge lookup but always cost O(V²) space — only worth it on dense graphs. Adjacency lists cost O(V + E) and dominate everywhere else, which means almost everything real (social networks, road maps, dependency graphs).
• Traversal = question shape. DFS uses a stack and probes deep first — natural for cycle detection, topological order, and any “explore one branch fully” problem. BFS uses a queue and explores level by level — the only traversal that finds shortest paths in unweighted graphs in linear time.
• Union-Find = connectivity oracle. Path compression plus union-by-rank pushes the amortised cost per operation to O(α(n)), where α is the inverse Ackermann function — at most 4 for any input the universe can hold¹.

Tree variants

Binary search tree (BST)

A BST holds the in-order invariant left subtree < node < right subtree. Search, insert, and delete are O(h) where h is the height. The catch: the height isn’t bounded unless something keeps it bounded.

Show 3 hidden lines4  right: BSTNode<T> | null5}67// Sorted insertions degenerate the tree to a linked list:8// insert(1), insert(2), insert(3), insert(4)9//   1 -> 2 -> 3 -> 4   (height = n, all ops O(n))10//11// The fix is a balancing invariant: AVL, Red-Black, B-tree, treap, ...

AVL trees: strict balance for search-heavy workloads

AVL trees, named after Adelson-Velsky and Landis (1962), were the first self-balancing BSTs². Every node’s balance factor — the height difference between left and right subtrees — must stay in {-1, 0, +1}. Insert or delete may break this; the tree restores it with a single or double rotation along the path back to the root.

• What you get: the tightest height bound of the common balanced trees (h ≤ 1.44 · log₂(n+2))³. Lookups visit fewer nodes than a comparable red-black tree.
• What you pay: more rotations per modification (potentially log n on the path back to the root) — a cost that matters under heavy mutation.
• When to reach for it: search-dominated workloads where you can amortise the rotation cost — read-mostly indexes, lookup-heavy in-memory dictionaries.

Red-black trees: looser balance for write-heavy workloads

Red-black trees come from Guibas and Sedgewick’s 1978 paper “A Dichromatic Framework for Balanced Trees”⁴. The invariants are colour-based, not height-based:

1. Every node is red or black.
2. The root is black.
3. NIL leaves are black.
4. A red node’s children are both black (no two reds in a row).
5. Every root-to-leaf path crosses the same number of black nodes (“black-height”).

Together these bound the height at 2 · log₂(n+1) — looser than AVL — but in exchange every insert needs at most 2 rotations and every delete at most 3, making modifications cheaper on average⁵.

• Production footprint: Java’s TreeMap and TreeSet, the GCC and LLVM standard libraries’ std::map / std::set, and the Linux kernel’s red-black tree (include/linux/rbtree.h) used by the Completely Fair Scheduler — and now the EEVDF scheduler since Linux 6.6 — to keep the runqueue ordered by virtual deadline⁶⁷.
• Why the kernel chose RB over a heap: the scheduler needs O(log n) insert and remove plus O(1) “leftmost” lookup (the next task). A red-black tree gives both with a contiguous parent/child layout that doesn’t need the heap’s sift-down on arbitrary removal⁶.

AVL vs red-black: the trade-off

B-trees and B+ trees: page-aware indexes

Binary trees are wrong for storage that fetches in pages. A modern HDD pays roughly 4–10 ms per random seek; a NVMe SSD pays 20–80 µs⁸. Either way the cost per node access dwarfs the comparison cost, so the engineering goal is to make each fetched page do as much work as possible. That means raising the fanout.

A B-tree of order m⁹:

• Every node holds up to m − 1 keys and m children.
• Every non-root node holds at least ⌈m/2⌉ − 1 keys.
• All leaves sit at the same depth (perfectly balanced).

Sized so a node fits one page (4–16 KB), a B-tree with millions of keys is typically 3–4 levels deep, so a point lookup costs 3–4 page fetches.

A B+ tree is the variant most production databases ship¹⁰¹¹:

• Internal nodes store only routing keys.
• All values live in the leaf level.
• Leaves are linked into a doubly-linked list for cheap range scans.

Production footprint:

• PostgreSQL uses Lehman & Yao’s high-concurrency B+ tree variant, which adds a right-link per page so readers traverse without blocking on splits¹⁰.
• MySQL InnoDB stores every table as a clustered B+ tree on the primary key; secondary indexes are separate B+ trees whose leaves hold the primary-key value rather than a row pointer¹¹.
• SQLite uses a B-tree for index pages and a B+ tree for table pages¹².
• File systems: NTFS, HFS+, Btrfs, and XFS use B/B+ trees for directories and on-disk indexes; ext4 uses an HTree (a hashed B-tree variant with fixed depth 1–2) for directory indexing¹³.

Show 2 hidden lines3  children: BTreeNode<K, V>[] // up to m4  isLeaf: boolean5}67// Order-4 node holding keys [10, 20, 30] partitions the key space:8//   (-inf, 10)  [10, 20)  [20, 30)  [30, +inf)9//      child 0    child 1    child 2    child 310//11// 1M keys, order 100 (~100 keys per page) -> height ≤ 3 -> at most12// 3 page fetches per point lookup, regardless of where the key sits.

Tries: prefix-shared search

Tries (aka prefix trees) replace per-key comparison with per-character descent. Each edge represents one character; a marked node means “a stored string ends here”. Lookup, insert, and delete are O(L) where L is the key length — independent of how many strings are stored.

• What they buy: prefix queries that hash maps cannot answer (autocomplete, “all keys starting with pre”), and longest-prefix matching for routing tables.
• What they cost: more memory than a hash table — every distinct character on the path needs a node or edge unless you compress.
• The compressed variants matter in practice:
  • Radix / Patricia tries collapse single-child chains into a single edge labelled with multiple characters¹⁴.
  • LC-tries add level compression on top, expanding dense subtries into a single node with a 2^k-entry vector. The Linux IPv4 routing table (fib_trie) has used an LC-trie for longest-prefix-match lookups since kernel 2.6.39¹⁵.

Application footprint: autocomplete, spell checking, IP routing (LC-trie / Patricia), genomic suffix structures.

Graph representations

Adjacency matrix

A V × V matrix where matrix[i][j] carries the edge weight (or 0/1 for unweighted). Edges are O(1) to look up but space is O(V²) regardless of how many edges exist.

Show 2 hidden lines34  constructor(vertices: number) {5    this.matrix = Array.from({ length: vertices }, () => Array(vertices).fill(0))6  }78  addEdge(u: number, v: number, weight = 1): void {9    this.matrix[u][v] = weight10    // For undirected: this.matrix[v][u] = weight11  }1213  hasEdge(u: number, v: number): boolean {14    return this.matrix[u][v] !== 0 // O(1)15  }16}

When it wins: dense graphs (E ≈ V²), heavy edge-existence queries, small graphs where V² is acceptable, and algorithms that benefit from cache-friendly contiguous memory (Floyd-Warshall is the canonical example).

Adjacency list

Each vertex maps to its set of neighbours. Space is O(V + E); edge-existence is O(degree) with arrays, O(1) with sets or hash maps.

Show 2 hidden lines34  constructor() {5    this.adj = new Map()6  }78  addEdge(u: number, v: number): void {9    if (!this.adj.has(u)) this.adj.set(u, new Set())10    this.adj.get(u)!.add(v)11  }1213  hasEdge(u: number, v: number): boolean {14    return this.adj.get(u)?.has(v) ?? false15  }1617  neighbors(u: number): number[] {18    return [...(this.adj.get(u) ?? [])]19  }20}

When it wins: sparse graphs (E ≪ V²) — which is virtually every real graph (social networks, road networks, dependency graphs), and any algorithm that iterates neighbours rather than probing arbitrary edges.

Representation trade-offs

Traversal algorithms

Depth-first search (DFS)

DFS goes deep before wide. The recursive version uses the call stack; the iterative version uses an explicit stack so you can run it on graphs deeper than your call-stack limit.

Show 3 hidden lines4  visited = new Set<number>(),5): void {6  if (visited.has(start)) return7  visited.add(start)8  // process(start)9  for (const neighbor of graph.get(start) ?? []) {10    dfsRecursive(graph, neighbor, visited)11  }12}1314function dfsIterative(graph: Map<number, number[]>, start: number): void {15  const visited = new Set<number>()16  const stack = [start]17  while (stack.length > 0) {18    const node = stack.pop()!19    if (visited.has(node)) continue20    visited.add(node)21    // process(node)22    const neighbors = graph.get(node) ?? []23    for (let i = neighbors.length - 1; i >= 0; i--) {24      if (!visited.has(neighbors[i])) stack.push(neighbors[i])25    }26  }27}

Tree DFS variants are useful in their own right:

• Preorder (root → left → right): tree copying, serialisation.
• Inorder (left → root → right): produces sorted output for a BST.
• Postorder (left → right → root): tree deletion, expression evaluation, dependency resolution where children must finish before the parent.

Complexity: O(V + E) time, O(V) space (visited set + stack/recursion depth).

Breadth-first search (BFS)

BFS explores all neighbours of the current node before any of their children, using a queue.

Show 3 hidden lines4  while (queue.length > 0) {5    const node = queue.shift()!6    // process(node)7    for (const neighbor of graph.get(node) ?? []) {8      if (!visited.has(neighbor)) {9        visited.add(neighbor)10        queue.push(neighbor)11      }12    }13  }14}

The defining property: in an unweighted graph, the first time BFS visits a node, it’s via a shortest path (in edge count). That single fact powers most “minimum hops” problems — friend-of-a-friend search, web crawls bounded by depth, network reachability checks.

Complexity: O(V + E) time, O(V) space.

DFS vs BFS

In wide-shallow graphs, DFS uses less memory; in deep-narrow graphs, BFS uses less. For balanced trees, both stay at O(log n).

Cycle detection

Undirected graphs: DFS with parent tracking

In undirected graphs, the parent → child → parent round-trip is structural, not a cycle. So the rule is: an edge to an already-visited node that isn’t the immediate parent is a back edge — and a back edge is a cycle.

Show 3 hidden lines4  function dfs(node: number, parent: number | null): boolean {5    visited.add(node)6    for (const neighbor of graph.get(node) ?? []) {7      if (!visited.has(neighbor)) {8        if (dfs(neighbor, node)) return true9      } else if (neighbor !== parent) {10        return true11      }12    }13    return false14  }1516  for (const v of vertices) {17    if (!visited.has(v) && dfs(v, null)) return true18  }19  return false20}

Directed graphs: three-colour DFS

In a directed graph, “I’ve seen this node before” doesn’t mean “I’m in a cycle” — you might just be re-arriving via a different path. The cycle question is: did I re-arrive at a node still on the current DFS path? That requires three states, not two.

Show 5 hidden lines67  function dfs(node: number): boolean {8    color.set(node, Color.GRAY)9    for (const neighbor of graph.get(node) ?? []) {10      if (color.get(neighbor) === Color.GRAY) return true       // back edge11      if (color.get(neighbor) === Color.WHITE && dfs(neighbor)) return true12    }13    color.set(node, Color.BLACK)14    return false15  }1617  for (const v of vertices) {18    if (color.get(v) === Color.WHITE && dfs(v)) return true19  }20  return false21}

This same machinery underlies most directed-DAG validators: import-cycle detection in module bundlers, dependency cycle detection in package managers, build-graph validation in CI.

Topological sorting

A topological order on a directed acyclic graph lists vertices so that for every edge u → v, u precedes v. It is the canonical output of dependency resolution.

Kahn’s algorithm (BFS-based)

Repeatedly emit a vertex with in-degree 0; decrement the in-degree of each of its out-neighbours; repeat until empty. If you ran out of zero-in-degree vertices but vertices remain, the graph has a cycle.

Show 3 hidden lines4): number[] | null {5  const inDegree = new Map<number, number>()6  vertices.forEach((v) => inDegree.set(v, 0))7  for (const [, neighbors] of graph) {8    for (const neighbor of neighbors) {9      inDegree.set(neighbor, (inDegree.get(neighbor) ?? 0) + 1)10    }11  }1213  const queue = vertices.filter((v) => inDegree.get(v) === 0)14  const result: number[] = []15  while (queue.length > 0) {16    const node = queue.shift()!17    result.push(node)18    for (const neighbor of graph.get(node) ?? []) {19      const newDegree = inDegree.get(neighbor)! - 120      inDegree.set(neighbor, newDegree)21      if (newDegree === 0) queue.push(neighbor)22    }23  }2425  return result.length === vertices.length ? result : null // null = cycle26}

DFS-based approach

Visit each unvisited vertex; emit it on the way back up (postorder); reverse at the end. The same colour bookkeeping that detected directed cycles tells you when the input isn’t a DAG.

Show 3 hidden lines4  const result: number[] = []56  function dfs(node: number): boolean {7    if (inStack.has(node)) return false8    if (visited.has(node)) return true9    visited.add(node)10    inStack.add(node)11    for (const neighbor of graph.get(node) ?? []) {12      if (!dfs(neighbor)) return false13    }14    inStack.delete(node)15    result.push(node)16    return true17  }1819  for (const v of vertices) {20    if (!visited.has(v) && !dfs(v)) return null21  }22  return result.reverse()23}

Both are O(V + E). Pick Kahn’s when you also want to drive a worker pool (it produces ready vertices in batches as in-degrees hit zero); pick the DFS form when the surrounding code already does a DFS.

Real-world applications: build systems (Make, Maven, Gradle, Bazel), package managers (npm, pip, cargo), database migrations, course-prerequisite scheduling, and any pipeline where step A must complete before step B begins.

Shortest paths

BFS for unweighted graphs

When every edge counts the same, BFS is the shortest-path algorithm. The first visit to a node is via a shortest path; reconstruct the path with a parent pointer back-chain.

Show 3 hidden lines4  end: number,5): number[] | null {6  const visited = new Set<number>([start])7  const parent = new Map<number, number>()8  const queue = [start]910  while (queue.length > 0) {11    const node = queue.shift()!12    if (node === end) {13      const path = [end]14      let current = end15      while (parent.has(current)) {16        current = parent.get(current)!17        path.unshift(current)18      }19      return path20    }21    for (const neighbor of graph.get(node) ?? []) {22      if (!visited.has(neighbor)) {23        visited.add(neighbor)24        parent.set(neighbor, node)25        queue.push(neighbor)26      }27    }28  }29  return null30}

Dijkstra (non-negative weights)

Always extract the unsettled vertex with the smallest tentative distance; relax its outgoing edges; repeat. The greedy invariant — once a vertex is settled, its distance is final — depends critically on edges being non-negative.

• Complexity: O((V + E) log V) with a binary heap. The classic Fibonacci-heap result is O(E + V log V) but the constant factors usually make a binary or d-ary heap competitive in practice¹⁶.
• Footprint: GPS routing (with A* on top), OSPF link-state routing, anything weighted with non-negative costs.

Bellman-Ford (handles negative weights)

Relax every edge V − 1 times. After that many rounds the shortest path distances are final unless a negative cycle exists; one extra round detects the cycle by spotting an edge that still relaxes.

• Complexity: O(V·E) — slower than Dijkstra by a factor of V / log V, paid in exchange for negative-weight support and explicit cycle detection.
• Footprint: the original distance-vector routing protocols (RIP), arbitrage detection across currency exchange rates (a profitable cycle is a negative cycle in -log(rate) space).

Algorithm selection

Union-Find (disjoint set union)

Union-Find answers “are x and y in the same connected component?” in near-constant amortised time. The two optimisations that get it there are:

• Union by rank (or by size): when merging two trees, attach the shorter under the taller so heights stay logarithmic.
• Path compression: every find walk re-points every visited node directly at the root, flattening the tree as a side effect of querying it.

Show 3 hidden lines45  constructor(elements: number[]) {6    this.parent = new Map()7    this.rank = new Map()8    elements.forEach((e) => {9      this.parent.set(e, e)10      this.rank.set(e, 0)11    })12  }1314  find(x: number): number {15    if (this.parent.get(x) !== x) {16      this.parent.set(x, this.find(this.parent.get(x)!)) // path compression17    }18    return this.parent.get(x)!19  }2021  union(x: number, y: number): void {22    const rootX = this.find(x)23    const rootY = this.find(y)24    if (rootX === rootY) return25    const rankX = this.rank.get(rootX)!26    const rankY = this.rank.get(rootY)!27    if (rankX < rankY) this.parent.set(rootX, rootY)28    else if (rankX > rankY) this.parent.set(rootY, rootX)29    else {30      this.parent.set(rootY, rootX)31      this.rank.set(rootX, rankX + 1)32    }33  }3435  connected(x: number, y: number): boolean {36    return this.find(x) === this.find(y)37  }38}

With both optimisations, the amortised cost of m operations on n elements is Θ(m · α(n)), where α is the inverse Ackermann function — at most 4 for any n you can store on real hardware¹¹⁷.

Footprint: Kruskal’s MST, dynamic connectivity, percolation models, image segmentation, and the cycle detector in undirected graph builders.

Production applications

DOM and virtual DOM (React)

The DOM is a tree; React’s reconciliation diffs two virtual DOM trees. The general “minimum edit distance between trees” problem is O(n³)¹⁸; React shaves it to O(n) with two heuristics, lifted directly from the official docs:

1. Two elements of different types produce different trees — React tears the old subtree down rather than diffing across the boundary.
2. Sibling elements with stable key props are matched by key across renders; without keys, React falls back to index-based matching, which thrashes when list order changes.

That’s why missing or unstable keys cause “lost focus / scroll position when a row reorders” — the DOM nodes are correct, but they’re now associated with different React fibers.

File systems

Modern file systems use trees at two levels: directory hierarchies as logical trees, and on-disk indexes as B/B+ trees or hashed variants¹³.

• Directory entries → inode numbers map names to metadata; ext4 indexes large directories with HTree (a hashed B-tree variant).
• NTFS, HFS+, Btrfs, XFS use B-trees / B+ trees for directory indexes and on-disk metadata.
• Dentry cache in the Linux VFS layer caches resolved path components so repeated lookups don’t replay the on-disk traversal.

Build and package systems

Maven, Gradle, npm, cargo, pip, Bazel, and Buck all model their build graph as a DAG and run topological sort on it. Gradle’s two-phase resolution¹⁹ is representative:

1. Graph resolution: build the DAG of declared and transitive dependencies.
2. Artifact resolution: fetch files for every resolved component.

The topological order both forces correct compile order and reveals the parallelism — every group of zero-in-degree tasks is independent and can be scheduled across cores.

Database indexes

B+ trees dominate database indexing because they minimise page fetches under realistic working-set sizes. A binary index of 1 million keys is ~20 levels deep; a B+ tree with fanout ~100 is 3 levels deep — and on a large table that often means 3 page reads rather than 20, the difference between sub-millisecond lookup and disk-bound query¹⁰¹¹.

Network routing

The Linux kernel’s IPv4 forwarding table is an LC-trie (fib_trie)¹⁵. Longest-prefix-match descents stop early thanks to path and level compression, keeping per-packet routing decisions in CPU-cache time.

Social networks

Friend graphs use BFS for the “n-th degree” queries that power “people you may know” panels, and personalised PageRank for ranking. Mutual-connections heuristics fall out as a one-step BFS combined with set intersection — no special data structure required, just an adjacency list.

Complexity reference

Tree operations

Graph operations by representation

Algorithm complexity

Practical takeaways

1. Pick the tree by workload, not by familiarity. AVL for read-heavy in-memory dictionaries, red-black as the safe default (it’s what every standard library shipped), B+ trees the moment data lives on disk or SSD, tries and their compressed variants for prefix-keyed problems.
2. Default to adjacency lists with hash sets. Matrices only earn their O(V²) cost on dense graphs or in algorithms (Floyd-Warshall) that exploit the contiguous layout.
3. DFS for “explore one branch fully”, BFS for “shortest path / nearest first”. Iterate, don’t recurse, when graphs may be deeper than a few thousand nodes.
4. Three-colour DFS for directed cycle detection, parent-tracking DFS for undirected. The two-state version that works in undirected graphs silently misses cycles in directed ones.
5. Negative weights → Bellman-Ford, otherwise Dijkstra. Don’t try to retrofit Dijkstra; the greedy invariant breaks the moment an edge can be negative.
6. Path-compressed union-find is effectively O(1). Reach for it any time the question is “are these in the same set?” — Kruskal, percolation, dynamic connectivity, dynamic equivalence classes.

Appendix

Prerequisites

• Big O notation and amortised analysis
• Recursion and iteration
• Arrays, hash maps, stacks, queues
• Comfortable reading TypeScript / pseudocode

Terminology

• BST (Binary Search Tree): binary tree with the in-order key invariant.
• AVL tree: self-balancing BST keeping balance factor in {-1, 0, +1}.
• Red-black tree: self-balancing BST using node colouring; the standard-library default.
• B-tree / B+ tree: multi-way trees designed for paged storage; B+ trees keep all values at the leaf level for cheap range scans.
• Trie / radix tree / LC-trie: prefix trees with progressively more aggressive compression.
• DAG: directed graph with no directed cycle.
• DFS / BFS: depth-first / breadth-first traversals.
• Topological order: linearisation of a DAG respecting edge direction.
• Union-Find / DSU: disjoint-set data structure with near-O(1) amortised operations.

References