There are only two fundamental ways to explore a structure: **go deep** or **go wide**. That's it. Whether you're traversing a binary tree, navigating a maze, finding connected components in a social network, or solving a Rubik's cube — the strategy boils down to one of two choices. Do you dive as far as possible down one path before backtracking? Or do you fan out layer by layer, exploring everything at the current distance before moving further? The first approach is **Depth-First Search (DFS)**. The second is **Breadth-First Search (BFS)**. Together, they are the bread and butter of tree and graph problems. If you had to pick just two algorithmic patterns to master for coding interviews, these would be it. They show up *everywhere*. LeetCode has hundreds of problems that are essentially DFS or BFS wearing different costumes. The good news? Both are built on data structures you already know — stacks and queues. DFS uses a stack (or the call stack via recursion). BFS uses a queue. Once you internalize the templates and build the intuition for *when to use which*, you can solve an enormous range of problems. > **DFS and BFS are not just algorithms. They're thinking strategies.** Learning them is like learning to read — suddenly, an entire world of problems becomes accessible. This guide is going to take you through both patterns, side by side. We'll start with the big picture, then work through the classic tree problems, move to graphs, compare the two strategies head-to-head, and build a decision framework you can use in any interview. Every problem gets full TypeScript code, a walkthrough, and Big O analysis. Let's explore. --- ## The Big Picture: Stack vs Queue, Depth vs Breadth Before we touch any code, let's build the mental model. ### DFS: Go Deep, Then Backtrack **Depth-First Search** explores as far as possible along one branch before backtracking. It uses a **stack** — either explicitly or implicitly via recursion (the call stack). Think of exploring a cave system. You pick a tunnel and walk as far as it goes. Dead end? Turn around, go back to the last fork, try the next tunnel. Repeat until you've explored every passage. ``` DFS order on a tree: 1 / \ 2 5 / \ \ 3 4 6 Visit order: 1 → 2 → 3 → 4 → 5 → 6 (Goes deep down the left branch first, backtracks, then right) ``` ### BFS: Go Wide, Level by Level **Breadth-First Search** explores all neighbors at the current depth before moving to the next level. It uses a **queue** — first-in, first-out. Think of dropping a pebble into a pond. The ripples expand outward in concentric circles. BFS explores the same way — everything at distance 1, then distance 2, then distance 3. ``` BFS order on a tree: 1 / \ 2 5 / \ \ 3 4 6 Visit order: 1 → 2 → 5 → 3 → 4 → 6 (Processes all nodes at each level before going deeper) ``` ### The Core Difference | | DFS | BFS | |---|-----|-----| | **Data Structure** | Stack (or recursion) | Queue | | **Exploration** | Deep first, backtrack | Level by level | | **Memory** | O(h) where h = height | O(w) where w = max width | | **Finds shortest path?** | No (finds *a* path) | Yes (in unweighted graphs) | | **Best for** | Exploring all paths, existence checks, tree structure | Shortest path, level-order processing | > **Key insight**: DFS and BFS will both visit every reachable node. The difference is the *order* in which they visit them — and that order determines which problems each one solves efficiently. Hold onto this table. We'll come back to it after working through a pile of problems. --- ## DFS on Trees Trees are the friendliest setting for DFS. There are no cycles to worry about, no visited set needed. Just recurse on children and trust the process. Let's start here to build confidence. --- ### Max Depth of Binary Tree (LeetCode 104) This is *the* gateway DFS problem. If DFS on trees were a tutorial level, this is it. #### Problem > Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. #### Examples ``` Input: 3 / \ 9 20 / \ 15 7 Output: 3 ``` #### The Key Insight The max depth of a tree is 1 (for the current node) plus the maximum of the left and right subtrees' depths. That's a recursive definition — and recursive definitions are DFS gold. **Base case**: If the node is `null`, depth is 0. **Recursive case**: `1 + max(depth(left), depth(right))`. #### TypeScript Solution ```typescript class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; } } function maxDepth(root: TreeNode | null): number { if (!root) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } ``` Three lines of actual logic. That's the beauty of recursive DFS on trees. #### Walkthrough ``` maxDepth(3) → 1 + max(maxDepth(9), maxDepth(20)) → maxDepth(9) = 1 + max(0, 0) = 1 → maxDepth(20) = 1 + max(maxDepth(15), maxDepth(7)) → maxDepth(15) = 1 → maxDepth(7) = 1 → maxDepth(20) = 1 + max(1, 1) = 2 → maxDepth(3) = 1 + max(1, 2) = 3 ``` #### Complexity - **Time**: O(n) — visit every node once - **Space**: O(h) — recursion stack depth, where h is the tree height. O(log n) for balanced, O(n) for skewed. --- ### Same Tree (LeetCode 100) #### Problem > Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same values. #### The Key Insight DFS both trees simultaneously. At each step, both nodes must either both be null, or both exist with the same value and identical subtrees. #### TypeScript Solution ```typescript function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean { if (!p && !q) return true; if (!p || !q) return false; return ( p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right) ); } ``` #### Walkthrough Think of it as walking two trees in lockstep. At every node, three things must be true: the values match, the left subtrees are the same, and the right subtrees are the same. If any check fails, short-circuit and return `false`. #### Complexity - **Time**: O(n) — worst case visit all nodes - **Space**: O(h) — recursion depth --- ### Invert Binary Tree (LeetCode 226) The problem that famously stumped the creator of Homebrew in a Google interview. Let's make sure it doesn't stump you. #### Problem > Given the root of a binary tree, invert the tree, and return its root. ``` Input: 4 Output: 4 / \ / \ 2 7 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1 ``` #### The Key Insight At every node, swap the left and right children, then recursively invert each subtree. The order doesn't matter — swap first then recurse, or recurse then swap. Both work because you're covering the entire tree. #### TypeScript Solution ```typescript function invertTree(root: TreeNode | null): TreeNode | null { if (!root) return null; const temp = root.left; root.left = root.right; root.right = temp; invertTree(root.left); invertTree(root.right); return root; } ``` Or the elegant one-liner approach: ```typescript function invertTree(root: TreeNode | null): TreeNode | null { if (!root) return null; [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]; return root; } ``` #### Complexity - **Time**: O(n) — visit every node - **Space**: O(h) — recursion stack --- ### Path Sum (LeetCode 112) and Path Sum II (LeetCode 113) These two problems show how DFS naturally accumulates information as it descends. #### Problem (112) > Given the root of a binary tree and an integer `targetSum`, return `true` if the tree has a root-to-leaf path such that adding up all the values along the path equals `targetSum`. #### The Key Insight As you DFS down the tree, subtract the current node's value from the target. When you reach a leaf, check if the remaining target is zero. This is DFS with **state carried down** through recursion arguments. #### TypeScript Solution (112 — Path Sum) ```typescript function hasPathSum(root: TreeNode | null, targetSum: number): boolean { if (!root) return false; if (!root.left && !root.right) { return root.val === targetSum; } return ( hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val) ); } ``` #### Problem (113 — Path Sum II) > Find *all* root-to-leaf paths where the sum equals `targetSum`. Now we need to **collect paths**, not just check existence. This means maintaining a running path and adding a copy to results when we find a valid leaf. #### TypeScript Solution (113 — Path Sum II) ```typescript function pathSum(root: TreeNode | null, targetSum: number): number[][] { const result: number[][] = []; function dfs(node: TreeNode | null, remaining: number, path: number[]): void { if (!node) return; path.push(node.val); if (!node.left && !node.right && remaining === node.val) { result.push([...path]); } dfs(node.left, remaining - node.val, path); dfs(node.right, remaining - node.val, path); path.pop(); // backtrack } dfs(root, targetSum, []); return result; } ``` > **The backtracking pattern**: Push before recursing, pop after. This lets you reuse the same `path` array without creating new arrays at every step. The `path.pop()` is crucial — it undoes the choice so the next branch starts clean. #### Complexity - **Time**: O(n) for both — visit every node - **Space**: O(h) for 112, O(n × h) for 113 (storing all valid paths) --- ### Lowest Common Ancestor (LeetCode 236) This is the classic recursive DFS problem that comes up constantly in interviews. It's beautiful once it clicks. #### Problem > Given a binary tree, find the lowest common ancestor (LCA) of two given nodes `p` and `q`. The LCA is defined as the lowest node in the tree that has both `p` and `q` as descendants (where a node can be a descendant of itself). #### The Key Insight DFS the tree. For each node, ask: is `p` in my left subtree? Is `q` in my right subtree? If one is on each side, **I'm the LCA**. If both are on the same side, the answer is deeper in that subtree. The recursive function returns: - The node itself if it's `p` or `q` - The LCA if found in a subtree - `null` if neither `p` nor `q` is in this subtree #### TypeScript Solution ```typescript function lowestCommonAncestor( root: TreeNode | null, p: TreeNode, q: TreeNode ): TreeNode | null { if (!root || root === p || root === q) return root; const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q); if (left && right) return root; return left ?? right; } ``` #### Walkthrough ``` Tree: 3 / \ 5 1 / \ / \ 6 2 0 8 Find LCA of 5 and 1: - At node 3: left returns 5 (found p), right returns 1 (found q) - Both sides returned non-null → node 3 is the LCA ✓ Find LCA of 5 and 6: - At node 3: left returns 5 (because 5 found itself and 6 is below it) - Right returns null - Answer is 5 (it's an ancestor of itself) ``` The beauty here is that the recursion does all the heavy lifting. You don't need to store paths or find ancestors explicitly. The stack frames naturally propagate the answer upward. #### Complexity - **Time**: O(n) — worst case visit all nodes - **Space**: O(h) — recursion stack --- ### Serialize and Deserialize Binary Tree (LeetCode 297) A hard problem that becomes very manageable with DFS pre-order traversal. #### Problem > Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. #### The Key Insight Use **pre-order DFS** (root → left → right). When you encounter a `null` node, serialize it as a marker (like `"#"`). During deserialization, read tokens in the same pre-order sequence and rebuild the tree recursively. Pre-order works perfectly because the root comes first — when deserializing, you always know which value is the root of the current subtree. #### TypeScript Solution ```typescript function serialize(root: TreeNode | null): string { const parts: string[] = []; function dfs(node: TreeNode | null): void { if (!node) { parts.push("#"); return; } parts.push(String(node.val)); dfs(node.left); dfs(node.right); } dfs(root); return parts.join(","); } function deserialize(data: string): TreeNode | null { const tokens = data.split(","); let index = 0; function dfs(): TreeNode | null { if (tokens[index] === "#") { index++; return null; } const node = new TreeNode(Number(tokens[index])); index++; node.left = dfs(); node.right = dfs(); return node; } return dfs(); } ``` #### Walkthrough ``` Tree: 1 / \ 2 3 / \ 4 5 Serialize: "1,2,#,#,3,4,#,#,5,#,#" Deserialize: Read "1" → create node(1) Read "2" → create node(2), left child of 1 Read "#" → null (left of 2) Read "#" → null (right of 2) Read "3" → create node(3), right child of 1 Read "4" → create node(4), left child of 3 Read "#" → null Read "#" → null Read "5" → create node(5), right child of 3 Read "#" → null Read "#" → null ``` The `index` variable acts as a shared pointer moving through the token array. Each recursive call consumes exactly the tokens it needs. #### Complexity - **Time**: O(n) for both serialize and deserialize - **Space**: O(n) for the string/token array --- ### Diameter of Binary Tree (LeetCode 543) This one introduces a critical DFS technique: **tracking a global maximum while recursing**. #### Problem > Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes. This path may or may not pass through the root. #### The Key Insight At each node, the longest path *through that node* is `leftHeight + rightHeight`. The overall diameter is the maximum of this value across all nodes. So we DFS to compute heights, and at each node, we update a global max. The trick is that the recursive function returns the **height** (for parent computation), but side-effects a **diameter** variable (the actual answer). #### TypeScript Solution ```typescript function diameterOfBinaryTree(root: TreeNode | null): number { let diameter = 0; function height(node: TreeNode | null): number { if (!node) return 0; const left = height(node.left); const right = height(node.right); diameter = Math.max(diameter, left + right); return 1 + Math.max(left, right); } height(root); return diameter; } ``` #### Walkthrough ``` Tree: 1 / \ 2 3 / \ 4 5 height(4) = 1, height(5) = 1 height(2): left=1, right=1, diameter = max(0, 1+1) = 2, returns 2 height(3): returns 1 height(1): left=2, right=1, diameter = max(2, 2+1) = 3, returns 3 Answer: 3 (path: 4 → 2 → 1 → 3, or 5 → 2 → 1 → 3) ``` > **Pattern to remember**: When the answer at each node depends on information from both subtrees, compute it during the DFS and track the global optimum with a closure variable. The function returns one thing (height) but computes another (diameter). This "compute answer as a side effect" pattern appears in many tree DFS problems. #### Complexity - **Time**: O(n) - **Space**: O(h) --- ## BFS on Trees BFS on trees is all about **level-order processing**. The queue naturally groups nodes by their depth, which makes level-related questions straightforward. --- ### Level Order Traversal (LeetCode 102) This is the BFS template for trees. Learn this, and every other BFS tree problem is a variation. #### Problem > Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). #### The BFS Tree Template The key technique is processing nodes **one level at a time**. At the start of each iteration, the queue contains exactly the nodes at the current level. You read the queue's length, process that many nodes, and each processed node enqueues its children (which form the next level). #### TypeScript Solution ```typescript function levelOrder(root: TreeNode | null): number[][] { if (!root) return []; const result: number[][] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { const levelSize = queue.length; const currentLevel: number[] = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; currentLevel.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(currentLevel); } return result; } ``` #### Walkthrough ``` Tree: 3 / \ 9 20 / \ 15 7 Queue starts: [3] Level 0: process 1 node → [3], enqueue 9, 20 Queue: [9, 20] Level 1: process 2 nodes → [9, 20], enqueue 15, 7 Queue: [15, 7] Level 2: process 2 nodes → [15, 7], enqueue nothing Queue: [] Result: [[3], [9, 20], [15, 7]] ``` > **The BFS tree template**: `while (queue not empty) { levelSize = queue.length; for i in levelSize { process node, enqueue children } }`. This "process by level" pattern is the foundation of almost every BFS tree problem. Memorize it. #### Complexity - **Time**: O(n) — every node processed once - **Space**: O(w) — max width of the tree (worst case O(n) for a complete tree's last level) --- ### Binary Tree Right Side View (LeetCode 199) #### Problem > Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom. #### The Key Insight BFS level by level. The **last node** in each level is visible from the right side. Just grab the last element of each level. #### TypeScript Solution ```typescript function rightSideView(root: TreeNode | null): number[] { if (!root) return []; const result: number[] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; if (i === levelSize - 1) { result.push(node.val); } if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } return result; } ``` Same template as level order, but instead of collecting all nodes per level, we only keep the last one. That's the whole trick. #### Complexity - **Time**: O(n) - **Space**: O(w) --- ### Minimum Depth of Binary Tree (LeetCode 111) This problem beautifully demonstrates **why BFS is the right tool** for shortest-path style questions. #### Problem > Given a binary tree, find its minimum depth — the number of nodes along the shortest path from the root to the nearest leaf node. #### The Key Insight BFS explores level by level. The **first leaf node** BFS encounters is guaranteed to be at the minimum depth. No need to explore the rest of the tree. DFS would have to explore *every* path to find the minimum. BFS finds it immediately. #### TypeScript Solution ```typescript function minDepth(root: TreeNode | null): number { if (!root) return 0; const queue: TreeNode[] = [root]; let depth = 0; while (queue.length > 0) { depth++; const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; if (!node.left && !node.right) { return depth; } if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } return depth; } ``` The instant we find a leaf (no left, no right), we return the current depth. BFS guarantees this is the shallowest leaf. > **This is the shortest-path property of BFS**: In any unweighted graph (or tree), BFS finds the shortest path from the source to any reachable node. The first time BFS reaches a node, it does so via the shortest possible route. This is *the* core reason to choose BFS over DFS for shortest-path problems. #### Complexity - **Time**: O(n) worst case, but often much less (stops at first leaf) - **Space**: O(w) --- ### Zigzag Level Order Traversal (LeetCode 103) #### Problem > Given the root of a binary tree, return the zigzag level order traversal — first level left to right, second level right to left, third level left to right, and so on. #### The Key Insight Standard BFS level-order, but alternate the direction each level. On even levels, read left to right. On odd levels, reverse the level array (or read right to left). #### TypeScript Solution ```typescript function zigzagLevelOrder(root: TreeNode | null): number[][] { if (!root) return []; const result: number[][] = []; const queue: TreeNode[] = [root]; let leftToRight = true; while (queue.length > 0) { const levelSize = queue.length; const currentLevel: number[] = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; currentLevel.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } if (!leftToRight) currentLevel.reverse(); result.push(currentLevel); leftToRight = !leftToRight; } return result; } ``` We always enqueue children left-to-right (so the tree structure is preserved), and just reverse the output on alternating levels. Simple and clean. #### Complexity - **Time**: O(n) - **Space**: O(w) --- ### Populating Next Right Pointers (LeetCode 116) #### Problem > Given a **perfect binary tree**, populate each node's `next` pointer to point to its next right node. If there is no next right node, the pointer should be set to `null`. ``` Input: 1 Output: 1 → null / \ / \ 2 3 2 → 3 → null / \ / \ / \ / \ 4 5 6 7 4→5→6→7 → null ``` #### The Key Insight BFS level by level. Within each level, link each node to the next node in the queue. The last node in each level points to `null`. #### TypeScript Solution ```typescript class NodeWithNext { val: number; left: NodeWithNext | null; right: NodeWithNext | null; next: NodeWithNext | null; constructor(val?: number) { this.val = val ?? 0; this.left = null; this.right = null; this.next = null; } } function connect(root: NodeWithNext | null): NodeWithNext | null { if (!root) return null; const queue: NodeWithNext[] = [root]; while (queue.length > 0) { const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; node.next = i < levelSize - 1 ? queue[0] : null; if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } return root; } ``` After shifting a node from the front of the queue, the next node in the queue (if we're not at the end of the level) is its right neighbor. So `node.next = queue[0]` works perfectly. #### Complexity - **Time**: O(n) - **Space**: O(w) for the queue --- ## DFS on Graphs Now things get interesting. Graphs introduce two complications that trees don't have: **cycles** and **multiple paths to the same node**. This means we need a **visited set** to avoid infinite loops and redundant work. --- ### Number of Islands (LeetCode 200) This is *the* gateway graph DFS problem. If you've never done graph DFS before, start here. #### Problem > Given an `m × n` 2D grid of `'1'`s (land) and `'0'`s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. #### Examples ``` Input: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Output: 3 ``` #### The Key Insight This grid is an **implicit graph**: each cell is a node, and edges connect horizontally/vertically adjacent land cells. An island is a **connected component** of land cells. The strategy: scan the grid. When you find a `'1'` you haven't visited, that's a new island. DFS (flood fill) from that cell to mark all connected land cells as visited. Increment your island count. Repeat. We can mark cells as visited by changing `'1'` to `'0'` (sinking the island), which avoids needing a separate visited set. #### TypeScript Solution ```typescript function numIslands(grid: string[][]): number { const rows = grid.length; const cols = grid[0].length; let count = 0; function dfs(r: number, c: number): void { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === "0") { return; } grid[r][c] = "0"; dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === "1") { count++; dfs(r, c); } } } return count; } ``` #### Walkthrough ``` Grid: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Scan (0,0): it's a '1' → island #1! DFS flood-fills all connected 1s to 0s. After DFS: top-left block is gone. Scan continues... (2,2): it's a '1' → island #2! DFS marks it. Scan continues... (3,3): it's a '1' → island #3! DFS marks (3,3) and (3,4). Total: 3 islands. ``` > **Grid DFS template**: Check bounds, check visited, mark visited, recurse in 4 directions. This exact pattern works for any grid exploration problem. The four directions `(r±1, c)` and `(r, c±1)` are your graph edges. #### Complexity - **Time**: O(m × n) — visit every cell at most once - **Space**: O(m × n) — recursion stack in worst case (all land) --- ### Clone Graph (LeetCode 133) #### Problem > Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value and a list of its neighbors. #### The Key Insight DFS through the graph. For each node, create a clone. Use a **hashmap** from original node to cloned node to: 1. Avoid cloning a node twice (it's your visited set) 2. Look up already-cloned neighbors when building adjacency lists #### TypeScript Solution ```typescript class GraphNode { val: number; neighbors: GraphNode[]; constructor(val?: number, neighbors?: GraphNode[]) { this.val = val ?? 0; this.neighbors = neighbors ?? []; } } function cloneGraph(node: GraphNode | null): GraphNode | null { if (!node) return null; const cloned = new Map(); function dfs(original: GraphNode): GraphNode { if (cloned.has(original)) return cloned.get(original)!; const copy = new GraphNode(original.val); cloned.set(original, copy); for (const neighbor of original.neighbors) { copy.neighbors.push(dfs(neighbor)); } return copy; } return dfs(node); } ``` The map serves double duty: it's both the "visited" set (preventing infinite loops in cyclic graphs) and the lookup table for already-created clones. #### Complexity - **Time**: O(V + E) — visit every node and edge once - **Space**: O(V) — the clone map --- ### Course Schedule (LeetCode 207) This is **cycle detection in a directed graph** — one of the most important graph DFS patterns. #### 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 (i.e., there are no circular dependencies). #### The Key Insight This is a directed graph where an edge `b → a` means "b must come before a." If there's a **cycle**, you can't complete all courses. So the problem reduces to: **does this directed graph contain a cycle?** The DFS coloring technique uses three states: - **White (0)**: unvisited - **Gray (1)**: currently being processed (in the current DFS path) - **Black (2)**: fully processed (all descendants explored) If DFS visits a **gray** node, we've found a back edge — a cycle! #### TypeScript Solution ```typescript function canFinish(numCourses: number, prerequisites: number[][]): boolean { const graph: number[][] = Array.from({ length: numCourses }, () => []); for (const [course, prereq] of prerequisites) { graph[prereq].push(course); } const color = new Array(numCourses).fill(0); // 0=white, 1=gray, 2=black function dfs(node: number): boolean { if (color[node] === 1) return false; // cycle detected if (color[node] === 2) return true; // already fully processed color[node] = 1; // mark gray (in progress) for (const neighbor of graph[node]) { if (!dfs(neighbor)) return false; } color[node] = 2; // mark black (done) return true; } for (let i = 0; i < numCourses; i++) { if (!dfs(i)) return false; } return true; } ``` #### Walkthrough ``` Courses: 4, Prerequisites: [[1,0], [2,0], [3,1], [3,2]] Graph: 0 → [1, 2] 1 → [3] 2 → [3] 3 → [] DFS from 0: 0(gray) → 1(gray) → 3(gray→black) → 1(black) → 2(gray) → 3(already black, skip) → 2(black) → 0(black) No cycle found → return true With a cycle like [[1,0], [0,1]]: DFS from 0: 0(gray) → 1(gray) → 0(gray!) → cycle detected → return false ``` > **Three-color DFS** is the standard technique for cycle detection in directed graphs. White = unvisited, Gray = in current path, Black = fully explored. A gray-to-gray edge means cycle. This pattern also forms the basis of **topological sort**. #### Complexity - **Time**: O(V + E) - **Space**: O(V + E) — adjacency list + color array --- ### Pacific Atlantic Water Flow (LeetCode 417) #### Problem > Given an `m × n` matrix of heights, water can flow from a cell to an adjacent cell (up, down, left, right) if the adjacent cell's height is **less than or equal to** the current cell's height. Water can flow to the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). Return a list of cells where water can flow to **both** oceans. #### The Key Insight Instead of DFS from every cell asking "can I reach both oceans?" (expensive), flip the perspective: **DFS from the ocean borders inward**. Start from Pacific edges and mark all reachable cells. Start from Atlantic edges and mark all reachable cells. The answer is the intersection. When DFS-ing from the ocean, we go **uphill** (to cells with equal or greater height), because we're tracing the water flow backward. #### TypeScript Solution ```typescript function pacificAtlantic(heights: number[][]): number[][] { const rows = heights.length; const cols = heights[0].length; const pacific = Array.from({ length: rows }, () => new Array(cols).fill(false)); const atlantic = Array.from({ length: rows }, () => new Array(cols).fill(false)); function dfs(r: number, c: number, reachable: boolean[][], prevHeight: number): void { if ( r < 0 || r >= rows || c < 0 || c >= cols || reachable[r][c] || heights[r][c] < prevHeight ) { return; } reachable[r][c] = true; const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]; for (const [dr, dc] of dirs) { dfs(r + dr, c + dc, reachable, heights[r][c]); } } for (let r = 0; r < rows; r++) { dfs(r, 0, pacific, heights[r][0]); dfs(r, cols - 1, atlantic, heights[r][cols - 1]); } for (let c = 0; c < cols; c++) { dfs(0, c, pacific, heights[0][c]); dfs(rows - 1, c, atlantic, heights[rows - 1][c]); } const result: number[][] = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (pacific[r][c] && atlantic[r][c]) { result.push([r, c]); } } } return result; } ``` > **Multi-source DFS from borders** is a powerful technique. Instead of running DFS from every interior cell (which would be O(m×n) DFS runs), we start from the borders and mark reachability inward. This reduces the work to O(m×n) total. The trick is reversing the direction — think "what cells can reach the ocean?" becomes "what cells can the ocean reach going uphill?" #### Complexity - **Time**: O(m × n) — each cell visited at most twice (once per ocean) - **Space**: O(m × n) — two reachability matrices --- ### Surrounded Regions (LeetCode 130) #### Problem > Given an `m × n` board containing `'X'` and `'O'`, capture all regions that are 4-directionally surrounded by `'X'`. A region is captured by flipping all `'O'`s into `'X'`s. `'O'`s on the border (and connected to the border) are NOT captured. #### The Key Insight Instead of trying to figure out which `O`s are surrounded (complex), figure out which `O`s are **NOT surrounded** — those connected to the border. DFS from every border `O` and mark them as safe. Then flip everything else. #### TypeScript Solution ```typescript function solve(board: string[][]): void { const rows = board.length; const cols = board[0].length; function dfs(r: number, c: number): void { if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== "O") { return; } board[r][c] = "S"; // mark as safe dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); } for (let r = 0; r < rows; r++) { dfs(r, 0); dfs(r, cols - 1); } for (let c = 0; c < cols; c++) { dfs(0, c); dfs(rows - 1, c); } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (board[r][c] === "O") board[r][c] = "X"; // captured else if (board[r][c] === "S") board[r][c] = "O"; // restore safe } } } ``` #### Walkthrough ``` Board: After border DFS: Final: X X X X X X X X X X X X X O O X → X O O X → X X X X X X O X X X O X X X X X X O X X X S X X X O X X The 'O' at (3,1) is connected to the border → marked 'S' → restored to 'O'. Interior 'O's at (1,1), (1,2), (2,2) are not connected to border → flipped to 'X'. ``` Same "DFS from border" pattern as Pacific Atlantic. Think backwards: instead of asking "is this cell surrounded?", ask "is this cell connected to the edge?" #### Complexity - **Time**: O(m × n) - **Space**: O(m × n) — recursion stack worst case --- ## BFS on Graphs Graph BFS shines when you need **shortest paths** in unweighted graphs, **level-by-level processing**, or **multi-source spreading**. The queue guarantees that you explore nodes in order of their distance from the source. --- ### Word Ladder (LeetCode 127) This problem is the poster child for "BFS finds shortest paths." #### Problem > Given two words `beginWord` and `endWord`, and a dictionary `wordList`, return the length of the shortest transformation sequence from `beginWord` to `endWord`, such that: > - Only one letter can be changed at a time. > - Each transformed word must exist in the word list. > > Return 0 if no transformation sequence exists. #### Examples ``` Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: "hit" → "hot" → "dot" → "dog" → "cog" ``` #### The Key Insight Think of each word as a **node** in a graph. Two words are connected by an edge if they differ by exactly one letter. The problem asks for the **shortest path** from `beginWord` to `endWord`. Shortest path in an unweighted graph = **BFS**. Why not DFS? DFS might find "hit" → "hot" → "lot" → "log" → "cog" (length 5) but then backtrack and try another path. It doesn't guarantee the shortest. BFS explores all paths of length k before any path of length k+1, so the first time it reaches `endWord`, that's the shortest transformation. For finding neighbors efficiently, we use a wildcard pattern: for "hot", the patterns are `*ot`, `h*t`, `ho*`. We precompute a map from patterns to words. #### TypeScript Solution ```typescript function ladderLength(beginWord: string, endWord: string, wordList: string[]): number { const wordSet = new Set(wordList); if (!wordSet.has(endWord)) return 0; const queue: [string, number][] = [[beginWord, 1]]; const visited = new Set([beginWord]); while (queue.length > 0) { const [word, steps] = queue.shift()!; for (let i = 0; i < word.length; i++) { const chars = word.split(""); for (let c = 97; c <= 122; c++) { // 'a' to 'z' chars[i] = String.fromCharCode(c); const nextWord = chars.join(""); if (nextWord === endWord) return steps + 1; if (wordSet.has(nextWord) && !visited.has(nextWord)) { visited.add(nextWord); queue.push([nextWord, steps + 1]); } } } } return 0; } ``` #### Why BFS Beats DFS Here | Approach | Behavior | Guarantee | |----------|----------|-----------| | **BFS** | Explores all 1-step transformations, then all 2-step, then 3-step... | First path found is shortest | | **DFS** | Dives deep into one transformation chain | Finds *a* path, possibly very long | To find shortest path with DFS, you'd need to explore *all* paths and take the minimum — exponentially slower. #### Complexity - **Time**: O(M² × N) where M = word length, N = number of words - **Space**: O(M × N) — visited set and queue --- ### Rotting Oranges (LeetCode 994) A beautiful multi-source BFS problem. #### Problem > In an `m × n` grid, each cell can have one of three values: `0` (empty), `1` (fresh orange), `2` (rotten orange). Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains. If impossible, return -1. #### The Key Insight All rotten oranges rot their neighbors simultaneously. This is **multi-source BFS**: start with all rotten oranges in the queue at once (they're all at "distance 0"), then spread outward level by level. Each level = one minute. #### TypeScript Solution ```typescript function orangesRotting(grid: number[][]): number { const rows = grid.length; const cols = grid[0].length; const queue: [number, number][] = []; let fresh = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 2) queue.push([r, c]); else if (grid[r][c] === 1) fresh++; } } if (fresh === 0) return 0; const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]; let minutes = 0; while (queue.length > 0) { const levelSize = queue.length; let rotted = false; for (let i = 0; i < levelSize; i++) { const [r, c] = queue.shift()!; for (const [dr, dc] of dirs) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) { grid[nr][nc] = 2; fresh--; rotted = true; queue.push([nr, nc]); } } } if (rotted) minutes++; } return fresh === 0 ? minutes : -1; } ``` #### Walkthrough ``` Grid: 2 1 1 1 1 0 0 1 1 Minute 0: Queue = [(0,0)] (initial rotten), fresh = 6 Minute 1: (0,0) rots (0,1) and (1,0). fresh = 4 Minute 2: (0,1) rots (0,2), (1,0) rots (1,1). fresh = 2 Minute 3: (0,2) does nothing new, (1,1) rots (2,1). fresh = 1 Minute 4: (2,1) rots (2,2). fresh = 0 Answer: 4 minutes ``` > **Multi-source BFS** is just regular BFS where you start with **multiple nodes** in the queue instead of one. The "ripple" spreads outward from all sources simultaneously. Each level of BFS corresponds to one time step, one distance increment, or one "round" of spreading. This is the same conceptual pattern as dropping multiple pebbles into a pond at once. #### Complexity - **Time**: O(m × n) - **Space**: O(m × n) — queue in worst case --- ### 01 Matrix (LeetCode 542) #### Problem > Given an `m × n` binary matrix, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. #### The Key Insight Multi-source BFS from all the `0` cells simultaneously. Start with every `0` in the queue at distance 0. Spread outward, and each `1` cell gets its distance when BFS first reaches it. This is conceptually the same as Rotting Oranges — the `0` cells are like the "rotten" source, and the `1` cells are the "fresh" ones waiting to be reached. #### TypeScript Solution ```typescript function updateMatrix(mat: number[][]): number[][] { const rows = mat.length; const cols = mat[0].length; const dist = Array.from({ length: rows }, () => new Array(cols).fill(Infinity)); const queue: [number, number][] = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (mat[r][c] === 0) { dist[r][c] = 0; queue.push([r, c]); } } } const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]; while (queue.length > 0) { const [r, c] = queue.shift()!; for (const [dr, dc] of dirs) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] > dist[r][c] + 1) { dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]); } } } return dist; } ``` The `dist[nr][nc] > dist[r][c] + 1` check acts as both the "visited" guard and the distance update. If we've already found a shorter path, we skip. #### Complexity - **Time**: O(m × n) - **Space**: O(m × n) --- ### Open the Lock (LeetCode 752) This problem takes BFS into **state space** — the graph isn't a grid or explicit adjacency list. It's an abstract space of states. #### Problem > You have a lock with 4 circular wheels, each with digits 0-9. Starting from `"0000"`, each move turns one wheel one slot (up or down, 9 wraps to 0 and vice versa). Given a list of `deadends` (states that lock you out) and a `target`, return the minimum number of moves to reach the target, or -1 if impossible. #### The Key Insight Each lock state is a node. Each turn of a wheel creates an edge to a new state. There are 10⁴ = 10,000 possible states. We want the **shortest path** from `"0000"` to `target`, avoiding deadends. Shortest path = BFS. #### TypeScript Solution ```typescript function openLock(deadends: string[], target: string): number { const dead = new Set(deadends); if (dead.has("0000")) return -1; if (target === "0000") return 0; const visited = new Set(["0000"]); const queue: [string, number][] = [["0000", 0]]; while (queue.length > 0) { const [state, moves] = queue.shift()!; for (let i = 0; i < 4; i++) { for (const delta of [-1, 1]) { const digits = state.split(""); digits[i] = String((Number(digits[i]) + delta + 10) % 10); const next = digits.join(""); if (next === target) return moves + 1; if (!visited.has(next) && !dead.has(next)) { visited.add(next); queue.push([next, moves + 1]); } } } } return -1; } ``` #### Walkthrough ``` Target: "0202", Deadends: ["0201","0101","0102","1212","2002"] "0000" → 8 neighbors (turn each of 4 wheels up or down) → "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009" Keep exploring level by level... Eventually: "0000" → "0900" → "0800" → "0802" → ... → "0202" BFS guarantees the minimum number of turns. ``` > **State-space BFS**: When the "graph" isn't given explicitly but is defined by valid transitions between states, BFS still works perfectly. Each state is a node, each valid transition is an edge, and BFS finds the shortest sequence of transitions. This pattern applies to puzzles, games, and constraint satisfaction problems. #### Complexity - **Time**: O(10⁴ × 8) — at most 10,000 states, each with 8 neighbors - **Space**: O(10⁴) — visited set --- ## DFS vs BFS: When to Use Which This is the million-dollar question. After all those problems, let's crystallize the decision framework. ### The Decision Table | Situation | Use | Why | |-----------|-----|-----| | Find **shortest path** (unweighted) | **BFS** | BFS explores by distance — first arrival is shortest | | Find **any path** / check **existence** | **Either** (DFS simpler) | Both work; DFS needs less code | | Explore **all paths** / all solutions | **DFS** | DFS naturally backtracks through all possibilities | | **Level-by-level** processing | **BFS** | Queue groups nodes by level naturally | | **Connected components** | **Either** (DFS simpler) | Both work; DFS is more concise | | **Cycle detection** (directed graph) | **DFS** | Three-color technique is DFS-based | | **Topological sort** | **DFS** | Post-order DFS gives reverse topological order | | Memory constrained + **deep, narrow** tree | **BFS** | BFS uses O(w); DFS would use O(h) where h ≈ n | | Memory constrained + **wide, shallow** tree | **DFS** | DFS uses O(h); BFS would use O(w) where w ≈ n | | **Shortest transformation** / minimum steps | **BFS** | Same as shortest path | | **Multi-source spreading** (rotting oranges, fire) | **BFS** | Start with all sources in queue simultaneously | ### The Quick Heuristic Ask yourself these three questions: 1. **Does the problem mention "shortest," "minimum steps," or "fewest moves"?** → BFS. 2. **Does the problem ask for "all paths," "all combinations," or "any valid solution"?** → DFS. 3. **Does the problem involve levels, layers, or simultaneous spreading?** → BFS. If none of these apply, DFS is usually simpler to write (especially with recursion) and is the default choice. > **Rule of thumb**: When in doubt, try DFS first. It's simpler, uses recursion (which is natural for trees), and handles most problems. Switch to BFS when you need shortest paths or level-order properties. --- ## Iterative DFS vs Recursive DFS So far, most of our DFS solutions have been recursive. That's natural and clean for tree problems. But there are situations where you need to convert to an **iterative** approach using an explicit stack. ### When to Go Iterative 1. **Stack overflow risk**: Deep trees or graphs can exceed the recursion limit. JavaScript has a relatively small call stack (~10,000–25,000 frames depending on the engine). 2. **Need more control**: Sometimes you need to inspect the stack, pause and resume, or process nodes in a specific order that's awkward with recursion. 3. **Interview requirement**: Some interviewers specifically ask for iterative DFS to test your understanding. ### The Iterative DFS Template ```typescript function iterativeDFS(root: TreeNode | null): void { if (!root) return; const stack: TreeNode[] = [root]; while (stack.length > 0) { const node = stack.pop()!; // process node here // push right first, so left is processed first (stack is LIFO) if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } } ``` ### Iterative vs Recursive: Side by Side Let's compare with a concrete example — pre-order traversal: **Recursive:** ```typescript function preorderRecursive(root: TreeNode | null, result: number[] = []): number[] { if (!root) return result; result.push(root.val); preorderRecursive(root.left, result); preorderRecursive(root.right, result); return result; } ``` **Iterative:** ```typescript function preorderIterative(root: TreeNode | null): number[] { if (!root) return []; const result: number[] = []; const stack: TreeNode[] = [root]; while (stack.length > 0) { const node = stack.pop()!; result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; } ``` Both produce the same output. The iterative version replaces the call stack with an explicit stack. Push right before left so that left is popped (processed) first. ### Iterative DFS on Graphs For graphs, add a visited set just like you would in recursive DFS: ```typescript function iterativeGraphDFS(graph: Map, start: number): number[] { const visited = new Set(); const stack: number[] = [start]; const result: number[] = []; while (stack.length > 0) { const node = stack.pop()!; if (visited.has(node)) continue; visited.add(node); result.push(node); for (const neighbor of graph.get(node) ?? []) { if (!visited.has(neighbor)) { stack.push(neighbor); } } } return result; } ``` ### Comparison | Aspect | Recursive DFS | Iterative DFS | |--------|--------------|---------------| | **Code clarity** | Cleaner, more intuitive | More verbose | | **Stack management** | Implicit (call stack) | Explicit (your own stack) | | **Stack depth limit** | Limited by engine (~10K–25K) | Limited by heap memory (much larger) | | **State management** | Local variables per frame | Must manage state manually | | **Performance** | Slight overhead per call | Slightly faster in practice | | **When to use** | Trees, moderate-depth graphs | Deep graphs, large inputs | > **Practical advice**: Use recursive DFS for interviews unless the problem has very deep recursion (like a linked list disguised as a tree with 100K nodes). If the interviewer asks for iterative, show the explicit stack version. Knowing both demonstrates depth of understanding. --- ## Multi-Source BFS: The Pattern Explained We've seen multi-source BFS in Rotting Oranges and 01 Matrix. Let's formalize the pattern. ### What Is Multi-Source BFS? Regular BFS starts from **one source** and finds shortest distances from that source. Multi-source BFS starts from **multiple sources simultaneously** and finds the shortest distance from *any* source. ### Why It's Efficient A naive approach might run BFS from each source separately: if there are K sources and V+E vertices/edges, that's O(K × (V+E)). Multi-source BFS does it in **O(V+E)** total. The trick: put all sources in the queue at the start with distance 0. Then run standard BFS. Because all sources start at the same "level," the BFS naturally computes the minimum distance from the nearest source for every node. ### The Template ```typescript function multiSourceBFS( grid: number[][], sources: [number, number][] ): number[][] { const rows = grid.length; const cols = grid[0].length; const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1)); const queue: [number, number][] = []; for (const [r, c] of sources) { dist[r][c] = 0; queue.push([r, c]); } const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]; while (queue.length > 0) { const [r, c] = queue.shift()!; for (const [dr, dc] of dirs) { const nr = r + dr; const nc = c + dc; if ( nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === -1 ) { dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]); } } } return dist; } ``` ### Visualizing It ``` Sources are S. After multi-source BFS, distances: Grid: Distances: . . S . . 2 1 0 1 2 . . . . . 3 2 1 2 3 S . . . . → 0 1 2 3 4 . . . . S 1 2 3 2 1 . . . . . 2 3 4 3 2 Each cell shows distance to nearest S. All sources processed simultaneously — O(V+E), not O(K×(V+E)). ``` > Think of it as a fire spreading from multiple starting points at the same time. Each "minute" (BFS level), the fire extends one step from every active front. The result is the shortest burn time to each cell. --- ## Common Pitfalls After working through all these problems, let's address the mistakes that trip people up most often. ### 1. Forgetting the Visited Set (Graphs) On **trees**, there are no cycles, so you don't need a visited set. On **graphs**, forgetting it means infinite loops. ```typescript // BUG: No visited set on a graph with cycles → infinite loop function brokenDFS(graph: Map, node: number): void { for (const neighbor of graph.get(node) ?? []) { brokenDFS(graph, neighbor); // will revisit nodes forever } } ``` **Fix**: Always use a visited set (or mark nodes) for graph problems. ### 2. Marking Visited Too Late in BFS This is a subtle but critical bug. You should mark a node as visited **when you enqueue it**, not when you dequeue it. ```typescript // BUG: Marking visited on dequeue while (queue.length > 0) { const node = queue.shift()!; visited.add(node); // TOO LATE — node might already be in queue multiple times for (const neighbor of graph.get(node) ?? []) { if (!visited.has(neighbor)) { queue.push(neighbor); } } } ``` The problem: before `node` is dequeued, another path might have already enqueued it. Now it's in the queue twice, leading to redundant processing and potentially wrong answers. ```typescript // CORRECT: Marking visited on enqueue while (queue.length > 0) { const node = queue.shift()!; for (const neighbor of graph.get(node) ?? []) { if (!visited.has(neighbor)) { visited.add(neighbor); // mark BEFORE pushing queue.push(neighbor); } } } ``` > **Rule**: In BFS, mark visited when you **enqueue**, not when you **dequeue**. This prevents duplicate entries in the queue and ensures O(V+E) time. ### 3. Grid Boundary Checks Grids are implicit graphs. Off-by-one errors are the most common bug. Always check bounds first: ```typescript function isValid(r: number, c: number, rows: number, cols: number): boolean { return r >= 0 && r < rows && c >= 0 && c < cols; } ``` Some people prefer defining a directions array to make the code cleaner: ```typescript const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]; for (const [dr, dc] of dirs) { const nr = r + dr; const nc = c + dc; if (isValid(nr, nc, rows, cols)) { // process (nr, nc) } } ``` ### 4. Not Handling Disconnected Graphs If the graph has multiple connected components, a single DFS/BFS from one node won't reach all nodes. You need to loop through all nodes and start a search from each unvisited one: ```typescript const visited = new Set(); for (let node = 0; node < n; node++) { if (!visited.has(node)) { dfs(node, visited); } } ``` This pattern shows up in Number of Islands, Course Schedule, and any problem that says "given a graph" without guaranteeing connectivity. ### 5. Confusing DFS Order on Trees Pre-order (root → left → right), in-order (left → root → right), and post-order (left → right → root) are all DFS — they just differ in *when* you process the root. Choosing the wrong order can give wrong results: - **Pre-order**: Process root first. Good for serialization, copying. - **In-order**: Process root between children. Gives sorted order on BSTs. - **Post-order**: Process root last. Good for computing dependent values (e.g., height, diameter). --- ## Cheat Sheet ### DFS Template — Recursive (Tree) ```typescript function dfs(node: TreeNode | null): ReturnType { if (!node) return baseCase; // pre-order processing (before children) const left = dfs(node.left); // in-order processing (between children) const right = dfs(node.right); // post-order processing (after children) return combineResults(left, right); } ``` ### DFS Template — Iterative (Tree / Graph) ```typescript function iterativeDFS(start: Node): void { const stack: Node[] = [start]; const visited = new Set(); while (stack.length > 0) { const node = stack.pop()!; if (visited.has(node)) continue; visited.add(node); // process node for (const neighbor of node.neighbors) { if (!visited.has(neighbor)) { stack.push(neighbor); } } } } ``` ### BFS Template (Tree — Level Order) ```typescript function bfs(root: TreeNode | null): void { if (!root) return; const queue: TreeNode[] = [root]; while (queue.length > 0) { const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; // process node if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } } ``` ### BFS Template (Graph) ```typescript function bfs(graph: Map, start: number): void { const visited = new Set([start]); const queue: number[] = [start]; while (queue.length > 0) { const node = queue.shift()!; // process node for (const neighbor of graph.get(node) ?? []) { if (!visited.has(neighbor)) { visited.add(neighbor); // mark on enqueue! queue.push(neighbor); } } } } ``` ### Grid Traversal Template (DFS) ```typescript function gridDFS(grid: string[][], r: number, c: number): void { const rows = grid.length; const cols = grid[0].length; if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === "visited") { return; } grid[r][c] = "visited"; gridDFS(grid, r + 1, c); gridDFS(grid, r - 1, c); gridDFS(grid, r, c + 1); gridDFS(grid, r, c - 1); } ``` ### Problem → Pattern Mapping | Problem | Pattern | Key Technique | |---------|---------|--------------| | Max Depth (104) | Tree DFS | Recursive height | | Same Tree (100) | Tree DFS | Parallel recursion | | Invert Tree (226) | Tree DFS | Swap + recurse | | Path Sum (112/113) | Tree DFS | Accumulate state downward | | LCA (236) | Tree DFS | Post-order bubbling | | Serialize Tree (297) | Tree DFS | Pre-order + null markers | | Diameter (543) | Tree DFS | Track global max during DFS | | Level Order (102) | Tree BFS | Queue + level size | | Right Side View (199) | Tree BFS | Last node per level | | Min Depth (111) | Tree BFS | First leaf = answer | | Zigzag (103) | Tree BFS | Alternate reverse | | Next Pointers (116) | Tree BFS | Link within level | | Number of Islands (200) | Grid DFS | Flood fill connected components | | Clone Graph (133) | Graph DFS | Map original→clone | | Course Schedule (207) | Graph DFS | Three-color cycle detection | | Pacific Atlantic (417) | Grid DFS | Multi-source from borders | | Surrounded Regions (130) | Grid DFS | Border DFS + invert logic | | Word Ladder (127) | Graph BFS | Shortest transformation path | | Rotting Oranges (994) | Grid BFS | Multi-source + levels = time | | 01 Matrix (542) | Grid BFS | Multi-source distance | | Open the Lock (752) | State-space BFS | Shortest path in abstract graph | ### Big O Reference | Problem | Time | Space | |---------|------|-------| | Tree DFS (most problems) | O(n) | O(h) | | Tree BFS (most problems) | O(n) | O(w) | | Grid DFS/BFS (m×n grid) | O(m × n) | O(m × n) | | Graph DFS/BFS | O(V + E) | O(V + E) | | Word Ladder | O(M² × N) | O(M × N) | | Open the Lock | O(10⁴ × 8) | O(10⁴) | Where: n = nodes, h = height, w = max width, V = vertices, E = edges, M = word length, N = word count. --- ## What's Next? DFS and BFS are the two eyes through which you see trees and graphs. With these patterns, you've unlocked the ability to tackle hundreds of problems — from simple tree traversals to complex graph exploration, from grid flood fills to abstract state-space searches. If you've been following the "Made Simple" series, here's how DFS and BFS connect to what you already know: - **Recursion** gave you the mental model for DFS — every recursive DFS is just the call stack doing the work for you - **Stacks and Queues** are the literal building blocks — DFS uses a stack, BFS uses a queue - **Binary Search** taught you to think about efficiency — DFS and BFS give you O(V+E) graph exploration, which is optimal - **Two Pointers** taught you to think about structure — BFS level-order processing is a similar "structured sweep" idea Coming up next in the series: - **Backtracking, Made Simple** — DFS extended to explore all combinations, permutations, and constraint satisfaction problems - **Dynamic Programming, Made Simple** — when DFS reveals overlapping subproblems, DP turns exponential into polynomial --- ## Practice Roadmap Build your DFS/BFS fluency in this order. Start easy, build up. ### Tier 1: Tree DFS Fundamentals | Problem | LeetCode # | Focus | |---------|-----------|-------| | Maximum Depth of Binary Tree | 104 | Basic tree DFS | | Same Tree | 100 | Parallel recursion | | Invert Binary Tree | 226 | Recursive transformation | | Path Sum | 112 | DFS with accumulation | ### Tier 2: Tree BFS Fundamentals | Problem | LeetCode # | Focus | |---------|-----------|-------| | Binary Tree Level Order Traversal | 102 | BFS template | | Binary Tree Right Side View | 199 | Level processing | | Minimum Depth of Binary Tree | 111 | BFS shortest path property | | Symmetric Tree | 101 | BFS/DFS comparison | ### Tier 3: Advanced Tree Problems | Problem | LeetCode # | Focus | |---------|-----------|-------| | Lowest Common Ancestor | 236 | Post-order DFS | | Diameter of Binary Tree | 543 | Global max during DFS | | Zigzag Level Order | 103 | BFS with alternation | | Serialize and Deserialize | 297 | DFS pre-order | ### Tier 4: Grid DFS/BFS | Problem | LeetCode # | Focus | |---------|-----------|-------| | Number of Islands | 200 | Grid flood fill | | Surrounded Regions | 130 | Border DFS | | Rotting Oranges | 994 | Multi-source BFS | | 01 Matrix | 542 | Multi-source BFS distances | ### Tier 5: Graph DFS/BFS | Problem | LeetCode # | Focus | |---------|-----------|-------| | Clone Graph | 133 | DFS with visited map | | Course Schedule | 207 | Cycle detection | | Pacific Atlantic Water Flow | 417 | Multi-source border DFS | | Word Ladder | 127 | BFS shortest transformation | | Open the Lock | 752 | State-space BFS | > Don't rush. For each problem, before writing code, ask: "Is this a DFS or BFS problem? Why? Am I looking for shortest path, all paths, or existence? Do I need a visited set? What are my graph's nodes and edges?" Answering these questions first is the real skill. --- ## Thanks for Reading If this guide helped DFS and BFS click for you, share it with someone who's studying. The best way to solidify understanding is to explain the difference between DFS and BFS to someone else — if you can walk through Number of Islands and Word Ladder from memory and explain *why* one uses DFS and the other uses BFS, you own these patterns. Go solve a few problems. Start with Max Depth and Level Order to warm up, work through Number of Islands and Rotting Oranges for graph practice, and when you're ready, tackle Word Ladder. That problem is the graduation exam for BFS — and you've got all the tools to pass it. Keep learning. Keep coding. You've got this. **Your Dev Brain, Now Thinking in Depth and Breadth** ---

Problem Solving Patterns: DFS and BFS, Made Simple