Trees and Graphs: Traversals and Applications

Hierarchical and networked data structures that underpin file systems, databases, build tools, and routing. This guide covers tree variants (BST, AVL, Red-Black, B-trees, tries), graph representations (adjacency matrix vs list), traversal algorithms (DFS, BFS), and key algorithms (cycle detection, topological sort, shortest paths). Focus on design trade-offs and when to choose each structure.

Abstract

Trees and graphs share a fundamental property: nodes connected by edges. The distinction lies in structure constraints—trees enforce hierarchy (single parent, no cycles), while graphs allow arbitrary connections.

Core mental model:

• Tree variants optimize different access patterns: AVL for search-heavy workloads (stricter balance = fewer comparisons), Red-Black for write-heavy workloads (fewer rotations), B-trees for disk I/O (multiple keys per node = fewer seeks), tries for prefix operations (shared prefixes = O(key length) search)
• Graph representation is a space-time trade-off: Adjacency matrices give O(1) edge lookup but O(V²) space; adjacency lists give O(V+E) space but O(degree) edge lookup. Choose based on graph density.
• Traversal choice follows from problem structure: DFS uses a stack and explores deeply first—ideal for cycle detection, topological sort, and backtracking. BFS uses a queue and explores level-by-level—ideal for shortest paths in unweighted graphs.
• Union-Find enables near-O(1) connectivity queries through path compression and union by rank, making it the go-to structure for dynamic connectivity and Kruskal’s MST.

Tree Fundamentals

Binary Search Tree (BST)

A BST maintains the invariant: left subtree values < node < right subtree values. This enables O(log n) search, insertion, and deletion—when balanced.

The problem: Without balancing, insertions in sorted order create a linear chain. A BST of n elements inserted in ascending order degenerates to a linked list with O(n) operations.

3 collapsed lines
1
// BST node structure
2
interface BSTNode<T> {
3
  value: T
4
  left: BSTNode<T> | null
5
  right: BSTNode<T> | null
6
}
7

8
// Worst case: sorted insertions create O(n) height
9
// insert(1), insert(2), insert(3), insert(4)
10
// Results in:
11
//   1
12
//    \
13
//     2
14
//      \
15
//       3
16
//        \
17
//         4
18

19
// Solution: self-balancing trees (AVL, Red-Black)

AVL Trees: Strict Balance for Search-Heavy Workloads

AVL trees (Adelson-Velsky and Landis, 1962) were the first self-balancing BSTs. The invariant: for every node, the height difference between left and right subtrees (balance factor) must be -1, 0, or +1.

Design rationale: Strict balancing minimizes tree height, guaranteeing O(log n) operations. The trade-off is more rotations during modifications.

When to use: Read-heavy workloads where search performance matters more than write throughput. Database indexes with infrequent updates.

Rotation mechanics: After insertion or deletion, if balance factor becomes ±2, perform single or double rotations to restore balance. Four cases: Left-Left, Right-Right (single rotation), Left-Right, Right-Left (double rotation).

Red-Black Trees: Looser Balance for Write-Heavy Workloads

Red-Black trees (Guibas and Sedgewick, 1978) use node coloring instead of strict height balance. Five invariants:

1. Every node is red or black
2. Root is black
3. Leaves (NIL) are black
4. Red nodes have black children
5. All paths from node to descendant leaves have equal black nodes

Design rationale: Looser balance (height can be up to 2× optimal) means fewer rotations during modifications. Maximum 2 rotations per insertion, 3 per deletion.

When to use: Write-heavy workloads. System-level data structures where modification frequency is high.

Real-world usage: Java TreeMap, C++ std::map, Linux kernel’s Completely Fair Scheduler (CFS).

AVL vs Red-Black: The Trade-off

B-Trees: Disk I/O Optimization

Binary trees are inefficient for disk storage: each node access requires a disk seek (~10ms latency). With millions of nodes, tree traversal becomes I/O-bound.

Design rationale: B-trees increase the branching factor. Each node contains multiple keys (typically sized to fit a disk page, 4-16KB), reducing tree height and disk seeks.

A B-tree of order m:

• Each node has at most m children
• Each node (except root) has at least ⌈m/2⌉ children
• All leaves are at the same depth

