function levelOrder(root) { if (!root) return []; const result = []; const queue = [root]; while (queue.length > 0) { const levelSize = queue.length; const currentLevel = []; // Process all nodes at current level 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;}// Tree: [3,9,20,null,null,15,7]// 3// / \// 9 20// / \// 15 7// Result: [[3],[9,20],[15,7]]// Time: O(n), Space: O(w) where w is max width
Example: Graph level order BFS
function bfsLevelOrder(graph, start) { const visited = new Set(); const queue = [start]; const levels = []; visited.add(start); while (queue.length > 0) { const levelSize = queue.length; const currentLevel = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift(); currentLevel.push(node); for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); } } } levels.push(currentLevel); } return levels;}// Graph: {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}// BFS from 0: [[0], [1,2], [3]]
Example: Right side view of tree
function rightSideView(root) { if (!root) return []; const result = []; const queue = [root]; while (queue.length > 0) { const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const node = queue.shift(); // Last node in level = rightmost if (i === levelSize - 1) { result.push(node.val); } if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } return result;}// [1,2,3,null,5,null,4] -> [1,3,4]
2. Multi-source BFS Pattern
Concept
Strategy
Use Case
Advantage
Multiple Starting Points
Initialize queue with all sources
Rotten oranges, 0-1 matrix distance
Single pass instead of multiple BFS
Simultaneous Expansion
All sources expand outward together
Natural wave propagation simulation
Correct distance/time calculation
Level = Time/Distance
Each level represents one unit
Minimum time to reach all cells
Level count gives answer directly
Common Applications
Grid problems, nearest point queries
Walls and gates, forest fire spread
O(m*n) for grid
Example: Rotting oranges (multi-source BFS)
function orangesRotting(grid) { const rows = grid.length; const cols = grid[0].length; const queue = []; let fresh = 0; // Find all initially rotten oranges and count fresh for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 2) { queue.push([r, c, 0]); // [row, col, time] } else if (grid[r][c] === 1) { fresh++; } } } const directions = [[0,1], [1,0], [0,-1], [-1,0]]; let minutes = 0; while (queue.length > 0) { const [r, c, time] = queue.shift(); minutes = Math.max(minutes, time); 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) { grid[nr][nc] = 2; // Make rotten fresh--; queue.push([nr, nc, time + 1]); } } } return fresh === 0 ? minutes : -1;}// [[2,1,1],[1,1,0],[0,1,1]] -> 4// All oranges rot simultaneously from all rotten sources
Example: 0-1 matrix (distance to nearest 0)
function updateMatrix(mat) { const rows = mat.length; const cols = mat[0].length; const queue = []; const dist = Array(rows).fill(null) .map(() => Array(cols).fill(Infinity)); // Initialize with all 0s for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (mat[r][c] === 0) { queue.push([r, c]); dist[r][c] = 0; } } } const directions = [[0,1], [1,0], [0,-1], [-1,0]]; while (queue.length > 0) { const [r, c] = queue.shift(); for (const [dr, dc] of directions) { 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;}// [[0,0,0],[0,1,0],[1,1,1]]// -> [[0,0,0],[0,1,0],[1,2,1]]
3. Shortest Path BFS Unweighted
Property
Details
Guarantee
Why It Works
Unweighted Graphs
All edges have weight 1
BFS finds shortest path
Level order = distance order
First Reach = Shortest
First time visiting a node is shortest
No need to revisit
BFS explores by increasing distance
Path Reconstruction
Store parent pointers during BFS
Backtrack from target to source
Parent map traces shortest path
Time Complexity
O(V + E) for adjacency list
Each vertex/edge visited once
Linear in graph size
Example: Shortest path in unweighted graph
function shortestPath(graph, start, target) { const queue = [[start, 0]]; // [node, distance] const visited = new Set([start]); const parent = new Map(); parent.set(start, null); while (queue.length > 0) { const [node, dist] = queue.shift(); if (node === target) { // Reconstruct path const path = []; let current = target; while (current !== null) { path.unshift(current); current = parent.get(current); } return { distance: dist, path }; } for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { visited.add(neighbor); parent.set(neighbor, node); queue.push([neighbor, dist + 1]); } } } return { distance: -1, path: [] }; // No path found}// Graph: {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}// shortestPath(graph, 0, 3) -> {distance: 2, path: [0,1,3]}
Example: Word ladder (shortest transformation)
function ladderLength(beginWord, endWord, wordList) { const wordSet = new Set(wordList); if (!wordSet.has(endWord)) return 0; const queue = [[beginWord, 1]]; // [word, level] const visited = new Set([beginWord]); while (queue.length > 0) { const [word, level] = queue.shift(); if (word === endWord) return level; // Try all possible one-letter changes for (let i = 0; i < word.length; i++) { for (let c = 97; c <= 122; c++) { // 'a' to 'z' const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1); if (wordSet.has(newWord) && !visited.has(newWord)) { visited.add(newWord); queue.push([newWord, level + 1]); } } } } return 0; // No transformation found}// beginWord="hit", endWord="cog"// wordList=["hot","dot","dog","lot","log","cog"]// -> 5 (hit -> hot -> dot -> dog -> cog)
4. Cycle Detection DFS Coloring
Color
Meaning
State
Detection Rule
White (0)
Not visited yet
Initial state
Start DFS from here
Gray (1)
Currently being processed
In DFS recursion stack
If we reach gray node = cycle!
Black (2)
Completely processed
All descendants visited
No cycle through this node
Cycle Detection
Edge to gray node during DFS
Back edge found
Indicates cycle in directed graph
Example: Detect cycle in directed graph (DFS coloring)
function hasCycle(graph) { const n = graph.length; const color = Array(n).fill(0); // 0=white, 1=gray, 2=black function dfs(node) { color[node] = 1; // Mark as being processed (gray) for (const neighbor of graph[node]) { if (color[neighbor] === 1) { // Back edge to gray node = cycle! return true; } if (color[neighbor] === 0) { if (dfs(neighbor)) return true; } // If black (2), skip - already processed } color[node] = 2; // Mark as completely processed (black) return false; } // Check all components for (let i = 0; i < n; i++) { if (color[i] === 0) { if (dfs(i)) return true; } } return false;}// Graph: [[1], [2], [0]] (0→1→2→0) -> true (cycle)// Graph: [[1], [2], []] (0→1→2) -> false (no cycle)
Example: Course schedule (cycle detection)
function canFinish(numCourses, prerequisites) { // Build adjacency list const graph = Array(numCourses).fill(null).map(() => []); for (const [course, prereq] of prerequisites) { graph[prereq].push(course); } const color = Array(numCourses).fill(0); function hasCycleDFS(node) { color[node] = 1; // Gray - in progress for (const neighbor of graph[node]) { if (color[neighbor] === 1) { return true; // Cycle detected } if (color[neighbor] === 0 && hasCycleDFS(neighbor)) { return true; } } color[node] = 2; // Black - completed return false; } for (let i = 0; i < numCourses; i++) { if (color[i] === 0 && hasCycleDFS(i)) { return false; // Cycle exists, can't finish } } return true; // No cycles, can finish all courses}// numCourses=2, prerequisites=[[1,0]]// -> true (take 0, then 1)// numCourses=2, prerequisites=[[1,0],[0,1]]// -> false (circular dependency)
5. Bidirectional BFS Optimization
Technique
Strategy
Benefit
Complexity
Two-ended Search
BFS from both start and end simultaneously
Meet in middle, reduces search space
O(b^(d/2)) vs O(b^d)
Alternating Expansion
Expand from smaller frontier each iteration
Balanced growth, better performance
Minimizes total nodes explored
Intersection Detection
Check if frontiers meet during expansion
Path found when they intersect
Sum of levels = shortest path length
Use Cases
Large graphs, long shortest paths
Exponential speedup possible
Best when branching factor is high
Example: Bidirectional BFS for shortest path
function bidirectionalBFS(graph, start, target) { if (start === target) return 0; const frontQueue = [start]; const backQueue = [target]; const frontVisited = new Map([[start, 0]]); const backVisited = new Map([[target, 0]]); let level = 0; while (frontQueue.length > 0 || backQueue.length > 0) { level++; // Expand from smaller frontier if (frontQueue.length <= backQueue.length) { // Expand forward const size = frontQueue.length; for (let i = 0; i < size; i++) { const node = frontQueue.shift(); for (const neighbor of graph[node]) { // Check if backward search reached this if (backVisited.has(neighbor)) { return frontVisited.get(node) + 1 + backVisited.get(neighbor); } if (!frontVisited.has(neighbor)) { frontVisited.set(neighbor, frontVisited.get(node) + 1); frontQueue.push(neighbor); } } } } else { // Expand backward const size = backQueue.length; for (let i = 0; i < size; i++) { const node = backQueue.shift(); for (const neighbor of graph[node]) { // Check if forward search reached this if (frontVisited.has(neighbor)) { return backVisited.get(node) + 1 + frontVisited.get(neighbor); } if (!backVisited.has(neighbor)) { backVisited.set(neighbor, backVisited.get(node) + 1); backQueue.push(neighbor); } } } } } return -1; // No path}// Reduces O(b^d) to O(b^(d/2)) where b=branching, d=depth
6. DFS Stack Iterative Implementation
Approach
Structure
Advantage
Drawback
Recursive DFS
Call stack (implicit stack)
Clean, intuitive code
Stack overflow risk for deep graphs
Iterative DFS
Explicit stack data structure
No stack overflow, controllable
More verbose, manual state management
Stack Operations
LIFO - push children, pop to visit
Mimics recursion behavior
O(V) space for stack
Visit Order
Depth-first, explores one path fully
Good for path-finding, topological sort
Not optimal for shortest path
Example: DFS recursive
function dfsRecursive(graph, start) { const visited = new Set(); const result = []; function dfs(node) { if (visited.has(node)) return; visited.add(node); result.push(node); for (const neighbor of graph[node]) { dfs(neighbor); } } dfs(start); return result;}// Clean and intuitive// Risk: Stack overflow for deep graphs
Example: DFS iterative with stack
function dfsIterative(graph, start) { const visited = new Set(); const stack = [start]; const result = []; while (stack.length > 0) { const node = stack.pop(); if (visited.has(node)) continue; visited.add(node); result.push(node); // Push neighbors in reverse order // to maintain left-to-right DFS for (let i = graph[node].length - 1; i >= 0; i--) { stack.push(graph[node][i]); } } return result;}// No recursion, no stack overflow
Example: DFS iterative with pre/post-order tracking
function dfsWithTimestamps(graph, start) { const visited = new Set(); const stack = [[start, 'pre']]; // [node, phase] const preOrder = []; const postOrder = []; while (stack.length > 0) { const [node, phase] = stack.pop(); if (phase === 'pre') { if (visited.has(node)) continue; visited.add(node); preOrder.push(node); // Push post-order marker stack.push([node, 'post']); // Push children for pre-order for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { stack.push([neighbor, 'pre']); } } } else { // Post-order - all children processed postOrder.push(node); } } return { preOrder, postOrder };}// Useful for topological sort (post-order reversed)
7. Flood Fill Pattern
Technique
Implementation
Use Case
Complexity
4-directional Fill
Up, down, left, right neighbors
Standard grid connectivity
4 neighbors per cell
8-directional Fill
Include diagonals
Chess king moves, island variants
8 neighbors per cell
DFS Approach
Recursively fill connected cells
Simple, clean code
O(m*n) time, O(m*n) stack worst case
BFS Approach
Queue-based level-by-level fill
Safer for large grids (no stack overflow)
O(m*n) time, O(min(m,n)) queue
Example: Flood fill DFS
function floodFill(image, sr, sc, color) { const originalColor = image[sr][sc]; if (originalColor === color) return image; const rows = image.length; const cols = image[0].length; function dfs(r, c) { if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] !== originalColor) { return; } image[r][c] = color; // 4-directional flood fill dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); } dfs(sr, sc); return image;}// image=[[1,1,1],[1,1,0],[1,0,1]]// sr=1, sc=1, color=2// -> [[2,2,2],[2,2,0],[2,0,1]]
Example: Flood fill BFS
function floodFillBFS(image, sr, sc, color) { const originalColor = image[sr][sc]; if (originalColor === color) return image; const rows = image.length; const cols = image[0].length; const queue = [[sr, sc]]; const directions = [[0,1],[1,0],[0,-1],[-1,0]]; image[sr][sc] = color; while (queue.length > 0) { const [r, c] = queue.shift(); for (const [dr, dc] of directions) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) { image[nr][nc] = color; queue.push([nr, nc]); } } } return image;}// Safer for large grids
Example: Number of islands (flood fill variant)
function numIslands(grid) { if (!grid || grid.length === 0) return 0; const rows = grid.length; const cols = grid[0].length; let count = 0; function dfs(r, c) { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') { return; } grid[r][c] = '0'; // Mark as visited 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); // Flood fill entire island } } } return count;}// [["1","1","0"],// ["1","1","0"],// ["0","0","1"]]// -> 2 islands// Time: O(m*n), Space: O(m*n) recursion stack worst case
Multi-source BFS: Initialize queue with all sources, single pass
Shortest Path: BFS guarantees shortest in unweighted graphs
Cycle Detection: DFS with 3-color (white/gray/black) scheme
Bidirectional BFS: Search from both ends, O(b^(d/2)) speedup
DFS Iterative: Explicit stack, no recursion, no stack overflow
Flood Fill: DFS or BFS to fill connected regions
Note:BFS is optimal for shortest path in unweighted graphs and level-order traversal. DFS is better for topological sort, cycle detection, and path enumeration. For very large graphs or deep paths, use iterative DFS to avoid stack overflow.
Warning: Always track visited nodes in graphs to prevent infinite loops. For grids, either mark cells in-place or use a separate visited set. In DFS cycle detection, distinguish between gray (in current path) and black (fully processed) to correctly identify back edges.