Recursive DFS is elegant. Each function call pushes a frame onto the call stack, and each return pops one off. The language runtime handles the bookkeeping. You just write dfs(neighbor) and trust the machine.

But that trust has a limit -- literally. The call stack is a fixed-size block of memory, typically between 1MB and 8MB depending on your runtime. Every recursive call consumes stack space for local variables, the return address, and function arguments. On a graph with 10,000 nodes in a straight chain, recursive DFS pushes 10,000 frames. On a graph with 100,000 nodes? Stack overflow.

Keep tapping and watch the frames pile up. Notice the moment the stack overflows -- it does not degrade gracefully. There is no warning, no partial result. The program simply crashes.

The fix: stop relying on the language's call stack. Allocate your own stack on the heap, where memory is practically unlimited. Same LIFO behavior, same DFS semantics, but you control the ceiling. This is iterative DFS, and once you understand the one trap it sets, you will reach for it whenever graph depth is unpredictable.

How deep can you go before the stack overflows? It depends on the runtime. Python defaults to a recursion limit of 1,000. Java's default thread stack is 512KB to 1MB, supporting roughly 5,000-20,000 frames depending on frame size. JavaScript in V8 can handle about 10,000-15,000 frames.

These numbers feel large until you encounter real-world graphs. A social network traversal. A file system walk. A grid DFS on a 500x500 matrix (which can produce paths of 250,000 cells). Suddenly “15,000 frames” is not enough.

Slide to increase graph depth and watch which runtimes survive -- and which crash. Notice that the iterative version, using a heap-allocated array as its stack, does not have this problem. It is limited only by available heap memory, which is typically gigabytes.

The translation from recursive to iterative DFS is mechanical. Replace the function call with a push to your stack array. Replace the function return with a pop. Replace local state (which lived in stack frames) with data stored alongside each node on your explicit stack.

The structure looks like BFS with one swap: instead of a queue (FIFO -- first in, first out), you use a stack (LIFO -- last in, first out). That single change -- popping from the same end you push to -- is what makes the traversal depth-first instead of breadth-first. The most recently discovered node gets explored next, exactly like a recursive call.

Tap Step to advance through the algorithm. Watch the explicit stack on the right grow as nodes are pushed and shrink as they are popped. This is exactly what the call stack does behind the scenes in recursive DFS -- you have just made it visible and controllable.

function dfs(graph, start) {

  const visited = new Set()

  const stack = [start]

  while (stack.length > 0) {

    const node = stack.pop()

    if (visited.has(node)) continue

    visited.add(node)

    for (child of reversed(graph[node]))

      if (!visited.has(child))

        stack.push(child)

  }

}

Here is the trap that catches nearly everyone who writes iterative DFS for the first time.

Recursive DFS visits children in the order you iterate them. If you loop through neighbors left-to-right, the leftmost child is visited first -- because that recursive call happens immediately, before the loop continues to the next neighbor.

Now consider the iterative version. You pop a node, then push its children left-to-right: push A, push B, push C. The stack now has C on top. You pop C next. But recursive DFS would have visited A first, not C.

The stack is LIFO: the last child you push is the first one you pop. If you push children in the same left-to-right order you would iterate them recursively, the visit order gets reversed. This does not affect correctness for most problems (connected components, cycle detection), but it breaks any problem where traversal order matters -- like topological sort or pre-order serialization.

Step through both versions simultaneously and watch the visit orders diverge.

The fix is a one-line change, but the reasoning behind it is what matters.

You want the leftmost child to be popped first. LIFO means the last item pushed is popped first. So the leftmost child must be pushed last. That means you push children in reverse order: right-to-left. This is a direct consequence of the stack's LIFO discipline, and once you see the logic, it becomes impossible to forget.

A concrete example: if a node has children [A, B, C], push C first, then B, then A. Now A sits on top of the stack. Pop A next -- it matches what recursive DFS would do. The stack now has B on top, and C beneath it. Pop B, then C. The visit order is A, B, C -- exactly what the recursive version produces.