B+ tree variant: Internal nodes contain only keys for routing; all data lives in leaf nodes, which are linked for efficient range scans. Used by most databases.

Real-world usage: SQLite, PostgreSQL, MySQL indexes. File systems: NTFS, HFS+, ext4, Btrfs.

2 collapsed lines
1
// B-tree node structure (simplified)
2
interface BTreeNode<K, V> {
3
  keys: K[] // Up to m-1 keys
4
  children: BTreeNode<K, V>[] // Up to m children
5
  isLeaf: boolean
6
}
7

8
// Example: B-tree of order 4 (up to 3 keys, 4 children per node)
9
// A single node can store keys [10, 20, 30]
10
// Children partition the key space:
11
// [-∞, 10), [10, 20), [20, 30), [30, +∞)
12

13
// Disk optimization: one node = one disk page
14
// Tree of 1M keys with order 100: height ≤ 3
1 collapsed line
15
// Only 3 disk reads for any lookup

Tries: Prefix-Optimized Search

Tries (prefix trees) organize strings by shared prefixes. Each edge represents a character; paths from root to marked nodes spell complete strings.

Design rationale: Exploit prefix sharing. Looking up “prefix” in a trie of 1M words takes O(6) operations—independent of dictionary size.

Trade-off: Higher memory than hash tables (each character requires a node or edge), but enables prefix queries that hash tables cannot support.

When to use:

• Autocomplete (find all strings with prefix)
• Spell checking
• IP routing (longest prefix matching)
• T9 predictive text

Complexity: O(L) for search, insert, delete—where L is key length, not dictionary size.

Graph Representations

Graphs model relationships without hierarchical constraints. The choice of representation determines performance for different operations.

Adjacency Matrix

A V×V matrix where matrix[i][j] indicates the edge from vertex i to j (1/0 for unweighted, weight value for weighted).

2 collapsed lines
1
// Adjacency matrix representation
2
class GraphMatrix {
3
  private matrix: number[][]
4

5
  constructor(vertices: number) {
6
    this.matrix = Array.from({ length: vertices }, () => Array(vertices).fill(0))
7
  }
8

9
  addEdge(u: number, v: number, weight = 1): void {
10
    this.matrix[u][v] = weight
11
    // For undirected: this.matrix[v][u] = weight;
12
  }
13

14
  hasEdge(u: number, v: number): boolean {
15
    return this.matrix[u][v] !== 0 // O(1)
16
  }
17
}

Operations:

• Edge lookup: O(1)
• Add/remove edge: O(1)
• Find neighbors: O(V)—must scan entire row
• Space: O(V²)—always, regardless of edge count

When to use: Dense graphs where E ≈ V², frequent edge existence checks, small graphs where V² is acceptable.

Adjacency List

Array or map of vertices, each storing a list of adjacent vertices.

2 collapsed lines
1
// Adjacency list representation
2
class GraphList {
3
  private adj: Map<number, Set<number>>
4

5
  constructor() {
6
    this.adj = new Map()
7
  }
8

9
  addEdge(u: number, v: number): void {
10
    if (!this.adj.has(u)) this.adj.set(u, new Set())
11
    this.adj.get(u)!.add(v)
12
    // For undirected: add reverse edge
13
  }
14

15
  hasEdge(u: number, v: number): boolean {
16
    return this.adj.get(u)?.has(v) ?? false // O(1) with Set
17
  }
18

19
  neighbors(u: number): number[] {
3 collapsed lines
20
    return [...(this.adj.get(u) ?? [])] // O(degree)
21
  }
22
}

Operations:

• Edge lookup: O(degree) with list, O(1) with Set/hash
• Add edge: O(1)
• Remove edge: O(degree) with list, O(1) with Set
• Find neighbors: O(degree)—exactly the neighbors, no scanning
• Space: O(V + E)

When to use: Sparse graphs (E << V²), most real-world graphs (social networks, road networks), memory-constrained environments.

Representation Trade-offs

Rule of thumb: If E < V²/64, adjacency list is more space-efficient. Most real graphs are sparse.

Traversal Algorithms

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking. Uses a stack (explicit or call stack).

