Minimal, copy-paste C++ 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(self, graph, node, visited):
    visited[node] = True
    # Process node
    cout << node << " "
    # Explore neighbors
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)
# DFS with return value
def dfs(self, graph, node, target, visited):
    if (node == target) return True
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor] * and  dfs(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)
def dfsGrid(self, grid, i, j):
    m = len(grid), n = grid[0].__len__()
    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
    # Explore 4 directions
    dfsGrid(grid, i + 1, j)
    dfsGrid(grid, i - 1, j)
    dfsGrid(grid, i, j + 1)
    dfsGrid(grid, i, j - 1)
# Number of Islands using DFS
def numIslands(self, grid):
    m = len(grid), n = grid[0].__len__()
    count = 0
    for (i = 0 i < m i += 1) :
    for (j = 0 j < n j += 1) :
    if grid[i][j] == '1':
        count += 1
        dfsGrid(grid, i, j)
return count
# Word Search
def dfsWordSearch(self, board, i, j, word, idx):
    if (idx == len(word)) return True
    if (i < 0  or  i >= len(board)  or  j < 0  or  j >= board[0].__len__()) return False
    if (board[i][j] != word[idx]) return False
    char temp = board[i][j]
    board[i][j] = '#' # Mark as visited
    list[pair<int, int>> dirs = \:\:0,1\, \:0,-1\, \:1,0\, \:-1,0\\
for ([dx, dy] : dirs) :
if dfsWordSearch(board, i + dx, j + dy, word, idx + 1):
    return True
board[i][j] = temp # Backtrack
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).

# Preorder DFS
def preorder(self, root, result):
    if (not root) return
    result.append(root.val)
    preorder(root.left, result)
    preorder(root.right, result)
# Inorder DFS
def inorder(self, root, result):
    if (not root) return
    inorder(root.left, result)
    result.append(root.val)
    inorder(root.right, result)
# Postorder DFS
def postorder(self, root, result):
    if (not root) return
    postorder(root.left, result)
    postorder(root.right, result)
    result.append(root.val)
# Path Sum
def hasPathSum(self, root, targetSum):
    if (not root) return False
    if not root.left  and  not root.right:
        return root.val == targetSum
    return hasPathSum(root.left, targetSum - root.val)  or
    hasPathSum(root.right, targetSum - root.val)
# Sum Root to Leaf Numbers
def sumNumbers(self, root, 0):
    if (not root) return 0
    sum = sum  10 + root.val
    if (not root.left  and  not root.right) return sum
    return sumNumbers(root.left, sum) + sumNumbers(root.right, sum)
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.

# DFS with memoization (e.g., Longest Increasing Path)
dfsWithMemo(list[list[int>> matrix, i, j,
list[list[int>> memo, prev) :
m = len(matrix), n = matrix[0].__len__()
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]
result = 1
list[pair<int, int>> dirs = \:\:0,1\, \:0,-1\, \:1,0\, \:-1,0\\
for ([dx, dy] : dirs) :
result = max(result, 1 + dfsWithMemo(matrix, i + dx, j + dy,
memo, matrix[i][j]))
memo[i][j] = result
return result
ID Title Link Solution
329 Longest Increasing Path in a Matrix Link -

Iterative DFS

DFS using stack instead of recursion.

# Iterative DFS on graph
def dfsIterative(self, graph, start):
    list[int> st
    list[bool> visited(len(graph), False)
    st.push(start)
    while not not st:
        node = st.top()
        st.pop()
        if (visited[node]) continue
        visited[node] = True
        # Process node
        cout << node << " "
        # Push neighbors in reverse order to maintain order
        for (i = graph[node].__len__() - 1 i >= 0 i -= 1) :
        if not visited[graph[node][i]]:
            st.push(graph[node][i])
# Iterative DFS on tree
def preorderIterative(self, root):
    list[int> result
    if (not root) return result
    list[TreeNode> st
    st.push(root)
    while not not st:
        TreeNode node = st.top()
        st.pop()
        result.append(node.val)
        if node.right) st.push(node.right:
        if node.left) st.push(node.left:
    return result
ID Title Link Solution
144 Binary Tree Preorder Traversal Link -
94 Binary Tree Inorder Traversal Link -

More templates