Depth-First Search (DFS) is a traversal algorithm for trees and graphs. It’s called “depth-first” because it explores as far down a path as possible before backtracking to try another path. This makes DFS incredibly versatile, and it’s arguably the most important algorithm to master for coding interviews.
Watch how DFS goes all the way down the left side (A → B → D) before backtracking to visit E, then finally exploring C’s subtree. This “go deep, then backtrack” behavior is what separates DFS from Breadth-First Search, which explores all nodes at one level before moving to the next. We will explore DFS in-depth in upcoming lessons.
Basic DFS Pattern
At its core, DFS follows this simple pattern:
dfs(node) if node is null return // process the current node dfs(node.left) dfs(node.right)
For graphs, you also need to track visited nodes to avoid infinite loops:
dfs(node, visited) if node in visited return visited.add(node) for neighbor in node.neighbors dfs(neighbor, visited)
Module Overview
This module teaches you how to solve coding interview questions using depth-first search. It’s divided into two main sections:
Binary Trees
We start with DFS on binary trees because they’re the simplest structure to work with. Trees have no cycles, so you don’t need to track visited nodes. You’ll learn:
How the call stack enables backtracking
How to use return values to aggregate information from subtrees
Common patterns like finding depth, validating structure, and path problems
Graphs
Graph problems add complexity: you need to handle cycles, different representations (adjacency lists and matrices), and sometimes disconnected components. You’ll practice:
DFS on adjacency list representations
DFS on 2D matrix grids
Patterns like connected components, boundary traversal, and cycle detection
After completing this module, continue to Breadth-First Search and Backtracking. Understanding when to use DFS vs BFS is critical. In short: use DFS when you need to explore all paths or find any valid solution, use BFS when you need the shortest path or level-by-level traversal.
Common DFS Problem Patterns
You’ll encounter a few recurring patterns in DFS problems. Recognizing these patterns quickly will help you identify the right approach during interviews.
Counting Connected Components
One of the most common DFS applications is counting distinct groups or regions in a grid or graph. Think of it as “flood filling” each region and counting how many times you had to start a new fill.
Take this grid where 1 represents land and 0 represents water. The goal is to count distinct islands (groups of connected 1s):
The answer is 4 because there are four separate islands.
The approach works like this: scan every cell in the grid from top-left to bottom-right. When you hit an unvisited 1, you’ve found a new island, so increment your count. Then run DFS to “flood” that entire island, marking every connected 1 as visited (typically by setting it to 0). When DFS returns, that island is fully consumed and won’t be counted again.
Watch the visualization below to see this in action. Notice how DFS explores deeply in one direction before backtracking, and how the count variable only increases when we discover an entirely new island.
def count_islands(grid): rows, cols = len(grid), len(grid[0]) visited = set() count = 0 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(r, c): if (r, c) in visited: return if r < 0 or r >= rows or c < 0 or c >= cols: return if grid[r][c] != 1: return visited.add((r, c)) for dr, dc in directions: dfs(r + dr, c + dc) for r in range(rows): for c in range(cols): if grid[r][c] == 1 and (r, c) not in visited: dfs(r, c) count += 1 return count
public int countIslands(int[][] grid) { int rows = grid.length, cols = grid[0].length; Set<String> visited = new HashSet<>(); int count = 0; int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1 && !visited.contains(r + "," + c)) { dfs(grid, r, c, visited, directions); count++; } } } return count;}void dfs(int[][] grid, int r, int c, Set<String> visited, int[][] dirs) { String key = r + "," + c; if (visited.contains(key)) return; if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return; if (grid[r][c] != 1) return; visited.add(key); for (int[] d : dirs) dfs(grid, r + d[0], c + d[1], visited, dirs);}
func countIslands(grid [][]int) int { rows, cols := len(grid), len(grid[0]) visited := make(map[string]bool) count := 0 dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} var dfs func(r, c int) dfs = func(r, c int) { key := fmt.Sprintf("%d,%d", r, c) if visited[key] { return } if r < 0 || r >= rows || c < 0 || c >= cols { return } if grid[r][c] != 1 { return } visited[key] = true for _, d := range dirs { dfs(r+d[0], c+d[1]) } } for r := 0; r < rows; r++ { for c := 0; c < cols; c++ { key := fmt.Sprintf("%d,%d", r, c) if grid[r][c] == 1 && !visited[key] { dfs(r, c) count++ } } } return count}
function countIslands(grid: number[][]): number { const rows = grid.length, cols = grid[0].length; const visited = new Set<string>(); let count = 0; const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function dfs(r: number, c: number): void { const key = `${r},${c}`; if (visited.has(key)) return; if (r < 0 || r >= rows || c < 0 || c >= cols) return; if (grid[r][c] !== 1) return; visited.add(key); for (const [dr, dc] of directions) { dfs(r + dr!, c + dc!); } } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 1 && !visited.has(`${r},${c}`)) { dfs(r, c); count++; } } } return count;}
The outer loop finds new islands; the DFS consumes each one so we don’t count it twice. This pattern applies to any “count distinct regions” problem, whether it’s islands, rooms in a building, or connected components in a graph.
Boundary DFS
Some problems ask you to find cells that are connected to the edge of a grid, i.e. all connected cells which are on boundary of the matrix. The naive way is to check every cell and finding “can this cell reach the boundary?” But that’s inefficient.
The trick is to flip the question: instead of checking if each cell can reach the border, start from the border and see which cells can be reached from this boundary cell. Run DFS from each relevant cell on the boundary, and everything you visit is “connected to the edge.”
def find_boundary_connected(grid): rows, cols = len(grid), len(grid[0]) visited = set() directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(r, c): if (r, c) in visited: return if r < 0 or r >= rows or c < 0 or c >= cols: return if grid[r][c] != 1: return visited.add((r, c)) for dr, dc in directions: dfs(r + dr, c + dc) # Start DFS from boundary cells with value 1 for r in range(rows): if grid[r][0] == 1: dfs(r, 0) if grid[r][cols-1] == 1: dfs(r, cols-1) for c in range(cols): if grid[0][c] == 1: dfs(0, c) if grid[rows-1][c] == 1: dfs(rows-1, c)
public void findBoundaryConnected(int[][] grid) { int rows = grid.length, cols = grid[0].length; Set<String> visited = new HashSet<>(); int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // Start DFS from boundary cells with value 1 for (int r = 0; r < rows; r++) { if (grid[r][0] == 1) dfs(grid, r, 0, visited, dirs); if (grid[r][cols-1] == 1) dfs(grid, r, cols-1, visited, dirs); } for (int c = 0; c < cols; c++) { if (grid[0][c] == 1) dfs(grid, 0, c, visited, dirs); if (grid[rows-1][c] == 1) dfs(grid, rows-1, c, visited, dirs); }}void dfs(int[][] grid, int r, int c, Set<String> visited, int[][] dirs) { String key = r + "," + c; if (visited.contains(key)) return; if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return; if (grid[r][c] != 1) return; visited.add(key); for (int[] d : dirs) dfs(grid, r + d[0], c + d[1], visited, dirs);}
func findBoundaryConnected(grid [][]int) { rows, cols := len(grid), len(grid[0]) visited := make(map[string]bool) dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // Start DFS from boundary cells with value 1 for r := 0; r < rows; r++ { if grid[r][0] == 1 { dfs(grid, r, 0, visited, dirs) } if grid[r][cols-1] == 1 { dfs(grid, r, cols-1, visited, dirs) } } for c := 0; c < cols; c++ { if grid[0][c] == 1 { dfs(grid, 0, c, visited, dirs) } if grid[rows-1][c] == 1 { dfs(grid, rows-1, c, visited, dirs) } }}func dfs(grid [][]int, r, c int, visited map[string]bool, dirs [][]int) { key := fmt.Sprintf("%d,%d", r, c) if visited[key] { return } if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) { return } if grid[r][c] != 1 { return } visited[key] = true for _, d := range dirs { dfs(grid, r+d[0], c+d[1], visited, dirs) }}
function findBoundaryConnected(grid: number[][]): void { const rows = grid.length, cols = grid[0].length; const visited = new Set<string>(); const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function dfs(r: number, c: number): void { const key = `${r},${c}`; if (visited.has(key)) return; if (r < 0 || r >= rows || c < 0 || c >= cols) return; if (grid[r][c] !== 1) return; visited.add(key); for (const [dr, dc] of directions) { dfs(r + dr!, c + dc!); } } // Start DFS from boundary cells with value 1 for (let r = 0; r < rows; r++) { if (grid[r][0] === 1) dfs(r, 0); if (grid[r][cols-1] === 1) dfs(r, cols-1); } for (let c = 0; c < cols; c++) { if (grid[0][c] === 1) dfs(0, c); if (grid[rows-1][c] === 1) dfs(rows-1, c); }}
This pattern appears in problems like “Surrounded Regions” and “Pacific Atlantic Water Flow.” The key insight is always the same: start from the boundary and work inward.
When to Use DFS
DFS excels when you need to:
Explore all possible paths (like finding all solutions or any valid solution)