3 collapsed lines
1
// DFS - Recursive (uses call stack)
2
function dfsRecursive(graph: Map<number, number[]>, start: number, visited = new Set<number>()): void {
3
  if (visited.has(start)) return
4
  visited.add(start)
5

6
  // Process node here
7
  console.log(start)
8

9
  for (const neighbor of graph.get(start) ?? []) {
10
    dfsRecursive(graph, neighbor, visited)
11
  }
12
}
13

14
// DFS - Iterative (explicit stack)
15
function dfsIterative(graph: Map<number, number[]>, start: number): void {
16
  const visited = new Set<number>()
17
  const stack = [start]
18

19
  while (stack.length > 0) {
20
    const node = stack.pop()!
21
    if (visited.has(node)) continue
22
    visited.add(node)
23

24
    // Process node here
25
    console.log(node)
26

27
    // Add neighbors in reverse for same order as recursive
28
    const neighbors = graph.get(node) ?? []
29
    for (let i = neighbors.length - 1; i >= 0; i--) {
6 collapsed lines
30
      if (!visited.has(neighbors[i])) {
31
        stack.push(neighbors[i])
32
      }
33
    }
34
  }
35
}

Tree DFS variants:

• Preorder (root-left-right): Process node before children. Use: tree copying, serialization.
• Inorder (left-root-right): Process node between children. Use: BST sorted traversal.
• Postorder (left-right-root): Process node after children. Use: tree deletion, expression evaluation, dependency resolution.

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

When to use: Cycle detection, topological sorting, path finding in mazes, detecting connected components.

Breadth-First Search (BFS)

BFS explores all neighbors at current depth before moving deeper. Uses a queue.

3 collapsed lines
1
// BFS - Level-order traversal
2
function bfs(graph: Map<number, number[]>, start: number): void {
3
  const visited = new Set<number>()
4
  const queue: number[] = [start]
5
  visited.add(start)
6

7
  while (queue.length > 0) {
8
    const node = queue.shift()! // Dequeue front
9

10
    // Process node here
11
    console.log(node)
12

13
    for (const neighbor of graph.get(node) ?? []) {
14
      if (!visited.has(neighbor)) {
15
        visited.add(neighbor)
16
        queue.push(neighbor)
17
      }
18
    }
19
  }
20
}

Complexity: O(V + E) time, O(V) space for visited set + queue.

Key property: BFS finds shortest path in unweighted graphs. The first time BFS reaches a node, it’s via the shortest path (in terms of edge count).

When to use: Shortest path (unweighted), level-order traversal, finding nearest neighbors, web crawling by depth.

DFS vs BFS: Choosing the Right Traversal

Memory consideration: In wide, shallow graphs, DFS uses less memory. In deep, narrow graphs, BFS uses less memory. For balanced trees, both use O(log n).

Cycle Detection

Undirected Graphs: DFS with Parent Tracking

In undirected graphs, an edge to a visited node that isn’t the parent indicates a cycle.

3 collapsed lines
1
// Cycle detection in undirected graph
2
function hasCycleUndirected(graph: Map<number, number[]>, vertices: number[]): boolean {
3
  const visited = new Set<number>()
4

5
  function dfs(node: number, parent: number | null): boolean {
6
    visited.add(node)
7

8
    for (const neighbor of graph.get(node) ?? []) {
9
      if (!visited.has(neighbor)) {
10
        if (dfs(neighbor, node)) return true
11
      } else if (neighbor !== parent) {
12
        // Visited and not parent = cycle
13
        return true
14
      }
15
    }
16
    return false
17
  }
18

19
  // Check all components
20
  for (const v of vertices) {
21
    if (!visited.has(v) && dfs(v, null)) return true
22
  }
23
  return false
24
}

Directed Graphs: Three-Color DFS

In directed graphs, use three states: unvisited (white), currently visiting (gray), fully visited (black). A back edge to a gray node indicates a cycle.

3 collapsed lines
1
// Cycle detection in directed graph (three-color algorithm)
2
enum Color {
3
  WHITE,
4
  GRAY,
5
  BLACK,
6
}
7

