Skip to main content
Mapagam

BFS and DFS Graph Traversal

1. Level Order Traversal (Queue-based BFS)

Component Implementation Purpose Complexity
Queue Structure FIFO - process nodes level by level Guarantees breadth-first order O(1) enqueue/dequeue
Level Tracking Record queue size at start of level Process exactly one level at a time Enables level-specific operations
Visited Set Track processed nodes to avoid cycles Prevent infinite loops in graphs O(V) space for V vertices
Applications Tree level order, graph BFS, shortest path Layer-by-layer exploration O(V + E) for graphs

Example: Binary tree level order traversal

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 in Unweighted Graph (BFS)

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 Using DFS (Graph 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 Iterative Implementation (Stack)

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 Algorithm 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

BFS DFS Graph Traversal Summary

  • BFS Level Order: Queue-based, FIFO, layer-by-layer exploration
  • 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.

Was this article helpful?

Related Cheat Sheets