Iterative DFS and recursion elimination

When you implement depth-first search as a recursive function, Python limits how deep the call stack can grow. On a tree or graph with 100,000 nodes, a recursive DFS may hit this limit and crash. Iterative DFS uses an explicit stack to handle the traversal without relying on the call stack.

Recursive DFS is elegant but fragile at scale. You write a function that calls itself on each unvisited neighbor. For a deep tree, each function call consumes stack space. Python's default recursion limit is around 1,000 calls, and increasing it with sys.setrecursionlimit() only delays the problem.

An iterative DFS performs the same traversal using a list as your own stack. You push and pop nodes, process them, and maintain full control over how many nodes are on the stack at once. This avoids the recursion limit entirely.

The basic iterative stack

The simplest iterative DFS maintains a stack of nodes to visit. Start by pushing the root. While the stack is not empty, pop a node, process it, and push all its unvisited neighbors.

1def iterative_dfs(adj, root):2    """Iterative DFS starting from root."""3    visited = set()4    stack = [root]5    order = []6
7    while stack:8        node = stack.pop()9        if node in visited:10            continue11        visited.add(node)12        order.append(node)13
14        for neighbor in reversed(adj[node]):15            if neighbor not in visited:16                stack.append(neighbor)17
18    return order19
20
21adj = {22    0: [1, 2],23    1: [3, 4],24    2: [5],25    3: [],26    4: [],27    5: []28}29
30result = iterative_dfs(adj, 0)31print("DFS order:", result)

DFS order: [0, 1, 3, 4, 2, 5]

This visits nodes in a DFS order and marks them as visited. The stack grows and shrinks as you explore branches. A deep tree no longer crashes because you control the stack size, not Python's function call stack.

One subtle point: when pushing neighbors, reverse the order. If the adjacency list is [a, b, c], push them as c, b, a so that a is popped first. This maintains the same left-to-right traversal order as the recursive version. Without reversing, you visit neighbors in reverse order, which can confuse when you are debugging tree properties.

Preorder and postorder processing

Recursive DFS naturally supports both preorder (process a node before its children) and postorder (process a node after its children) traversals. Iterative DFS can do both, but you must track state carefully.

For preorder, process the node when you first pop it from the stack, then push its children. For postorder, push a node twice: once with a marker to say "process this later", and once to push its children. When you pop the marker, process the node.

1def iterative_postorder_dfs(adj, root):2    """Iterative postorder DFS using a marker technique."""3    visited = set()4    stack = [root]5    order = []6    MARKER = None7
8    while stack:9        node = stack[-1]10        if node is MARKER or node in visited:11            stack.pop()12            if node is not MARKER:13                order.append(node)14            continue15
16        visited.add(node)17        stack.append(MARKER)18        for neighbor in reversed(adj[node]):19            if neighbor not in visited:20                stack.append(neighbor)21
22    return order23
24
25adj = {26    0: [1, 2],27    1: [3, 4],28    2: [5],29    3: [],30    4: [],31    5: []32}33
34result = iterative_postorder_dfs(adj, 0)35print("Postorder DFS:", result)

Postorder DFS: [3, 4, 1, 5, 2, 0]

Postorder is essential for tree DP problems where you need child results before computing the parent's value.

Consider a tree where each node has a weight, and you want the maximum weight found anywhere in each subtree. In postorder, you visit all of a node's children first, collect their subtree maximums, then combine those with the node's own weight. Preorder cannot do this: the parent is processed before its children are known. The marker technique guarantees a node's children finish before the node itself does, so the value it needs is always ready.

True DFS order with iterator indices

A more sophisticated technique maintains iterator indices for each node. When a node is pushed onto the stack, an index tracks which neighbor you are about to visit next. This lets you resume from the exact point you left off, matching the behavior of a recursive DFS precisely.

1def iterative_dfs_true_order(adj, root):2    """Iterative DFS with iterator indices for true DFS order."""3    visited = set()4    stack = [(root, 0)]5    order = []6
7    while stack:8        node, idx = stack[-1]9        if node in visited and idx == 0:10            stack.pop()11            continue12        if idx == 0:13            visited.add(node)14            order.append(node)15
16        if idx < len(adj[node]):17            neighbor = adj[node][idx]18            stack[-1] = (node, idx + 1)19            if neighbor not in visited:20                stack.append((neighbor, 0))21        else:22            stack.pop()23
24    return order25
26
27adj = {28    0: [1, 2],29    1: [3, 4],30    2: [5],31    3: [],32    4: [],33    5: []34}35
36result = iterative_dfs_true_order(adj, 0)37print("DFS with iterator order:", result)

DFS with iterator order: [0, 1, 3, 4, 2, 5]

This approach is crucial when the DFS tree itself is the output and you need to know parent-child relationships. Each node is pushed once, and its index advances as you explore its neighbors. Backtracking happens naturally when the index reaches the end of the neighbor list.

Iterative DFS on very deep graphs

PyPy stopped a single-branch recursive fill after about 1,400 calls in an earlier module. A tree or graph with 100,000 nodes can easily produce a path that long, and a recursive DFS rooted at one end of it crashes with a RecursionError well before it finishes. An explicit stack has no such limit: it lives on the heap, not the call stack, and grows only as large as your program lets it.

A rooted tree with a chain of depth 10,000 cannot be traversed recursively on PyPy without raising the recursion limit and hoping the underlying call stack has room to match. The two-pass approach, or the marker technique, visits every node in the right order without touching sys.setrecursionlimit() at all.

Why iterator indices matter

The iterator-index technique is harder to understand but essential for problems where the DFS tree structure itself is the answer. For example, some problems ask "how many nodes are in the subtree rooted at X?" or "what is the first ancestor of X with property Y?". To answer these, you need to know which edges are tree edges and which are back edges. Tree edges come from the DFS traversal itself. Back edges are shortcuts within the graph that do not belong to the DFS tree.

When you maintain an iterator index for each node, you process each edge exactly once. The first time you reach a neighbor, you explore it. If you return to that neighbor later via a back edge, the index is beyond it, so you skip it. This guarantees a proper DFS tree with no edge counted twice.

Cost and performance

Iterative DFS runs in $O(V + E)$ time and $O(V)$ space, the same as recursive DFS. The stack holds at most as many entries as the tree is deep. The trade-off is code complexity: basic iterative DFS is simple, postorder with markers is trickier, and iterator indices take the most care to get right. Choose the simplest variant that solves your problem.

On PyPy, iterative DFS is often faster than recursive DFS despite greater code complexity. There is no function-call overhead, and list operations are highly optimized. On CPython, the difference is smaller but still measurable. For the largest competitive programming test cases, iterative DFS is the only option.

Recap

Iterative DFS replaces recursion with an explicit stack, avoiding depth limits. Preorder processes nodes as they are popped; postorder uses a marker to defer processing. Iterator indices track which neighbor is next, preserving true DFS order. This approach scales to graphs with hundreds of thousands of nodes and is a foundational template for competitive programming.