You know binary trees. You can insert into a BST, run an in-order traversal, and calculate the height of a tree in your sleep. That's a solid foundation. But it's time to leave the nursery. The data structures in this article are the ones that power the real world. **AVL trees** keep databases fast when data arrives in the worst possible order. **Tries** are the reason your phone can suggest words before you finish typing them. **Heaps** are why your operating system knows which process to run next. **Graphs** are the mathematical backbone of GPS navigation, social networks, the internet itself, and basically every interesting system you've ever interacted with. This is where data structures stop being academic exercises and start being engineering tools. Every structure here solves a specific, important problem — and understanding them gives you superpowers in both system design and coding interviews. > If Trees 101 taught you how to walk, this article teaches you how to fly. Buckle up. By the end of this deep dive, you'll: - Understand **self-balancing trees** (AVL and Red-Black) and why they exist - Build a complete **Trie** for autocomplete and prefix search - Implement a **MinHeap** and **Priority Queue** from scratch - Know the difference between **adjacency lists** and **adjacency matrices** - Implement **Dijkstra's** and **Bellman-Ford** shortest path algorithms - Master **topological sort** for dependency resolution - Build a **Union-Find** data structure with path compression - Detect **cycles** in both directed and undirected graphs - Understand **minimum spanning trees** (Kruskal's and Prim's) - Have a complete **cheat sheet** for when to use what Let's dive deep. --- ## Self-Balancing Trees ### Why Balance Matters In Trees 101, we built a Binary Search Tree and saw that operations like search, insert, and delete are **O(h)** where h is the height of the tree. For a **balanced** BST, h = log n, giving us beautiful O(log n) performance. But here's the problem. Insert the values `1, 2, 3, 4, 5` into a BST in that order: ``` 1 \ 2 \ 3 \ 4 \ 5 ``` That's not a tree — that's a **linked list** wearing a tree costume. The height is n, not log n, and every operation degrades to **O(n)**. Now compare that with a balanced tree holding the same values: ``` 3 / \ 2 4 / \ 1 5 ``` Height = 2. Searching for any value takes at most 2 comparisons. That's the difference between O(n) and O(log n) — and for a million elements, that's the difference between **1,000,000 operations** and **20 operations**. > **The core problem**: A regular BST has no guarantees about its shape. If data arrives in sorted or nearly-sorted order (which happens *all the time* in real applications), performance collapses. Self-balancing trees solve this by automatically restructuring themselves after every insertion and deletion. --- ### AVL Trees **AVL trees** (named after inventors **A**delson-**V**elsky and **L**andis, 1962) were the first self-balancing BST ever invented. The idea is elegant: after every insertion or deletion, check if the tree is still balanced. If it's not, fix it with **rotations**. #### The Balance Factor Every node in an AVL tree has a **balance factor**: ``` Balance Factor = height(left subtree) - height(right subtree) ``` The AVL invariant is simple: **the balance factor of every node must be -1, 0, or 1**. If any node violates this after an insert or delete, we rotate to fix it. ``` 30 (BF = 1) 30 (BF = 2) ← VIOLATION! / \ / \ 20 40 20 40 / / 10 10 / 5 ← this insertion broke the balance ``` #### The Four Rotations There are exactly four cases to handle, depending on where the imbalance occurs. **Case 1: Left-Left (LL) — Right Rotation** The imbalance is in the left child's left subtree: ``` Before (LL imbalance): After Right Rotation: 30 20 / / \ 20 10 30 / 10 Steps: 1. 20 becomes the new root 2. 30 becomes 20's right child 3. 20's old right child (if any) becomes 30's left child ``` **Case 2: Right-Right (RR) — Left Rotation** The mirror of LL — the imbalance is in the right child's right subtree: ``` Before (RR imbalance): After Left Rotation: 10 20 \ / \ 20 10 30 \ 30 Steps: 1. 20 becomes the new root 2. 10 becomes 20's left child 3. 20's old left child (if any) becomes 10's right child ``` **Case 3: Left-Right (LR) — Left Rotation then Right Rotation** The imbalance is in the left child's right subtree. A single rotation won't fix this — we need two: ``` Before (LR imbalance): After Left Rotate(10): After Right Rotate(30): 30 30 20 / / / \ 10 20 10 30 \ / 20 10 Steps: 1. Left-rotate the left child (10) to convert LR → LL 2. Right-rotate the root (30) to fix the LL imbalance ``` **Case 4: Right-Left (RL) — Right Rotation then Left Rotation** The mirror of LR: ``` Before (RL imbalance): After Right Rotate(30): After Left Rotate(10): 10 10 20 \ \ / \ 30 20 10 30 / \ 20 30 Steps: 1. Right-rotate the right child (30) to convert RL → RR 2. Left-rotate the root (10) to fix the RR imbalance ``` #### TypeScript Implementation ```typescript class AVLNode { value: T; left: AVLNode | null = null; right: AVLNode | null = null; height: number = 1; constructor(value: T) { this.value = value; } } class AVLTree { root: AVLNode | null = null; private getHeight(node: AVLNode | null): number { return node ? node.height : 0; } private getBalanceFactor(node: AVLNode): number { return this.getHeight(node.left) - this.getHeight(node.right); } private updateHeight(node: AVLNode): void { node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right)); } private rotateRight(y: AVLNode): AVLNode { const x = y.left!; const T2 = x.right; x.right = y; y.left = T2; this.updateHeight(y); this.updateHeight(x); return x; } private rotateLeft(x: AVLNode): AVLNode { const y = x.right!; const T2 = y.left; y.left = x; x.right = T2; this.updateHeight(x); this.updateHeight(y); return y; } private rebalance(node: AVLNode): AVLNode { this.updateHeight(node); const bf = this.getBalanceFactor(node); // Left-heavy if (bf > 1) { if (this.getBalanceFactor(node.left!) < 0) { // Left-Right case node.left = this.rotateLeft(node.left!); } // Left-Left case return this.rotateRight(node); } // Right-heavy if (bf < -1) { if (this.getBalanceFactor(node.right!) > 0) { // Right-Left case node.right = this.rotateRight(node.right!); } // Right-Right case return this.rotateLeft(node); } return node; } insert(value: T): void { this.root = this.insertNode(this.root, value); } private insertNode(node: AVLNode | null, value: T): AVLNode { if (!node) return new AVLNode(value); if (value < node.value) { node.left = this.insertNode(node.left, value); } else if (value > node.value) { node.right = this.insertNode(node.right, value); } else { return node; // duplicates not allowed } return this.rebalance(node); } search(value: T): boolean { let current = this.root; while (current) { if (value === current.value) return true; current = value < current.value ? current.left : current.right; } return false; } private getMinNode(node: AVLNode): AVLNode { while (node.left) node = node.left; return node; } delete(value: T): void { this.root = this.deleteNode(this.root, value); } private deleteNode(node: AVLNode | null, value: T): AVLNode | null { if (!node) return null; if (value < node.value) { node.left = this.deleteNode(node.left, value); } else if (value > node.value) { node.right = this.deleteNode(node.right, value); } else { if (!node.left) return node.right; if (!node.right) return node.left; const successor = this.getMinNode(node.right); node.value = successor.value; node.right = this.deleteNode(node.right, successor.value); } return this.rebalance(node); } } // Usage const avl = new AVLTree(); [1, 2, 3, 4, 5, 6, 7].forEach((n) => avl.insert(n)); // Despite inserting in sorted order, the tree stays balanced: // 4 // / \ // 2 6 // / \ / \ // 1 3 5 7 ``` #### AVL Tree Complexity | Operation | Time Complexity | Space Complexity | |-----------|----------------|-----------------| | Search | O(log n) | O(1) | | Insert | O(log n) | O(log n) stack | | Delete | O(log n) | O(log n) stack | The height of an AVL tree is always between **log₂(n)** and **1.44 × log₂(n)**. That's a strict guarantee — no degenerate cases, ever. #### When to Use AVL Trees AVL trees are ideal when **reads vastly outnumber writes**. They maintain stricter balance than Red-Black trees (height ≤ 1.44 log n vs ≤ 2 log n), which means faster lookups. The trade-off is that insertions and deletions are slightly slower because more rotations may be needed. **Use AVL when**: database indexes, in-memory dictionaries, any scenario where lookup speed is critical and modifications are less frequent. --- ### Red-Black Trees **Red-Black trees** are the other major self-balancing BST. They're used in Java's `TreeMap`, C++'s `std::map` and `std::set`, the Linux kernel's completely fair scheduler, and countless other systems. Where AVL trees enforce strict balance through height differences, Red-Black trees use a coloring scheme. Every node is either **red** or **black**, and the tree must satisfy these five properties: 1. Every node is either red or black 2. The root is always black 3. Every leaf (null/NIL) is considered black 4. If a node is red, both its children must be black (no two consecutive reds) 5. Every path from a node to any of its descendant NIL leaves contains the **same number of black nodes** (the "black height") ``` 13 (B) / \ 8 (R) 17 (R) / \ / \ 1(B) 11(B) 15(B) 25(B) \ \ \ 6(R) 16(R) 27(R) ``` **The mental model**: Red-Black trees are like a "relaxed" AVL tree. They allow slightly more imbalance (the longest path can be up to 2x the shortest path), but they require fewer rotations on average during insertions and deletions. This makes them better for workloads with frequent modifications. The full insertion and deletion algorithms for Red-Black trees involve multiple cases of recoloring and rotation. They're complex enough that implementing them from scratch in an interview would be unusual — but understanding the concept and trade-offs is important. #### AVL vs Red-Black: The Decision | Property | AVL Tree | Red-Black Tree | |----------|----------|---------------| | Balance strictness | Tighter (height ≤ 1.44 log n) | Looser (height ≤ 2 log n) | | Lookup speed | Faster (shorter height) | Slightly slower | | Insert/Delete speed | Slower (more rotations) | Faster (fewer rotations) | | Best for | Read-heavy workloads | Write-heavy or mixed workloads | | Used in | Database indexes, memory lookups | Language standard libraries, OS kernels | > **Bottom line**: If you need a self-balancing BST, use whatever your language provides. If you're implementing one for learning, AVL is more straightforward. If you're designing a standard library, Red-Black is the industry standard. --- ## Tries (Prefix Trees) ### What Is a Trie? A **trie** (pronounced "try," from re**trie**val) is a tree-like data structure designed for storing strings. Unlike a BST where each node holds a complete key, in a trie each node represents a **single character**, and the path from root to any node spells out a prefix. Tries are the data structure behind: - **Autocomplete** — type "hel" and get "hello," "help," "helmet" - **Spell checkers** — quickly determine if a word exists in a dictionary - **IP routing** — longest prefix matching in network routers - **T9 predictive text** — the old phone keyboard system - **Search engine suggestions** — Google's search bar as you type ### Why Not Just Use a Hash Map? A hash map can tell you if a word exists in O(1). But it can't efficiently answer "give me all words that start with 'pre'." A trie can do this naturally by traversing to the "pre" node and collecting all descendants — something that would require scanning every key in a hash map. ### Anatomy of a Trie Here's a trie containing the words: **"cat," "car," "card," "care," "do," "dog"**: ``` (root) / \ c d | | a o ★ / \ \ t★ r★ g ★ / \ d★ e★ ★ = end of word marker ``` Key observations: - The root is empty (it represents the empty prefix "") - Common prefixes share nodes ("car," "card," "care" all share c → a → r) - The ★ marker indicates that the path up to this node forms a complete word - "do" is a word (★ on 'o') AND a prefix of "dog" ### TypeScript Implementation ```typescript class TrieNode { children: Map = new Map(); isEndOfWord: boolean = false; } class Trie { root: TrieNode = new TrieNode(); insert(word: string): void { let current = this.root; for (const char of word) { if (!current.children.has(char)) { current.children.set(char, new TrieNode()); } current = current.children.get(char)!; } current.isEndOfWord = true; } search(word: string): boolean { const node = this.findNode(word); return node !== null && node.isEndOfWord; } startsWith(prefix: string): boolean { return this.findNode(prefix) !== null; } private findNode(str: string): TrieNode | null { let current = this.root; for (const char of str) { if (!current.children.has(char)) return null; current = current.children.get(char)!; } return current; } getAllWordsWithPrefix(prefix: string): string[] { const node = this.findNode(prefix); if (!node) return []; const results: string[] = []; this.collectWords(node, prefix, results); return results; } private collectWords( node: TrieNode, currentWord: string, results: string[] ): void { if (node.isEndOfWord) { results.push(currentWord); } for (const [char, child] of node.children) { this.collectWords(child, currentWord + char, results); } } delete(word: string): boolean { return this.deleteHelper(this.root, word, 0); } private deleteHelper( node: TrieNode, word: string, depth: number ): boolean { if (depth === word.length) { if (!node.isEndOfWord) return false; node.isEndOfWord = false; return node.children.size === 0; } const char = word[depth]; const child = node.children.get(char); if (!child) return false; const shouldDeleteChild = this.deleteHelper(child, word, depth + 1); if (shouldDeleteChild) { node.children.delete(char); return node.children.size === 0 && !node.isEndOfWord; } return false; } searchWithWildcard(pattern: string): boolean { return this.wildcardHelper(this.root, pattern, 0); } private wildcardHelper( node: TrieNode, pattern: string, index: number ): boolean { if (index === pattern.length) { return node.isEndOfWord; } const char = pattern[index]; if (char === '.') { for (const child of node.children.values()) { if (this.wildcardHelper(child, pattern, index + 1)) { return true; } } return false; } const child = node.children.get(char); if (!child) return false; return this.wildcardHelper(child, pattern, index + 1); } } // Usage const trie = new Trie(); ['cat', 'car', 'card', 'care', 'do', 'dog'].forEach((w) => trie.insert(w)); console.log(trie.search('car')); // true console.log(trie.search('ca')); // false (prefix, not a word) console.log(trie.startsWith('ca')); // true console.log(trie.getAllWordsWithPrefix('car')); // ['car', 'card', 'care'] console.log(trie.searchWithWildcard('c.r')); // true (matches 'car') console.log(trie.searchWithWildcard('d.g')); // true (matches 'dog') trie.delete('car'); console.log(trie.search('car')); // false console.log(trie.search('card')); // true (still exists) ``` ### Trie Complexity | Operation | Time Complexity | Space Complexity | |-----------|----------------|-----------------| | Insert | O(m) | O(m) where m = word length | | Search | O(m) | O(1) | | startsWith | O(m) | O(1) | | Delete | O(m) | O(1) | | Prefix search (all words) | O(m + k) | O(k) where k = total chars in results | **Space**: A trie's space usage depends on how many unique prefixes exist. In the worst case (no shared prefixes), it's O(n × m) where n is the number of words and m is the average length. In practice, shared prefixes compress the space significantly. **Space optimization**: **Compressed tries** (also called radix trees or Patricia trees) merge chains of single-child nodes into one node. Instead of c → a → t, you store "cat" in a single node. This dramatically reduces the node count for sparse tries. --- ## Heaps and Priority Queues ### What Is a Heap? A **heap** is a specialized **complete binary tree** that satisfies the **heap property**: - **Min-Heap**: Every parent is **less than or equal to** its children. The minimum element is at the root. - **Max-Heap**: Every parent is **greater than or equal to** its children. The maximum element is at the root. ``` Min-Heap: Max-Heap: 1 50 / \ / \ 3 5 30 40 / \ / \ / \ / 7 8 9 10 10 20 15 ``` **Critical distinction**: A heap is NOT a BST. In a BST, the left child is smaller and the right child is larger. In a heap, both children are larger (min-heap) or smaller (max-heap) than the parent, but there's **no ordering between siblings**. #### Why "Complete" Binary Tree? A complete binary tree fills every level from left to right, with the last level filled from the left. This property is critical because it means we can represent the tree as a **flat array** with no wasted space — no pointers, no null children, just indices. ### Array Representation This is the magic of heaps. We store the tree in an array, and navigate parent/child relationships with simple math: ``` Tree: 1 / \ 3 5 / \ / \ 7 8 9 10 Array: [1, 3, 5, 7, 8, 9, 10] Index: 0 1 2 3 4 5 6 ``` For any node at index **i**: | Relationship | Index Formula | |-------------|---------------| | Parent | `Math.floor((i - 1) / 2)` | | Left child | `2 * i + 1` | | Right child | `2 * i + 2` | Verify: node `3` is at index 1. Its parent is at `Math.floor((1-1)/2) = 0` → which is `1`. Its left child is at `2*1+1 = 3` → which is `7`. Its right child is at `2*1+2 = 4` → which is `8`. It all works. ### TypeScript MinHeap Implementation ```typescript class MinHeap { private heap: T[] = []; private compare: (a: T, b: T) => number; constructor(compareFn?: (a: T, b: T) => number) { this.compare = compareFn ?? ((a, b) => (a < b ? -1 : a > b ? 1 : 0)); } get size(): number { return this.heap.length; } peek(): T | undefined { return this.heap[0]; } insert(value: T): void { this.heap.push(value); this.bubbleUp(this.heap.length - 1); } extractMin(): T | undefined { if (this.heap.length === 0) return undefined; if (this.heap.length === 1) return this.heap.pop(); const min = this.heap[0]; this.heap[0] = this.heap.pop()!; this.bubbleDown(0); return min; } private bubbleUp(index: number): void { while (index > 0) { const parentIdx = Math.floor((index - 1) / 2); if (this.compare(this.heap[index], this.heap[parentIdx]) >= 0) break; [this.heap[index], this.heap[parentIdx]] = [ this.heap[parentIdx], this.heap[index], ]; index = parentIdx; } } private bubbleDown(index: number): void { const length = this.heap.length; while (true) { let smallest = index; const left = 2 * index + 1; const right = 2 * index + 2; if ( left < length && this.compare(this.heap[left], this.heap[smallest]) < 0 ) { smallest = left; } if ( right < length && this.compare(this.heap[right], this.heap[smallest]) < 0 ) { smallest = right; } if (smallest === index) break; [this.heap[index], this.heap[smallest]] = [ this.heap[smallest], this.heap[index], ]; index = smallest; } } static fromArray(arr: T[], compareFn?: (a: T, b: T) => number): MinHeap { const heap = new MinHeap(compareFn); heap.heap = [...arr]; for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) { heap.bubbleDown(i); } return heap; } } ``` #### How Insert Works (Bubble Up) When we insert a value, we add it to the end of the array (maintaining the complete tree shape), then "bubble it up" to its correct position: ``` Insert 2 into this min-heap: Step 1: Add to end Step 2: Bubble up (swap with 8) 1 1 / \ / \ 3 5 3 5 / \ / \ / \ / \ 7 8 9 10 7 2 9 10 / / 2 ← added here 8 Step 3: Bubble up (swap with 3) 1 / \ 2 5 / \ / \ 7 3 9 10 / 8 Done! 2 > 1, so it stays. ``` #### How ExtractMin Works (Bubble Down) To remove the minimum (root), we replace it with the last element, then "bubble it down": ``` Extract min from: Step 1: Replace root with last 1 8 / \ / \ 2 5 2 5 / \ / \ / \ / 7 3 9 10 7 3 9 / 8 Step 2: Bubble down (swap with 2) Step 3: Bubble down (swap with 3) 2 2 / \ / \ 8 5 3 5 / \ / / \ / 7 3 9 7 8 9 Done! 8 > both children, no more swaps needed... wait. 8 > 3, so swap. Now 8 has no children smaller. Done! ``` #### Building a Heap: O(n) vs O(n log n) There are two ways to build a heap from an array: 1. **Insert one by one**: Insert n elements, each taking O(log n) → **O(n log n)** total 2. **Heapify (Floyd's algorithm)**: Start from the last non-leaf node and bubble down → **O(n)** total The `fromArray` static method above uses Floyd's algorithm. It's O(n) because most nodes are near the bottom and only need to bubble down a short distance. The math works out beautifully — it's a classic result in algorithm analysis. ### Priority Queue A **priority queue** is an abstract data type where each element has a priority, and the element with the highest priority (lowest value in a min-priority queue) is served first. A heap is the standard implementation: ```typescript class PriorityQueue { private heap: MinHeap<{ value: T; priority: number }>; constructor() { this.heap = new MinHeap((a, b) => a.priority - b.priority); } enqueue(value: T, priority: number): void { this.heap.insert({ value, priority }); } dequeue(): T | undefined { return this.heap.extractMin()?.value; } peek(): T | undefined { return this.heap.peek()?.value; } get size(): number { return this.heap.size; } isEmpty(): boolean { return this.size === 0; } } // Usage const pq = new PriorityQueue(); pq.enqueue('low priority task', 10); pq.enqueue('URGENT task', 1); pq.enqueue('medium task', 5); console.log(pq.dequeue()); // 'URGENT task' console.log(pq.dequeue()); // 'medium task' console.log(pq.dequeue()); // 'low priority task' ``` ### Heap Complexity | Operation | Time Complexity | |-----------|----------------| | Insert (push) | O(log n) | | Extract min/max | O(log n) | | Peek (get min/max) | O(1) | | Build heap (heapify) | O(n) | | Search | O(n) — heaps are not optimized for search | ### Classic Heap Problems #### Kth Largest Element in an Array **LeetCode 215**: Find the kth largest element in an unsorted array. **Strategy**: Use a min-heap of size k. The top of the heap is the kth largest. ```typescript function findKthLargest(nums: number[], k: number): number { const heap = new MinHeap(); for (const num of nums) { heap.insert(num); if (heap.size > k) { heap.extractMin(); } } return heap.peek()!; } console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5 console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4 ``` **Why this works**: After processing all elements, the heap contains the k largest elements. The smallest of those (at the top of the min-heap) is the kth largest overall. Time: O(n log k). Space: O(k). #### Top K Frequent Elements **LeetCode 347**: Given an integer array, return the k most frequent elements. ```typescript function topKFrequent(nums: number[], k: number): number[] { const freqMap = new Map(); for (const num of nums) { freqMap.set(num, (freqMap.get(num) ?? 0) + 1); } const heap = new MinHeap<[number, number]>((a, b) => a[1] - b[1]); for (const [num, freq] of freqMap) { heap.insert([num, freq]); if (heap.size > k) { heap.extractMin(); } } const result: number[] = []; while (heap.size > 0) { result.push(heap.extractMin()![0]); } return result; } console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [1, 2] console.log(topKFrequent([1], 1)); // [1] ``` **How it works**: Build a frequency map, then maintain a min-heap of size k. Elements with the lowest frequency get evicted first, leaving the top k most frequent. Time: O(n log k). Space: O(n). --- ## Introduction to Graphs ### What Is a Graph? A **graph** is a collection of **vertices** (also called nodes) connected by **edges**. That's it. No rules about parents, no root, no hierarchy — just vertices and the connections between them. If a tree is a family hierarchy, a **graph is a social network**. People (vertices) connected by friendships (edges). Some friendships are mutual (undirected), some are one-way like following someone on Twitter (directed). Some connections are stronger than others (weighted). And unlike a family tree, you can have cycles — A is friends with B, B with C, and C with A. ``` Tree (strict rules): Graph (no rules): A A --- B / \ | / | B C | / | / \ | / | D E C --- D \ / \ / E ``` > **Every tree is a graph, but not every graph is a tree.** A tree is a connected, acyclic graph with exactly n-1 edges for n nodes. Graphs are the generalization. ### Types of Graphs #### Directed vs Undirected **Undirected graph**: Edges have no direction. If A connects to B, then B connects to A. Think: Facebook friendships, roads between cities. ``` Undirected: A --- B A ↔ B (bidirectional) | | C --- D ``` **Directed graph** (digraph): Edges have direction. A → B doesn't mean B → A. Think: Twitter follows, web page links, prerequisites. ``` Directed: A → B A can reach B, but B cannot reach A (unless B → A exists) ↑ ↓ C ← D ``` #### Weighted vs Unweighted **Unweighted**: All edges are equal. The "cost" of traversing any edge is the same. **Weighted**: Each edge has a numeric weight (cost, distance, time, capacity). GPS navigation uses a weighted graph where weights are distances or drive times. ``` Weighted: A --5-- B | | 2 8 | | C --3-- D ``` #### Connected, Disconnected, and Strongly Connected **Connected** (undirected): There's a path between every pair of vertices. **Disconnected**: Some vertices can't reach others. ``` Connected: Disconnected: A --- B A --- B D --- E | | | C --- D C ``` **Strongly connected** (directed): Every vertex can reach every other vertex following edge directions. **Weakly connected** (directed): Connected if you ignore edge directions. #### Cyclic vs Acyclic **Cyclic**: Contains at least one cycle (a path that starts and ends at the same vertex). **Acyclic**: No cycles exist. **DAG** (Directed Acyclic Graph): A directed graph with no cycles. Incredibly important in computer science — build systems, task scheduling, version control, and neural network architectures are all DAGs. ``` Cyclic: DAG (Directed Acyclic Graph): A → B A → B ↑ ↓ ↓ ↓ D ← C C → D → E (A→B→C→D→A is a cycle) (no way to return to a visited node) ``` ### Graph Terminology Reference | Term | Definition | |------|-----------| | **Vertex (Node)** | A point in the graph | | **Edge** | A connection between two vertices | | **Degree** | Number of edges connected to a vertex. In directed graphs: in-degree (incoming) and out-degree (outgoing) | | **Path** | A sequence of vertices connected by edges | | **Cycle** | A path that starts and ends at the same vertex | | **Connected component** | A maximal set of vertices where every pair is connected | | **Adjacent** | Two vertices connected by an edge | | **Neighbor** | A vertex adjacent to a given vertex | | **Sparse graph** | Few edges relative to vertices (E ≪ V²) | | **Dense graph** | Many edges relative to vertices (E ≈ V²) | --- ## Graph Representations There are three main ways to represent a graph in code. Each has trade-offs, and choosing the right one matters. ### Adjacency Matrix A 2D array where `matrix[i][j]` indicates whether there's an edge from vertex i to vertex j. For weighted graphs, the value is the edge weight. ``` Graph: Adjacency Matrix: 0 --- 1 0 1 2 3 | / | 0 [ 0, 1, 1, 0 ] | / | 1 [ 1, 0, 1, 1 ] 2 --- 3 2 [ 1, 1, 0, 1 ] 3 [ 0, 1, 1, 0 ] ``` ```typescript class AdjacencyMatrix { private matrix: number[][]; private numVertices: number; constructor(numVertices: number) { this.numVertices = numVertices; this.matrix = Array.from({ length: numVertices }, () => new Array(numVertices).fill(0) ); } addEdge(from: number, to: number, weight: number = 1): void { this.matrix[from][to] = weight; this.matrix[to][from] = weight; // remove for directed graph } removeEdge(from: number, to: number): void { this.matrix[from][to] = 0; this.matrix[to][from] = 0; } hasEdge(from: number, to: number): boolean { return this.matrix[from][to] !== 0; } getNeighbors(vertex: number): number[] { const neighbors: number[] = []; for (let i = 0; i < this.numVertices; i++) { if (this.matrix[vertex][i] !== 0) { neighbors.push(i); } } return neighbors; } getWeight(from: number, to: number): number { return this.matrix[from][to]; } } ``` **Pros**: O(1) edge lookup, simple to implement, great for dense graphs. **Cons**: O(V²) space always (even for sparse graphs), O(V) to find all neighbors. ### Adjacency List Each vertex stores a list of its neighbors. This is the **most common representation** for general-purpose graph algorithms. ``` Graph: Adjacency List: 0 --- 1 0 → [1, 2] | / | 1 → [0, 2, 3] | / | 2 → [0, 1, 3] 2 --- 3 3 → [1, 2] ``` ```typescript class Graph { private adjacencyList: Map> = new Map(); addVertex(vertex: T): void { if (!this.adjacencyList.has(vertex)) { this.adjacencyList.set(vertex, new Map()); } } addEdge(from: T, to: T, weight: number = 1): void { this.addVertex(from); this.addVertex(to); this.adjacencyList.get(from)!.set(to, weight); this.adjacencyList.get(to)!.set(from, weight); // remove for directed } addDirectedEdge(from: T, to: T, weight: number = 1): void { this.addVertex(from); this.addVertex(to); this.adjacencyList.get(from)!.set(to, weight); } removeEdge(from: T, to: T): void { this.adjacencyList.get(from)?.delete(to); this.adjacencyList.get(to)?.delete(from); } hasEdge(from: T, to: T): boolean { return this.adjacencyList.get(from)?.has(to) ?? false; } getNeighbors(vertex: T): Map { return this.adjacencyList.get(vertex) ?? new Map(); } getVertices(): T[] { return [...this.adjacencyList.keys()]; } getEdgeWeight(from: T, to: T): number | undefined { return this.adjacencyList.get(from)?.get(to); } } ``` **Pros**: O(V + E) space, O(degree) to find neighbors, efficient for sparse graphs. **Cons**: O(degree) edge lookup (vs O(1) for matrix). ### Edge List Simply a list of all edges. Minimal, but not great for neighbor lookups. Useful for algorithms like Kruskal's that iterate over all edges. ```typescript type Edge = { from: T; to: T; weight: number }; const edges: Edge[] = [ { from: 'A', to: 'B', weight: 5 }, { from: 'A', to: 'C', weight: 2 }, { from: 'B', to: 'D', weight: 8 }, { from: 'C', to: 'D', weight: 3 }, ]; ``` ### Comparison Table | Feature | Adjacency Matrix | Adjacency List | Edge List | |---------|-----------------|----------------|-----------| | Space | O(V²) | O(V + E) | O(E) | | Check edge exists | O(1) | O(degree) | O(E) | | Find all neighbors | O(V) | O(degree) | O(E) | | Add edge | O(1) | O(1) | O(1) | | Remove edge | O(1) | O(degree) | O(E) | | Best for | Dense graphs, frequent edge lookups | Sparse graphs, most algorithms | Edge-centric algorithms (Kruskal's) | > **Rule of thumb**: Use an adjacency list for almost everything. Use a matrix only when the graph is dense (E ≈ V²) and you need constant-time edge lookups. Use an edge list when the algorithm primarily iterates over edges. --- ## Graph Traversals Graph traversals are the foundation of almost every graph algorithm. If you've done DFS and BFS on trees, graph traversals are the same idea with one addition: a **visited set** to prevent infinite loops caused by cycles. ### Depth-First Search (DFS) Explore as deep as possible before backtracking. Use a **stack** (or recursion's call stack) and a **visited set**. ```typescript function dfsRecursive(graph: Graph, start: T): T[] { const visited = new Set(); const result: T[] = []; function dfs(vertex: T): void { visited.add(vertex); result.push(vertex); for (const [neighbor] of graph.getNeighbors(vertex)) { if (!visited.has(neighbor)) { dfs(neighbor); } } } dfs(start); return result; } function dfsIterative(graph: Graph, start: T): T[] { const visited = new Set(); const stack: T[] = [start]; const result: T[] = []; while (stack.length > 0) { const vertex = stack.pop()!; if (visited.has(vertex)) continue; visited.add(vertex); result.push(vertex); for (const [neighbor] of graph.getNeighbors(vertex)) { if (!visited.has(neighbor)) { stack.push(neighbor); } } } return result; } ``` ### Breadth-First Search (BFS) Explore all neighbors at the current depth before moving deeper. Use a **queue** and a **visited set**. ```typescript function bfs(graph: Graph, start: T): T[] { const visited = new Set(); const queue: T[] = [start]; visited.add(start); const result: T[] = []; while (queue.length > 0) { const vertex = queue.shift()!; result.push(vertex); for (const [neighbor] of graph.getNeighbors(vertex)) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); } } } return result; } ``` **Key difference from tree traversals**: In trees, we never revisit nodes because trees have no cycles. In graphs, the **visited set** is essential. Without it, a cycle would cause an infinite loop. **Time complexity**: Both DFS and BFS are **O(V + E)** — we visit every vertex once and examine every edge once. > For a deeper dive into DFS and BFS applications and patterns, check out the **DFS/BFS Made Simple** article in the problem-solving patterns series. --- ## Shortest Path Algorithms Finding the shortest path between two points is one of the most practical problems in computer science. Your GPS uses it. Your network router uses it. Game pathfinding uses it. Here are the algorithms that make it work. ### Dijkstra's Algorithm **Edsger Dijkstra** published this algorithm in 1959, and it remains one of the most important algorithms ever written. It finds the **shortest path from a source vertex to all other vertices** in a weighted graph with **non-negative edge weights**. #### How It Works Dijkstra's is a **greedy algorithm** that uses a **priority queue**: 1. Set the distance to the source as 0, all others as ∞ 2. Add the source to a priority queue 3. While the queue is not empty: a. Extract the vertex with the smallest distance b. For each neighbor: if the path through the current vertex is shorter than the known distance, update it c. Add updated neighbors to the queue The key insight: once a vertex is extracted from the priority queue, its shortest distance is **finalized**. The greedy choice is always correct because all edge weights are non-negative. #### Visual Walkthrough Find shortest paths from **A** to all other vertices: ``` Graph: A / \ 4 1 / \ B --2-- C | | 5 8 | | D --3-- E Step 1: Start at A Distances: A=0, B=∞, C=∞, D=∞, E=∞ PQ: [(A, 0)] Step 2: Process A (dist=0) - A→B: 0+4 = 4 < ∞ → update B=4 - A→C: 0+1 = 1 < ∞ → update C=1 Distances: A=0, B=4, C=1, D=∞, E=∞ PQ: [(C, 1), (B, 4)] Step 3: Process C (dist=1) ← smallest in PQ - C→B: 1+2 = 3 < 4 → update B=3 - C→E: 1+8 = 9 < ∞ → update E=9 Distances: A=0, B=3, C=1, D=∞, E=9 PQ: [(B, 3), (B, 4), (E, 9)] Step 4: Process B (dist=3) - B→D: 3+5 = 8 < ∞ → update D=8 Distances: A=0, B=3, C=1, D=8, E=9 PQ: [(B, 4), (D, 8), (E, 9)] Step 5: Process B (dist=4) — already finalized, skip Step 6: Process D (dist=8) - D→E: 8+3 = 11 > 9 → no update Distances: A=0, B=3, C=1, D=8, E=9 Step 7: Process E (dist=9) — no updates needed Final shortest distances from A: A→A: 0 A→B: 3 (via A→C→B) A→C: 1 (via A→C) A→D: 8 (via A→C→B→D) A→E: 9 (via A→C→E) ``` #### TypeScript Implementation ```typescript function dijkstra( graph: Graph, source: T ): { distances: Map; previous: Map } { const distances = new Map(); const previous = new Map(); const visited = new Set(); const pq = new MinHeap<{ vertex: T; dist: number }>( (a, b) => a.dist - b.dist ); for (const vertex of graph.getVertices()) { distances.set(vertex, Infinity); previous.set(vertex, null); } distances.set(source, 0); pq.insert({ vertex: source, dist: 0 }); while (pq.size > 0) { const { vertex: current, dist: currentDist } = pq.extractMin()!; if (visited.has(current)) continue; visited.add(current); for (const [neighbor, weight] of graph.getNeighbors(current)) { if (visited.has(neighbor)) continue; const newDist = currentDist + weight; if (newDist < distances.get(neighbor)!) { distances.set(neighbor, newDist); previous.set(neighbor, current); pq.insert({ vertex: neighbor, dist: newDist }); } } } return { distances, previous }; } function getShortestPath( previous: Map, target: T ): T[] { const path: T[] = []; let current: T | null = target; while (current !== null) { path.unshift(current); current = previous.get(current) ?? null; } return path; } // Usage const graph = new Graph(); graph.addEdge('A', 'B', 4); graph.addEdge('A', 'C', 1); graph.addEdge('B', 'C', 2); graph.addEdge('B', 'D', 5); graph.addEdge('C', 'E', 8); graph.addEdge('D', 'E', 3); const { distances, previous } = dijkstra(graph, 'A'); console.log(distances); // Map { 'A' => 0, 'B' => 3, 'C' => 1, 'D' => 8, 'E' => 9 } console.log(getShortestPath(previous, 'E')); // ['A', 'C', 'E'] console.log(getShortestPath(previous, 'D')); // ['A', 'C', 'B', 'D'] ``` #### Dijkstra's Complexity | Metric | With Binary Heap | With Fibonacci Heap | |--------|-----------------|-------------------| | Time | O((V + E) log V) | O(V log V + E) | | Space | O(V) | O(V) | #### Limitation: No Negative Weights Dijkstra's assumes that once a vertex is finalized, no shorter path can be found. **Negative edge weights break this assumption**: ``` A --1-→ B | | 4 -5 | | ↓ ↓ C --2-→ D Dijkstra processes B (dist=1), then C (dist=4). But the path A→B→D costs 1+(-5) = -4, then D→... could lead back and improve C. Dijkstra would miss this because it already finalized B. ``` For graphs with negative weights, we need Bellman-Ford. --- ### Bellman-Ford Algorithm **Bellman-Ford** handles **negative edge weights** and can even **detect negative weight cycles** (a cycle whose total weight is negative, meaning you could loop forever reducing the cost). #### How It Works The idea is simpler than Dijkstra's (but slower): 1. Set distance to source as 0, all others as ∞ 2. **Repeat V-1 times**: For every edge (u, v, w), if `dist[u] + w < dist[v]`, update `dist[v]` 3. Do one more pass. If any distance decreases, there's a **negative cycle** **Why V-1 iterations?** The shortest path between any two vertices can have at most V-1 edges. Each iteration guarantees at least one more edge of each shortest path is correctly computed. #### TypeScript Implementation ```typescript type BFEdge = { from: string; to: string; weight: number }; function bellmanFord( vertices: string[], edges: BFEdge[], source: string ): { distances: Map; hasNegativeCycle: boolean } { const distances = new Map(); for (const v of vertices) { distances.set(v, Infinity); } distances.set(source, 0); // Relax all edges V-1 times for (let i = 0; i < vertices.length - 1; i++) { let updated = false; for (const { from, to, weight } of edges) { const distFrom = distances.get(from)!; if (distFrom === Infinity) continue; if (distFrom + weight < distances.get(to)!) { distances.set(to, distFrom + weight); updated = true; } } if (!updated) break; // early termination optimization } // Check for negative cycles let hasNegativeCycle = false; for (const { from, to, weight } of edges) { const distFrom = distances.get(from)!; if (distFrom !== Infinity && distFrom + weight < distances.get(to)!) { hasNegativeCycle = true; break; } } return { distances, hasNegativeCycle }; } // Usage const vertices = ['A', 'B', 'C', 'D', 'E']; const edges: BFEdge[] = [ { from: 'A', to: 'B', weight: 4 }, { from: 'A', to: 'C', weight: 1 }, { from: 'C', to: 'B', weight: -2 }, { from: 'B', to: 'D', weight: 3 }, { from: 'C', to: 'D', weight: 6 }, { from: 'D', to: 'E', weight: 1 }, ]; const result = bellmanFord(vertices, edges, 'A'); console.log(result.distances); // Map { 'A' => 0, 'B' => -1, 'C' => 1, 'D' => 2, 'E' => 3 } console.log(result.hasNegativeCycle); // false ``` #### Bellman-Ford Complexity | Metric | Complexity | |--------|-----------| | Time | O(V × E) | | Space | O(V) | Bellman-Ford is slower than Dijkstra's — O(VE) vs O((V+E) log V) — but it's more general. Use Dijkstra's when you can, Bellman-Ford when you must. --- ### Floyd-Warshall (All-Pairs Shortest Path) If you need the shortest path between **every pair** of vertices, **Floyd-Warshall** computes all of them in O(V³) using dynamic programming. It's elegant but only practical for small graphs (a few hundred vertices). ```typescript function floydWarshall(matrix: number[][]): number[][] { const n = matrix.length; const dist = matrix.map((row) => [...row]); for (let k = 0; k < n; k++) { for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } return dist; } ``` The key idea: for each intermediate vertex k, check if going through k improves any shortest path. Three nested loops, each iterating over all vertices. Simple, correct, and O(V³). ### Shortest Path Algorithm Comparison | Algorithm | Weights | Negative Weights | Negative Cycles | Time | Use Case | |-----------|---------|-----------------|-----------------|------|----------| | Dijkstra's | Weighted | No | No | O((V+E) log V) | Single-source, non-negative weights | | Bellman-Ford | Weighted | Yes | Detects | O(VE) | Single-source, negative weights possible | | Floyd-Warshall | Weighted | Yes | Detects | O(V³) | All-pairs shortest path | | BFS | Unweighted | N/A | N/A | O(V+E) | Single-source, unweighted | --- ## Topological Sort ### What Is It? A **topological sort** is a linear ordering of vertices in a **Directed Acyclic Graph (DAG)** such that for every directed edge u → v, vertex u comes before vertex v in the ordering. Think of it as a valid order to do things when some things depend on others: ``` Course prerequisites: Calculus I → Calculus II → Differential Equations Linear Algebra → Differential Equations Calculus I → Linear Algebra Topological order: Calculus I → Calculus II → Linear Algebra → Diff Eq (or) Calculus I → Linear Algebra → Calculus II → Diff Eq Both are valid! Topological sort is not unique. ``` ``` DAG: A → B → D A → C → D C → E Topological orders: A, B, C, D, E ✓ A, C, B, E, D ✓ A, C, E, B, D ✓ B, A, C, D, E ✗ (B before A, but A → B) ``` **Where topological sort is used**: - **Build systems** — compile dependencies in the right order (Make, webpack) - **Task scheduling** — which tasks must finish before others can start - **Course planning** — determine a valid order to take classes - **Package managers** — install dependencies before the packages that need them - **Spreadsheets** — evaluate cells in dependency order > **Important**: Topological sort is only possible on a DAG. If the graph has a cycle, no valid ordering exists (you'd have a chicken-and-egg problem). ### Kahn's Algorithm (BFS-Based) Kahn's algorithm uses the concept of **in-degree** (number of incoming edges): 1. Compute in-degree for every vertex 2. Add all vertices with in-degree 0 to a queue (they have no dependencies) 3. While the queue is not empty: a. Remove a vertex, add it to the result b. For each neighbor, decrement its in-degree c. If a neighbor's in-degree becomes 0, add it to the queue 4. If the result contains all vertices, we have a valid ordering. If not, there's a cycle. ```typescript function topologicalSortKahn(graph: Graph): T[] | null { const inDegree = new Map(); const vertices = graph.getVertices(); for (const v of vertices) { inDegree.set(v, 0); } for (const v of vertices) { for (const [neighbor] of graph.getNeighbors(v)) { inDegree.set(neighbor, (inDegree.get(neighbor) ?? 0) + 1); } } const queue: T[] = []; for (const [v, degree] of inDegree) { if (degree === 0) queue.push(v); } const result: T[] = []; while (queue.length > 0) { const vertex = queue.shift()!; result.push(vertex); for (const [neighbor] of graph.getNeighbors(vertex)) { const newDegree = inDegree.get(neighbor)! - 1; inDegree.set(neighbor, newDegree); if (newDegree === 0) { queue.push(neighbor); } } } return result.length === vertices.length ? result : null; // null = cycle detected } ``` ### DFS-Based Topological Sort The DFS approach works backwards: vertices that finish their DFS exploration last should come first in the ordering. We use a post-order approach and reverse the result. ```typescript function topologicalSortDFS(graph: Graph): T[] | null { const visited = new Set(); const inStack = new Set(); const result: T[] = []; let hasCycle = false; function dfs(vertex: T): void { if (hasCycle) return; visited.add(vertex); inStack.add(vertex); for (const [neighbor] of graph.getNeighbors(vertex)) { if (inStack.has(neighbor)) { hasCycle = true; return; } if (!visited.has(neighbor)) { dfs(neighbor); } } inStack.delete(vertex); result.push(vertex); } for (const vertex of graph.getVertices()) { if (!visited.has(vertex)) { dfs(vertex); } } if (hasCycle) return null; return result.reverse(); } ``` ### Walkthrough: LeetCode 207 — Course Schedule **Problem**: There are `numCourses` courses labeled `0` to `numCourses - 1`. You're given an array `prerequisites` where `prerequisites[i] = [a, b]` means you must take course `b` before course `a`. Return `true` if you can finish all courses. **Translation**: Build a directed graph from prerequisites. If a valid topological sort exists (no cycle), return true. ```typescript function canFinish( numCourses: number, prerequisites: number[][] ): boolean { const graph = new Map(); const inDegree = new Array(numCourses).fill(0); for (let i = 0; i < numCourses; i++) { graph.set(i, []); } for (const [course, prereq] of prerequisites) { graph.get(prereq)!.push(course); inDegree[course]++; } const queue: number[] = []; for (let i = 0; i < numCourses; i++) { if (inDegree[i] === 0) queue.push(i); } let completed = 0; while (queue.length > 0) { const course = queue.shift()!; completed++; for (const next of graph.get(course)!) { inDegree[next]--; if (inDegree[next] === 0) { queue.push(next); } } } return completed === numCourses; } // Example console.log(canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]])); // true // Valid order: 0, 1, 2, 3 or 0, 2, 1, 3 console.log(canFinish(2, [[1, 0], [0, 1]])); // false // Cycle: 0 → 1 → 0 ``` ### Topological Sort Complexity | Algorithm | Time | Space | |-----------|------|-------| | Kahn's (BFS) | O(V + E) | O(V) | | DFS-based | O(V + E) | O(V) | Both are equivalent in performance. Kahn's naturally detects cycles (if the result is shorter than V, there's a cycle). The DFS approach detects cycles using the "in-stack" set. --- ## Union-Find (Disjoint Set Union) ### What Problem Does It Solve? Imagine you have n elements in separate groups. You need to: 1. **Union**: Merge two groups into one 2. **Find**: Determine which group an element belongs to 3. **Connected**: Check if two elements are in the same group This comes up in: - **Connected components** — are two nodes in the same component? - **Kruskal's MST algorithm** — does adding this edge create a cycle? - **Network connectivity** — are two computers on the same network? - **Social networks** — are two people in the same friend group? - **Image processing** — labeling connected regions ### The Naive Approach You could use DFS/BFS to check connectivity each time, but that's O(V + E) per query. Union-Find achieves **nearly O(1)** per operation with two optimizations. ### How It Works Each element points to a **parent**. The root of each tree is the **representative** of that group. Initially, every element is its own parent (its own group). ``` Initial state (5 elements, each is its own group): 0 1 2 3 4 ↑ ↑ ↑ ↑ ↑ (self-loops: each is its own root) After Union(0, 1) and Union(2, 3): 0 ← 1 2 ← 3 4 After Union(0, 2): 0 / \ 1 2 | 3 Element 4 is still separate. Find(3) = 0 (follow parent pointers: 3 → 2 → 0) Find(4) = 4 Connected(1, 3) = true (same root: 0) Connected(1, 4) = false (different roots: 0 vs 4) ``` ### Optimizations Without optimizations, Union-Find can degrade to O(n) per operation (just like a degenerate BST). Two optimizations bring it down to nearly O(1): **1. Path Compression (on Find)**: When finding the root, make every node along the path point directly to the root. This flattens the tree. ``` Before Find(3): After Find(3) with path compression: 0 0 / / | \ 2 1 2 3 / 3 ``` **2. Union by Rank**: When merging two trees, attach the shorter tree under the root of the taller tree. This keeps the tree shallow. ### TypeScript Implementation ```typescript class UnionFind { private parent: number[]; private rank: number[]; private count: number; // number of distinct components constructor(size: number) { this.parent = Array.from({ length: size }, (_, i) => i); this.rank = new Array(size).fill(0); this.count = size; } find(x: number): number { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // path compression } return this.parent[x]; } union(x: number, y: number): boolean { const rootX = this.find(x); const rootY = this.find(y); if (rootX === rootY) return false; // already connected // union by rank if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else if (this.rank[rootX] > this.rank[rootY]) { this.parent[rootY] = rootX; } else { this.parent[rootY] = rootX; this.rank[rootX]++; } this.count--; return true; } connected(x: number, y: number): boolean { return this.find(x) === this.find(y); } getCount(): number { return this.count; } } // Usage const uf = new UnionFind(5); uf.union(0, 1); uf.union(2, 3); console.log(uf.connected(0, 1)); // true console.log(uf.connected(0, 3)); // false console.log(uf.getCount()); // 3 components: {0,1}, {2,3}, {4} uf.union(1, 3); console.log(uf.connected(0, 3)); // true console.log(uf.getCount()); // 2 components: {0,1,2,3}, {4} ``` ### Union-Find Complexity | Operation | Without Optimization | With Path Compression + Union by Rank | |-----------|---------------------|--------------------------------------| | Find | O(n) worst case | O(α(n)) ≈ O(1) amortized | | Union | O(n) worst case | O(α(n)) ≈ O(1) amortized | **α(n)** is the **inverse Ackermann function**, which grows so slowly that for any practical input size (up to 2^65536), it never exceeds 4. For all intents and purposes, it's constant time. ### LeetCode 200 — Number of Islands (Union-Find Approach) The classic Number of Islands problem is usually solved with DFS/BFS, but Union-Find provides an elegant alternative: ```typescript function numIslands(grid: string[][]): number { if (grid.length === 0) return 0; const rows = grid.length; const cols = grid[0].length; const uf = new UnionFind(rows * cols); let waterCount = 0; const directions = [ [0, 1], [1, 0], [0, -1], [-1, 0], ]; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === '0') { waterCount++; continue; } for (const [dr, dc] of directions) { const nr = r + dr; const nc = c + dc; if ( nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1' ) { uf.union(r * cols + c, nr * cols + nc); } } } } return uf.getCount() - waterCount; } // Example const grid = [ ['1', '1', '0', '0', '0'], ['1', '1', '0', '0', '0'], ['0', '0', '1', '0', '0'], ['0', '0', '0', '1', '1'], ]; console.log(numIslands(grid)); // 3 ``` --- ## Cycle Detection Detecting cycles is a fundamental graph operation. It determines whether a topological sort is possible, whether adding an edge would create a loop, and whether a graph is a tree (trees are connected acyclic graphs). ### Cycle Detection in Directed Graphs For directed graphs, we use a **three-color DFS** (also called white-gray-black marking): - **White**: Not yet visited - **Gray**: Currently being explored (in the current DFS path) - **Black**: Fully explored (all descendants visited) If we encounter a **gray** node during DFS, we've found a **back edge** — a cycle. ``` Graph: A → B → C ↗ ↓ E ← D DFS from A: Visit A (gray) → Visit B (gray) → Visit C (gray) → Visit D (gray) → Visit E (gray) → E has edge to B, and B is GRAY → CYCLE DETECTED! The cycle is: B → C → D → E → B ``` ```typescript function hasCycleDirected(graph: Graph): boolean { const WHITE = 0; const GRAY = 1; const BLACK = 2; const color = new Map(); for (const v of graph.getVertices()) { color.set(v, WHITE); } function dfs(vertex: T): boolean { color.set(vertex, GRAY); for (const [neighbor] of graph.getNeighbors(vertex)) { if (color.get(neighbor) === GRAY) return true; // back edge = cycle if ( color.get(neighbor) === WHITE && dfs(neighbor) ) { return true; } } color.set(vertex, BLACK); return false; } for (const vertex of graph.getVertices()) { if (color.get(vertex) === WHITE) { if (dfs(vertex)) return true; } } return false; } ``` **Why three colors instead of two?** In a directed graph, encountering a visited node doesn't always mean there's a cycle. If the node is **black** (fully explored), it means we're looking at a **cross edge** or **forward edge**, not a back edge. Only gray nodes indicate a cycle. ### Cycle Detection in Undirected Graphs For undirected graphs, the approach is simpler. During DFS, if we encounter a visited node that **isn't our parent**, we've found a cycle. ``` Graph: A --- B | | C --- D DFS from A: Visit A → Visit B (parent=A) → Visit D (parent=B) → D has neighbor C (not visited) → Visit C (parent=D) → C has neighbor A (visited, and A ≠ parent D) → CYCLE! ``` ```typescript function hasCycleUndirected(graph: Graph): boolean { const visited = new Set(); function dfs(vertex: T, parent: T | null): boolean { visited.add(vertex); for (const [neighbor] of graph.getNeighbors(vertex)) { if (!visited.has(neighbor)) { if (dfs(neighbor, vertex)) return true; } else if (neighbor !== parent) { return true; // visited neighbor that isn't our parent = cycle } } return false; } for (const vertex of graph.getVertices()) { if (!visited.has(vertex)) { if (dfs(vertex, null)) return true; } } return false; } ``` #### Union-Find Approach for Undirected Graphs Union-Find provides an alternative for undirected cycle detection. For each edge, if both endpoints are already in the same component, adding the edge creates a cycle: ```typescript function hasCycleUnionFind( numVertices: number, edges: [number, number][] ): boolean { const uf = new UnionFind(numVertices); for (const [u, v] of edges) { if (uf.connected(u, v)) return true; // already connected = cycle uf.union(u, v); } return false; } ``` ### Cycle Detection Complexity | Method | Graph Type | Time | Space | |--------|-----------|------|-------| | Three-color DFS | Directed | O(V + E) | O(V) | | DFS with parent | Undirected | O(V + E) | O(V) | | Union-Find | Undirected | O(E × α(V)) ≈ O(E) | O(V) | --- ## Minimum Spanning Tree A **Minimum Spanning Tree (MST)** of a weighted, connected, undirected graph is a subset of edges that connects all vertices with the **minimum total edge weight** and **no cycles**. It's a tree (V-1 edges, connected, acyclic) that "spans" all vertices at minimum cost. **Real-world applications**: Designing road networks, laying cable, network design, approximating NP-hard problems like the Traveling Salesman. ### Kruskal's Algorithm **Strategy**: Sort all edges by weight. Add edges from lightest to heaviest, skipping any edge that would create a cycle. Use **Union-Find** for cycle detection. ```typescript interface MSTEdge { from: number; to: number; weight: number; } function kruskal(numVertices: number, edges: MSTEdge[]): MSTEdge[] { edges.sort((a, b) => a.weight - b.weight); const uf = new UnionFind(numVertices); const mst: MSTEdge[] = []; for (const edge of edges) { if (!uf.connected(edge.from, edge.to)) { uf.union(edge.from, edge.to); mst.push(edge); if (mst.length === numVertices - 1) break; } } return mst; } // Example const mstEdges: MSTEdge[] = [ { from: 0, to: 1, weight: 4 }, { from: 0, to: 2, weight: 1 }, { from: 1, to: 2, weight: 2 }, { from: 1, to: 3, weight: 5 }, { from: 2, to: 3, weight: 8 }, { from: 3, to: 4, weight: 3 }, ]; const mst = kruskal(5, mstEdges); console.log(mst); // Edges: 0-2 (1), 1-2 (2), 3-4 (3), 0-1 (4) // Total weight: 10 ``` #### Visual Walkthrough ``` Graph: MST (total weight = 10): 0 --4-- 1 0 ------ 1 | \ | | | 1 2 5 1 2 | | \ | | | 2 --8-- 3 --3-- 4 2 3 --3-- 4 Edges sorted: (0,2,1) (1,2,2) (3,4,3) (0,1,4) (1,3,5) (2,3,8) 1. Add (0,2,1): {0,2} connected ✓ 2. Add (1,2,2): {0,1,2} connected ✓ 3. Add (3,4,3): {3,4} connected ✓ 4. Add (0,1,4): 0 and 1 already connected → SKIP 5. Add (1,3,5): {0,1,2,3,4} all connected ✓ → Done! Total weight: 1 + 2 + 3 + 5 = 11 ``` **Time complexity**: O(E log E) for sorting + O(E × α(V)) for Union-Find = **O(E log E)** ### Prim's Algorithm **Strategy**: Start from any vertex. Repeatedly add the cheapest edge that connects a vertex in the MST to a vertex outside it. Use a **priority queue**. ```typescript function prim(graph: Graph, startVertex: number): MSTEdge[] { const mst: MSTEdge[] = []; const visited = new Set(); const pq = new MinHeap((a, b) => a.weight - b.weight); visited.add(startVertex); for (const [neighbor, weight] of graph.getNeighbors(startVertex)) { pq.insert({ from: startVertex, to: neighbor, weight }); } while (pq.size > 0 && mst.length < graph.getVertices().length - 1) { const edge = pq.extractMin()!; if (visited.has(edge.to)) continue; visited.add(edge.to); mst.push(edge); for (const [neighbor, weight] of graph.getNeighbors(edge.to)) { if (!visited.has(neighbor)) { pq.insert({ from: edge.to, to: neighbor, weight }); } } } return mst; } ``` **Time complexity**: O(E log V) with a binary heap. ### Kruskal's vs Prim's | Property | Kruskal's | Prim's | |----------|-----------|--------| | Approach | Edge-centric (sort edges) | Vertex-centric (grow from a vertex) | | Data structure | Union-Find | Priority Queue | | Time | O(E log E) | O(E log V) | | Best for | Sparse graphs | Dense graphs | | Implementation | Simpler | Slightly more complex | --- ## When to Use What Choosing the right data structure or algorithm is half the battle. Here's a decision guide. ### Tree vs Graph | Question | If Yes → | |----------|---------| | Is the data hierarchical with a single root? | Tree | | Can a node have multiple parents? | Graph | | Are there cycles? | Graph | | Is it a dependency/prerequisite structure? | DAG (directed graph) | ### Which Tree Structure? | Need | Use | |------|-----| | Sorted data with fast lookup | BST (basic) or AVL/Red-Black (self-balancing) | | Prefix search, autocomplete | Trie | | Priority-based access (min/max) | Heap | | Read-heavy with guaranteed performance | AVL Tree | | Mixed read/write workload | Red-Black Tree | | Database indexes | B-Tree / B+ Tree | ### Which Graph Algorithm? | Problem | Algorithm | Time | |---------|-----------|------| | Shortest path (unweighted) | BFS | O(V + E) | | Shortest path (non-negative weights) | Dijkstra's | O((V+E) log V) | | Shortest path (negative weights) | Bellman-Ford | O(VE) | | All-pairs shortest path | Floyd-Warshall | O(V³) | | Dependency ordering | Topological Sort | O(V + E) | | Connected components | Union-Find or DFS | O(V + E) | | Cycle detection (directed) | Three-color DFS | O(V + E) | | Cycle detection (undirected) | DFS with parent / Union-Find | O(V + E) | | Minimum spanning tree (sparse) | Kruskal's | O(E log E) | | Minimum spanning tree (dense) | Prim's | O(E log V) | ### Heap vs Sorted Array | Operation | Heap | Sorted Array | |-----------|------|-------------| | Insert | O(log n) | O(n) | | Get min/max | O(1) | O(1) | | Extract min/max | O(log n) | O(1) amortized (from end) | | Search | O(n) | O(log n) | | Best for | Dynamic data with frequent insert/extract | Static data with frequent search | > **Rule of thumb**: If you're constantly adding and removing the min/max element, use a heap. If you need to search by value, use a sorted array or BST. --- ## Cheat Sheet ### Data Structure Complexity | Structure | Access | Search | Insert | Delete | Space | |-----------|--------|--------|--------|--------|-------| | BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | Trie | — | O(m)* | O(m)* | O(m)* | O(n × m) | | Min/Max Heap | — | O(n) | O(log n) | O(log n) | O(n) | | Priority Queue | — | O(n) | O(log n) | O(log n) | O(n) | | Union-Find | — | — | — | — | O(n) | *m = length of the key (string)* ### Graph Algorithm Decision Table | I need to... | Algorithm | Works on | Time | |--------------|-----------|----------|------| | Find shortest path (no weights) | BFS | Unweighted | O(V+E) | | Find shortest path (positive weights) | Dijkstra's | Weighted (≥0) | O((V+E) log V) | | Find shortest path (negative weights) | Bellman-Ford | Weighted (any) | O(VE) | | Find all shortest paths | Floyd-Warshall | Weighted | O(V³) | | Order tasks by dependencies | Topological Sort | DAG | O(V+E) | | Check if two nodes are connected | Union-Find | Undirected | O(α(n)) | | Find connected components | DFS/BFS or Union-Find | Any | O(V+E) | | Detect cycles (directed) | Three-color DFS | Directed | O(V+E) | | Detect cycles (undirected) | DFS / Union-Find | Undirected | O(V+E) | | Find cheapest network | Kruskal's / Prim's | Weighted undirected | O(E log V) | | Traverse all nodes | DFS / BFS | Any | O(V+E) | ### Key Relationships ``` Graph / \ Directed Undirected / \ | DAG Cyclic Tree (connected, acyclic) | | Topological Sort Spanning Tree | MST ``` --- ## Wrapping Up You've just covered an enormous amount of ground. Let's recap what you've learned: - **AVL trees** maintain strict balance through rotations, guaranteeing O(log n) operations even in the worst case - **Red-Black trees** trade slightly looser balance for faster insertions and deletions, making them the go-to for standard library implementations - **Tries** enable lightning-fast prefix operations and power the autocomplete features you use every day - **Heaps** and **priority queues** give you constant-time access to the minimum or maximum element, with logarithmic insertion and extraction - **Graphs** generalize trees into a structure that can represent virtually any relationship — social connections, road networks, dependencies, and more - **Dijkstra's algorithm** finds shortest paths greedily using a priority queue, while **Bellman-Ford** handles the trickier case of negative weights - **Topological sort** linearizes dependencies, making it essential for build systems and scheduling - **Union-Find** tracks connected components in nearly constant time per operation — one of the most elegant data structures in computer science - **Cycle detection** uses coloring for directed graphs and parent tracking for undirected graphs - **Minimum spanning trees** connect all vertices at minimum cost using Kruskal's or Prim's algorithm These aren't just interview topics. They're the structures and algorithms that professional software engineers reach for when building real systems. Every time you use a GPS, run a build pipeline, search for a file, or get a friend suggestion on social media, some combination of these data structures is working behind the scenes. The best way to internalize all of this? **Build things**. Implement a shortest-path visualizer. Create an autocomplete system with a trie. Solve graph problems on LeetCode until the patterns become second nature. The code is all here — now make it yours. > **What's next?** Check out the problem-solving pattern articles for DFS/BFS, recursion, and other algorithmic techniques that build on everything covered here. The deep dive never ends — it just gets more interesting. Happy coding.

Trees and Graphs: The Complete Deep Dive