Depth-First Search Pattern: Template + 366 LeetCode Problems

What the depth-first search pattern is

Depth-first search commits to one branch and follows it to exhaustion before backing up, which makes it the right traversal whenever the question is about a whole component rather than about distance. Recursion is the natural expression because the call stack already is the traversal stack, but the recursion depth equals the longest path — enough to blow Python's default limit on a large grid, which is when the explicit-stack form earns its keep. The bug that costs the most time is marking nodes seen at the wrong moment: mark on discovery, when the node is first pushed or first entered, never when it is popped, or a node reachable by two edges gets queued twice and the traversal degenerates. For cycle detection in a directed graph, a two-state seen set is not enough — you need three, because a node already finished is not the same thing as a node still on the current path, and only the second means a cycle.

When to use it

• —You need everything reachable from a node: a connected component, an island, an enclosed region.
• —The problem is about paths, subtree aggregates, or values computed from children.
• —You are detecting a cycle in a directed graph, or classifying edges.
• —The graph is deep and narrow rather than wide, so a queue would hold more than the stack does.

The depth-first search template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 366 problems listed below.

def dfs(graph, start):
    seen = {start}
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)     # mark on PUSH, not on pop
                stack.append(neighbour)

    return order

Complexity characteristics

Time

O(V + E)

Auxiliary space

O(V)

Every node is marked seen once and every edge is examined once from each endpoint, so the traversal is linear in the size of the graph — on an r × c grid that is O(r·c), with four edges per cell. The space is the seen set plus the stack, and the stack holds the longest path in the graph, which is why the recursive form overflows Python's default recursion limit on a large grid while the explicit-stack form does not.

All 366 depth-first search LeetCode problems

Every problem in the library the depth-first search pattern applies to, grouped by LeetCode's own difficulty rating. 272 of the 366 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Depth-First Search pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.