8
function hasCycleDirected(graph: Map<number, number[]>, vertices: number[]): boolean {
9
  const color = new Map<number, Color>()
10
  vertices.forEach((v) => color.set(v, Color.WHITE))
11

12
  function dfs(node: number): boolean {
13
    color.set(node, Color.GRAY) // Currently visiting
14

15
    for (const neighbor of graph.get(node) ?? []) {
16
      if (color.get(neighbor) === Color.GRAY) {
17
        // Back edge to node in current path = cycle
18
        return true
19
      }
20
      if (color.get(neighbor) === Color.WHITE) {
21
        if (dfs(neighbor)) return true
22
      }
23
    }
24

25
    color.set(node, Color.BLACK) // Fully visited
26
    return false
27
  }
28

29
  for (const v of vertices) {
4 collapsed lines
30
    if (color.get(v) === Color.WHITE && dfs(v)) return true
31
  }
32
  return false
33
}

Why three colors? In directed graphs, revisiting a node isn’t inherently a cycle—it could be via a different path. Only revisiting a node in the current DFS path (gray) indicates a cycle.

Topological Sorting

Topological sort produces a linear ordering of DAG (Directed Acyclic Graph) vertices where for every edge u→v, u appears before v. Essential for dependency resolution.

Kahn’s Algorithm (BFS-based)

Process vertices with no incoming edges first, then update in-degrees.

3 collapsed lines
1
// Kahn's algorithm - BFS-based topological sort
2
function topologicalSortKahn(graph: Map<number, number[]>, vertices: number[]): number[] | null {
3
  // Calculate in-degrees
4
  const inDegree = new Map<number, number>()
5
  vertices.forEach((v) => inDegree.set(v, 0))
6

7
  for (const [_, neighbors] of graph) {
8
    for (const neighbor of neighbors) {
9
      inDegree.set(neighbor, (inDegree.get(neighbor) ?? 0) + 1)
10
    }
11
  }
12

13
  // Queue vertices with in-degree 0
14
  const queue = vertices.filter((v) => inDegree.get(v) === 0)
15
  const result: number[] = []
16

17
  while (queue.length > 0) {
18
    const node = queue.shift()!
19
    result.push(node)
20

21
    for (const neighbor of graph.get(node) ?? []) {
22
      const newDegree = inDegree.get(neighbor)! - 1
23
      inDegree.set(neighbor, newDegree)
24
      if (newDegree === 0) {
25
        queue.push(neighbor)
26
      }
27
    }
28
  }
29

30
  // If not all vertices processed, cycle exists
31
  return result.length === vertices.length ? result : null
32
}

Advantage: Naturally detects cycles—if result doesn’t include all vertices, a cycle exists.

DFS-based Approach

Add vertices to result after visiting all descendants (postorder), then reverse.

3 collapsed lines
1
// DFS-based topological sort
2
function topologicalSortDFS(graph: Map<number, number[]>, vertices: number[]): number[] | null {
3
  const visited = new Set<number>()
4
  const inStack = new Set<number>() // For cycle detection
5
  const result: number[] = []
6

7
  function dfs(node: number): boolean {
8
    if (inStack.has(node)) return false // Cycle
9
    if (visited.has(node)) return true
10

11
    visited.add(node)
12
    inStack.add(node)
13

14
    for (const neighbor of graph.get(node) ?? []) {
15
      if (!dfs(neighbor)) return false
16
    }
17

18
    inStack.delete(node)
19
    result.push(node) // Postorder
20
    return true
21
  }
22

23
  for (const v of vertices) {
24
    if (!visited.has(v) && !dfs(v)) return null
25
  }
26

27
  return result.reverse()
28
}

Real-world applications:

• Build systems (Maven, Gradle, Make): Compile dependencies before dependents
• Package managers (npm, pip): Install dependencies in correct order
• Task scheduling: Execute prerequisites before dependent tasks
• Database migrations: Apply schema changes in dependency order
• Course scheduling: Prerequisites before advanced courses

Shortest Path Algorithms

BFS for Unweighted Graphs

BFS inherently finds shortest paths when all edges have equal weight (or weight = 1).

3 collapsed lines
1
// Shortest path in unweighted graph using BFS
2
function shortestPath(graph: Map<number, number[]>, start: number, end: number): number[] | null {
3
  const visited = new Set<number>()
4
  const parent = new Map<number, number>()
5
  const queue = [start]
6
  visited.add(start)
7

8
  while (queue.length > 0) {
9
    const node = queue.shift()!
10
    if (node === end) {
11
      // Reconstruct path
12
      const path = [end]
13
      let current = end
14
      while (parent.has(current)) {
15
        current = parent.get(current)!
16
        path.unshift(current)
17
      }
18
      return path
19
    }
20

21
    for (const neighbor of graph.get(node) ?? []) {
22
      if (!visited.has(neighbor)) {
23
        visited.add(neighbor)
24
        parent.set(neighbor, node)
6 collapsed lines
25
        queue.push(neighbor)
26
      }
27
    }
28
  }
29
  return null // No path exists
30
}

