Depth-First Search (DFS) Pattern

Depth-First Search (DFS) is a traversal algorithm that explores as far as possible along each branch before backtracking. It's used for exploring all paths or branches in graphs or trees.

When to Use This Pattern

  • Exploring all paths in graphs or trees
  • Finding connected components
  • Topological sorting
  • Finding cycles in graphs
  • Path finding problems
  • Tree/graph traversal

Key Concepts

DFS can be implemented using:

  • Recursion: Natural for tree/graph traversal
  • Stack: Iterative approach using explicit stack

Algorithm Section

Recursive DFS

def dfs_recursive(node, visited):
    visited.add(node)
    # Process node
    
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs_recursive(neighbor, visited)

Iterative DFS

def dfs_iterative(start):
    stack = [start]
    visited = set()
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # Process node
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    stack.append(neighbor)

Practice Problems

Problem 1: Clone Graph (LeetCode #133)

Given a reference of a node in a connected undirected graph, return a deep copy of the graph.

Solution:

def cloneGraph(node):
    if not node:
        return None
    
    clone_map = {}
    
    def dfs(original):
        if original in clone_map:
            return clone_map[original]
        
        clone = Node(original.val)
        clone_map[original] = clone
        
        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

Explanation: We use DFS to traverse the graph. For each node, we create a clone and recursively clone all neighbors. We use a map to avoid creating duplicate clones and handle cycles.

Time Complexity: O(V + E)

Space Complexity: O(V)

Problem 2: Path Sum II (LeetCode #113)

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum.

Solution:

def pathSum(root, targetSum):
    result = []
    
    def dfs(node, path, remaining):
        if not node:
            return
        
        path.append(node.val)
        remaining -= node.val
        
        if not node.left and not node.right and remaining == 0:
            result.append(path[:])
        
        dfs(node.left, path, remaining)
        dfs(node.right, path, remaining)
        
        path.pop()  # Backtrack
    
    dfs(root, [], targetSum)
    return result

Explanation: We use DFS to explore all paths. We maintain current path and remaining sum. When we reach a leaf with remaining == 0, we found a valid path. We backtrack by removing the node from path after exploring its children.

Time Complexity: O(n)

Space Complexity: O(h) where h is height

Problem 3: Course Schedule II (LeetCode #210)

There are a total of numCourses courses you have to take. Return the ordering of courses you should take to finish all courses.

Solution:

def findOrder(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)
    
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * numCourses
    result = []
    
    def dfs(node):
        if color[node] == GRAY:
            return False  # Cycle detected
        if color[node] == BLACK:
            return True
        
        color[node] = GRAY
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        
        color[node] = BLACK
        result.append(node)
        return True
    
    for i in range(numCourses):
        if color[i] == WHITE:
            if not dfs(i):
                return []
    
    return result[::-1]

Explanation: We use DFS with three colors: WHITE (unvisited), GRAY (visiting), BLACK (visited). GRAY indicates we're in the current path - if we encounter GRAY, there's a cycle. We add nodes to result after processing all neighbors (post-order), then reverse for topological order.

Time Complexity: O(V + E)

Space Complexity: O(V + E)

Problem 4: Number of Islands (LeetCode #200)

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands.

Solution:

def numIslands(grid):
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return
        
        grid[i][j] = '0'  # Mark as visited
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

Explanation: We iterate through the grid. When we find land ('1'), we increment count and use DFS to mark all connected land as visited ('0'). This ensures each island is counted only once.

Time Complexity: O(m × n)

Space Complexity: O(m × n) for recursion stack

Problem 5: Binary Tree Maximum Path Sum (LeetCode #124)

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. Return the maximum path sum.

Solution:

def maxPathSum(root):
    max_sum = float('-inf')
    
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        
        left_sum = max(0, dfs(node.left))
        right_sum = max(0, dfs(node.right))
        
        current_path = node.val + left_sum + right_sum
        max_sum = max(max_sum, current_path)
        
        return node.val + max(left_sum, right_sum)
    
    dfs(root)
    return max_sum

Explanation: For each node, we calculate the maximum path sum that goes through it. We can either include both children (current_path) or extend upward with the better child. We use max(0, ...) to ignore negative contributions.

Time Complexity: O(n)

Space Complexity: O(h)