Minimal, copy-paste Python for graph DFS, grid DFS, tree DFS, memoization, and iterative DFS. See also Graph and Backtracking.

Contents

Basic DFS

Depth-First Search explores as far as possible before backtracking.

# DFS on graph (adjacency list)
def dfs_graph(graph: list[list[int]], node: int, visited: list[bool]) -> None:
    visited[node] = True
    # process node
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs_graph(graph, neighbor, visited)


def dfs_find_target(
    graph: list[list[int]], node: int, target: int, visited: list[bool]
) -> bool:
    if node == target:
        return True
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor] and dfs_find_target(graph, neighbor, target, visited):
            return True
    return False

DFS on Grid

DFS for 2D grid problems (connected components, paths).

# DFS on 2D grid (4-directional)
DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def dfs_grid(grid: list[list[str]], i: int, j: int) -> None:
    m, n = len(grid), len(grid[0])
    if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
        return
    grid[i][j] = "0"
    for di, dj in DIRS:
        dfs_grid(grid, i + di, j + dj)


def num_islands(grid: list[list[str]]) -> int:
    m, n = len(grid), len(grid[0])
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                count += 1
                dfs_grid(grid, i, j)
    return count


def dfs_word_search(board: list[list[str]], i: int, j: int, word: str, idx: int) -> bool:
    if idx == len(word):
        return True
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
        return False
    if board[i][j] != word[idx]:
        return False
    temp = board[i][j]
    board[i][j] = "#"
    for di, dj in DIRS:
        if dfs_word_search(board, i + di, j + dj, word, idx + 1):
            board[i][j] = temp
            return True
    board[i][j] = temp
    return False
ID Title Link Solution
200 Number of Islands Link Solution
79 Word Search Link Solution
695 Max Area of Island Link Solution
133 Clone Graph Link Solution
417 Pacific Atlantic Water Flow Link Solution
323 Number of Connected Components Link Solution
547 Number of Provinces Link Solution

DFS on Tree

DFS for tree problems (preorder, inorder, postorder).

class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def preorder(root: TreeNode | None, result: list[int]) -> None:
    if not root:
        return
    result.append(root.val)
    preorder(root.left, result)
    preorder(root.right, result)


def inorder(root: TreeNode | None, result: list[int]) -> None:
    if not root:
        return
    inorder(root.left, result)
    result.append(root.val)
    inorder(root.right, result)


def postorder(root: TreeNode | None, result: list[int]) -> None:
    if not root:
        return
    postorder(root.left, result)
    postorder(root.right, result)
    result.append(root.val)


def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target_sum
    return has_path_sum(root.left, target_sum - root.val) or has_path_sum(
        root.right, target_sum - root.val
    )


def sum_numbers(root: TreeNode | None, cur: int = 0) -> int:
    if not root:
        return 0
    cur = cur * 10 + root.val
    if not root.left and not root.right:
        return cur
    return sum_numbers(root.left, cur) + sum_numbers(root.right, cur)
ID Title Link Solution
100 Same Tree Link Solution
101 Symmetric Tree Link Solution
104 Maximum Depth of Binary Tree Link Solution
111 Minimum Depth of Binary Tree Link Solution
112 Path Sum Link Solution
129 Sum Root to Leaf Numbers Link Solution
226 Invert Binary Tree Link Solution
236 Lowest Common Ancestor Link Solution
437 Path Sum III Link Solution
690 Employee Importance Link Solution

DFS with Memoization

DFS with caching to avoid recomputation.

DIRS4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def dfs_with_memo(
    matrix: list[list[int]], i: int, j: int, memo: list[list[int]], prev: int
) -> int:
    m, n = len(matrix), len(matrix[0])
    if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] <= prev:
        return 0
    if memo[i][j] != -1:
        return memo[i][j]
    best = 1
    for di, dj in DIRS4:
        best = max(best, 1 + dfs_with_memo(matrix, i + di, j + dj, memo, matrix[i][j]))
    memo[i][j] = best
    return best
ID Title Link Solution
329 Longest Increasing Path in a Matrix Link Solution

Iterative DFS

DFS using stack instead of recursion.

class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def dfs_iterative(graph: list[list[int]], start: int) -> None:
    st: list[int] = [start]
    visited = [False] * len(graph)
    while st:
        node = st.pop()
        if visited[node]:
            continue
        visited[node] = True
        for nei in reversed(graph[node]):
            if not visited[nei]:
                st.append(nei)


def preorder_iterative(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    result: list[int] = []
    st: list[TreeNode] = [root]
    while st:
        node = st.pop()
        result.append(node.val)
        if node.right:
            st.append(node.right)
        if node.left:
            st.append(node.left)
    return result
ID Title Link Solution
144 Binary Tree Preorder Traversal Link -
94 Binary Tree Inorder Traversal Link -

More templates