DFS

DFS (Depth-First Search)

Use when: Explore all paths, detect cycles, connected components, tree traversals.

Complexity: O(V + E)

Recursive DFS (Graph)

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
 
visited = set()
dfs(graph, start, visited)

Iterative DFS (Graph)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

DFS - Grid

def dfs_grid(grid, r, c, visited):
    rows, cols = len(grid), len(grid[0])
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    if (r, c) in visited:
        return
    visited.add((r, c))
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        dfs_grid(grid, r + dr, c + dc, visited)

DFS - All Paths (with backtracking)

def dfs_paths(graph, node, target, path, result):
    if node == target:
        result.append(list(path))
        return
    for neighbor in graph[node]:
        path.append(neighbor)
        dfs_paths(graph, neighbor, target, path, result)
        path.pop()  # backtrack
 
result = []
dfs_paths(graph, start, target, [start], result)

Tree Traversals

def inorder(root):   # left → root → right
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []
 
def preorder(root):  # root → left → right
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []
 
def postorder(root): # left → right → root
    return postorder(root.left) + postorder(root.right) + [root.val] if root else []

Signals in a Problem

• “All paths” / “all possibilities”
• Connected components
• Cycle detection
• Tree path problems