Depth-First Search

Use Cases

Code Template

Most LeetCode tree solutions nest a def dfs(node): ... inside the outer method. Three patterns cover most problems:

Graphs / grids: same recursion idea, but add visited (set, or mutate the cell) before expanding neighbors — see 200. Number of Islands in Related Problem.

Pattern 1 — Top-down (preorder list or state such as path sum)

dfs runs before children see aggregated subtree answers. Use a shared result list, nonlocal count, or extra parameters (acc, depth, target).

def dfs(node, result):
    if not node:
        return

Same traversal shell with parameters (e.g. 112. Path Sum): pass acc down instead of only using a list.

def dfs(node, acc: int) -> bool:
    if not node:
        return False
    acc += node.val
    if not node.left and not node.right:
        return acc == target
    return dfs(node.left, acc) or dfs(node.right, acc)

Pattern 2 — Bottom-up (return value from children / post-order)

Use this when the answer is computed from children up (height, diameter, subtree validity, tree DP, etc.).

def dfs(node):
    if not node:
        return 0  # example: height of empty tree

Pattern 3 — Backtracking (all root-to-leaf paths)

Push before children, list(path) when you store, and pop after recursion so the shared path stays correct for siblings.

def dfs(node, path):
    if not node:
        return

One-line mental checklist

1. Base case first (None, out of bounds, or already visited on graphs/grids).
2. Top-down: process / update state, then recurse; bottom-up: recurse first, then combine; backtracking: choose, recurse, undo.
3. Binary tree: for child in (node.left, node.right) when both use the same logic.
4. Use self.ans, a closure list, or nonlocal when you need both a return value and a global best.

Common mistakes

1. Wrong Base Case

# Wrong: missing base case
def dfs(root, result):
    result.append(root.val)  # Will fail on None
# Wrong: wrong return value
def dfs(root, result):
    if not root:
        return result  # Should return None
# Correct:
if not root:
    return

Issues and consideration

• BFS VS DFS: BFS is ideal when you need the shortest path in an unweighted graph or a level-by-level view. DFS fits deep paths, exhaustive choices, and many tree recurrences.
• Cycles: on general graphs, mark visited (or use grid bounds + a “blocked” cell) before recursing into neighbors.

Related Problem

110. Balanced Binary Tree

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Pattern 2 — bottom-up: children return height; parent combines
        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1

            return max(left, right) + 1
    
        return dfs(root) != -1

543. Diameter of Binary Tree

Longest path between any two nodes passes through some “highest” node; at each node, depth-first search returns subtree height while updating the best diameter with left depth + right depth — Pattern 2 (bottom-up).

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # Pattern 2 — bottom-up: return height; diameter through this node = left + right
        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)
            self.diameter = max(self.diameter, left + right)
            return max(left, right) + 1

        self.diameter = 0
        dfs(root)
        return self.diameter

144. Binary Tree Preorder Traversal

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # Pattern 1 — top-down: process node, then recurse on children
        def dfs(node, result):
            if not node:
                return
            result.append(node.val)
            for child in (node.left, node.right):
                dfs(child, result)

        result = []
        dfs(root, result)
        return result

112. Path Sum

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        # Pattern 1 — top-down: same shell, pass running sum as a parameter
        def dfs(node, acc):
            if not node:
                return False
            acc += node.val
            if not node.left and not node.right:
                return acc == targetSum
            for child in (node.left, node.right):
                if dfs(child, acc):
                    return True
            return False

        return dfs(root, 0)

200. Number of Islands

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # Pattern 1 — top-down on a grid: base case (out of bounds / water / seen), then recurse to neighbors
        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '#'
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                dfs(nr, nc)

        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1
        return count