This feels backward, and that is exactly why it trips people up. The mental model: “I want to visit left-first, so I push left-last.” Inverse of intuition, but mechanical once you see it. The same pattern appears any time you translate a natural order into a LIFO structure -- reversing the input restores the intended output order.

Watch the fix in action below. Compare the visit order with the child-ordering trap you saw on the previous screen and verify that the reversal produces the correct sequence.

This iterative DFS compiles and runs without errors. It visits every node. It even terminates correctly. But the visit order is wrong -- it does not match the recursive DFS that it is supposed to replicate.

The tricky thing about order bugs in iterative DFS is that they produce output that looks correct at a glance. Every node appears in the result. The traversal is depth-first -- it dives deep before backtracking. If the problem only cares about which nodes were visited (connected components, flood fill), the wrong order does not matter and the bug is invisible. The bug only surfaces when traversal order matters: pre-order serialization, topological sort, or any problem where the sequence of visits affects the result. This makes it a particularly insidious class of bug -- it passes some problems and fails others, and the failing cases are not always obvious.

The bug is the child-ordering trap in disguise. Somewhere in this code, children are being pushed in the wrong order, causing the LIFO reversal you just learned about. The output looks plausible, so you would not catch this by “does it crash?” testing. You have to reason about the stack's LIFO behavior and mentally trace which node ends up on top after each batch of pushes.

Find the buggy line, then pick the correct fix.

You have seen the stack overflow, the LIFO reversal, and the one-line fix. Now construct iterative DFS from scratch.

The conversion from recursive to iterative is a skill that separates junior from senior graph implementations. Recursive DFS is elegant and easy to write, but it breaks on deep graphs -- and in production, you rarely control the graph's depth. A social network with a long chain of connections, a file system with deeply nested directories, a grid DFS on a 1000x1000 matrix: all of these can produce recursion depths that exceed the call stack limit. The iterative version handles all of them without risk, because the explicit stack lives on the heap where memory is measured in gigabytes, not megabytes.

The mental model that makes this construction straightforward: every recursive call becomes a push, every return becomes a pop, and every local variable that lived in a stack frame now lives alongside the node data on your explicit stack. The LIFO behavior of your array-based stack ensures depth-first ordering, just like the LIFO behavior of the call stack did. Same semantics, different mechanism.

Four blanks, four key decisions. The first asks what data structure holds your frontier (stack, not queue). The second asks when to stop (stack empty). The third asks how to retrieve the next node (pop, not dequeue). The fourth -- the trap -- asks which order to push children so the visit order matches recursive DFS. That last blank is where the LIFO reversal hides, and it is the one most people get wrong on the first try.

Three questions that test the mental models, not just the mechanics.

The iterative DFS pattern has an interesting property that makes it worth understanding deeply rather than just memorizing: it reveals the hidden assumptions in recursive code. When you write dfs(neighbor) in a loop, the language runtime is making LIFO decisions for you -- the first recursive call executes immediately, suspending the loop, and later calls wait on the implicit stack. You never see this happening. The iterative version forces you to make those same decisions explicitly, which means you understand why the visit order is what it is, not just what it is.

This understanding pays dividends beyond DFS itself. BFS is the same template with a queue instead of a stack. Dijkstra is the same template with a priority queue. A* is Dijkstra with a heuristic-adjusted priority. The explicit-stack DFS you just built is the foundation of a family of algorithms that differ only in their frontier discipline -- and once you see that shared skeleton, converting between them is mechanical.

You will need to reason about when iterative DFS is necessary (stack depth), what causes the LIFO reversal (push order), and what happens if you forget to reverse -- specifically, which real problems break and which silently produce wrong answers. The child-ordering trap is one of those bugs that interviews love because it tests whether you truly understand LIFO behavior or just memorized the template.