Dijkstra’s Algorithm (Non-negative Weights)

Greedy algorithm using a priority queue. Always processes the vertex with smallest known distance.

Invariant: When a vertex is dequeued, its distance is final.

Limitation: Cannot handle negative edge weights—the greedy assumption breaks.

Complexity: O(E + V log V) with binary heap, O(E + V log V) with Fibonacci heap.

Use cases: GPS navigation, network routing (OSPF protocol).

Bellman-Ford (Handles Negative Weights)

Relaxes all edges V-1 times. Can detect negative cycles.

Algorithm:

1. Initialize distances (source = 0, others = ∞)
2. Repeat V-1 times: for each edge (u,v), if dist[u] + weight < dist[v], update dist[v]
3. Check for negative cycles: if any edge can still be relaxed, negative cycle exists

Complexity: O(V·E)—slower than Dijkstra but handles negative weights.

Use cases: Routing protocols (RIP), arbitrage detection in currency exchange.

Algorithm Selection

Union-Find (Disjoint Set Union)

Union-Find manages a collection of disjoint sets, answering “are x and y connected?” in near-constant time.

Operations

• MakeSet(x): Create a singleton set containing x
• Find(x): Return the representative (root) of x’s set
• Union(x, y): Merge the sets containing x and y

Optimizations

Path compression: During Find, make every node point directly to the root.

3 collapsed lines
1
// Union-Find with path compression and union by rank
2
class UnionFind {
3
  private parent: Map<number, number>
4
  private rank: Map<number, number>
5

6
  constructor(elements: number[]) {
7
    this.parent = new Map()
8
    this.rank = new Map()
9
    elements.forEach((e) => {
10
      this.parent.set(e, e) // Each element is its own parent
11
      this.rank.set(e, 0)
12
    })
13
  }
14

15
  find(x: number): number {
16
    if (this.parent.get(x) !== x) {
17
      // Path compression: point directly to root
18
      this.parent.set(x, this.find(this.parent.get(x)!))
19
    }
20
    return this.parent.get(x)!
21
  }
22

23
  union(x: number, y: number): void {
24
    const rootX = this.find(x)
25
    const rootY = this.find(y)
26
    if (rootX === rootY) return
27

28
    // Union by rank: attach smaller tree to larger
29
    const rankX = this.rank.get(rootX)!
30
    const rankY = this.rank.get(rootY)!
31
    if (rankX < rankY) {
32
      this.parent.set(rootX, rootY)
33
    } else if (rankX > rankY) {
34
      this.parent.set(rootY, rootX)
10 collapsed lines
35
    } else {
36
      this.parent.set(rootY, rootX)
37
      this.rank.set(rootX, rankX + 1)
38
    }
39
  }
40

41
  connected(x: number, y: number): boolean {
42
    return this.find(x) === this.find(y)
43
  }
44
}

Union by rank: Attach the shorter tree to the taller one, preventing worst-case linear chains.

Combined complexity: O(α(n)) per operation, where α is the inverse Ackermann function. For all practical purposes, α(n) ≤ 4, making operations effectively O(1).

Use cases:

• Kruskal’s MST algorithm
• Cycle detection in undirected graphs
• Connected components
• Network connectivity (social graphs, computer networks)
• Image segmentation

Production Applications

DOM and Virtual DOM (React)

The DOM (Document Object Model) is a tree where each node represents an HTML element. React’s reconciliation algorithm diffs virtual DOM trees.

The O(n³) problem: A general algorithm to transform one tree into another with minimum edit operations requires O(n³) time—prohibitive for UI updates.

React’s heuristics (from React documentation):

1. Elements of different types produce different trees (full rebuild)
2. Elements of same type with different key props are different instances
3. Same type, same key → minimal diff

Result: O(n) diffing with well-chosen keys. Without keys, React falls back to index-based matching, causing unnecessary re-renders when list order changes.

File Systems

File systems use tree structures for directory hierarchies and B-trees for efficient storage.

Inode-based structure (Linux, macOS):

• Directory entries map filenames to inode numbers
• Inodes store metadata and block pointers
• Multi-level indexing (direct, indirect, double indirect) for large files

Dentry cache: Kernel caches directory lookups, avoiding repeated disk reads for path traversal.

Dependency Resolution (Build Systems)

Gradle, Maven, and npm model dependencies as DAGs and use topological sorting.

Gradle’s two-phase resolution:

1. Graph resolution: Build DAG of dependencies and transitive dependencies
2. Artifact resolution: Fetch files for resolved components

Topological sort determines build order and enables parallel execution of independent tasks.

Database Indexing

B-trees are the standard for database indexes because they minimize disk I/O.

Why B-trees: A binary tree with 1M keys has height ~20. A B-tree of order 100 with 1M keys has height ~3. Each level requires a disk seek—reducing seeks by 85% dramatically improves query performance.

Social Networks

Social graphs use graph algorithms for friend recommendations and connectivity.

Common algorithms:

• Common neighbors: Suggest users with most mutual connections
• BFS: Find 1st/2nd/3rd degree connections
• Personalized PageRank: User-specific importance ranking

Complexity Reference

Tree Operations

Graph Operations by Representation

Algorithm Complexity

Conclusion

Trees and graphs model hierarchical and networked relationships respectively. The key engineering decisions are:

1. Tree variant selection: Match the data structure to access patterns—AVL for reads, Red-Black for writes, B-trees for disk, tries for prefixes.

2. Graph representation: Adjacency lists for sparse graphs (most real-world cases), matrices only for dense graphs with frequent edge lookups.

3. Traversal choice: DFS for problems requiring path exploration (cycles, dependencies), BFS for shortest path and level-order problems.

4. Union-Find for connectivity: Near-O(1) operations make it the optimal choice for dynamic connectivity problems.

These structures underpin critical systems—file systems, databases, build tools, social networks, and routing. Understanding their trade-offs enables informed architectural decisions.

Appendix

Prerequisites

• Big O notation and complexity analysis
• Recursion and iteration
• Basic data structures (arrays, linked lists, hash maps)
• Stack and queue operations

Terminology

• BST (Binary Search Tree): Binary tree where left < root < right
• AVL tree: Self-balancing BST with strict height balance (difference ≤ 1)
• Red-Black tree: Self-balancing BST using node coloring for looser balance
• B-tree: Multi-way search tree optimized for disk I/O
• Trie (prefix tree): Tree structure for string storage with shared prefixes
• DAG (Directed Acyclic Graph): Directed graph with no cycles
• DFS (Depth-First Search): Traversal exploring deep before wide
• BFS (Breadth-First Search): Traversal exploring level by level
• Topological sort: Linear ordering of DAG vertices respecting edge direction
• Union-Find: Data structure for disjoint set operations with near-O(1) complexity

Summary

• Tree variants optimize different dimensions: AVL for search, Red-Black for writes, B-trees for disk, tries for prefixes
• Graph representation choice depends on density: Adjacency list for sparse (E << V²), matrix for dense
• DFS uses stack, BFS uses queue: Choose based on problem structure—depth exploration vs level-order
• Cycle detection: Parent tracking for undirected, three-color for directed graphs
• Topological sort requires DAG: Kahn’s (BFS) or DFS-based, both O(V + E)
• Union-Find achieves near-O(1) through path compression and union by rank

References

• Introduction to Algorithms (CLRS) - Chapters on BSTs, Red-Black trees, B-trees, graph algorithms
• Red-Black Tree - Wikipedia - Properties and implementation
• AVL Tree - Wikipedia - Balance factors and rotations
• B-tree - Wikipedia - Structure and disk optimization rationale
• SQLite B-Tree Module - Production B-tree implementation
• React Reconciliation - DOM diffing algorithm and heuristics
• Trie - Wikipedia - Prefix tree structure and applications
• Disjoint Set Union - CP-Algorithms - Union-Find optimizations
• Dijkstra vs Bellman-Ford - Baeldung - Shortest path algorithm comparison
• Gradle Dependency Resolution - Build system graph handling