Iterative vs Recursive DFS: Trade-offs for Trees and Graphs

You should write recursive DFS for almost every tree problem because it is cleaner and less prone to bugs. Switch to an iterative approach with an explicit Stack only when you face a graph with a depth exceeding the system recursion limit, which typically happens around 10,000 nodes in many environments.

The Case for Recursion

Recursion maps directly to the structure of a tree. When you write dfs(node.left) and dfs(node.right), you are letting the call stack manage the state for you. This is the standard way to solve problems like Binary Tree Maximum Path Sum or Lowest Common Ancestor. The code is short, readable, and easy to debug during a whiteboard interview. If you use an explicit stack, you have to manually push and pop nodes, which increases the chance of a simple logic error, like forgetting to mark a node as visited or pushing the same child twice.

When Iteration Becomes Necessary

Graphs are different from trees. A graph can have a cycle or a very long, thin path that forces the recursion depth to exceed the memory allocated for the stack. If you are solving a problem like Course Schedule or finding the Connected Components in a massive graph with 100,000 nodes, a recursive solution will trigger a StackOverflowError.

In these cases, you must use an explicit Stack data structure on the heap. The heap is much larger than the thread stack. You are essentially moving the memory burden from the language runtime to your own data structure. This is the only time an interviewer expects you to demonstrate the iterative version.

A Worked Example

Consider a simple linked list acting as a graph: 1 -> 2 -> 3 -> 4.

Recursive DFS:

1. Call dfs(1)
2. Call dfs(2)
3. Call dfs(3)
4. Call dfs(4)
5. Base case reached, return.

The stack holds four frames. If the list had 20,000 nodes, the program crashes.

Iterative DFS:

1. Create Stack s. Push 1.
2. Pop 1, push 2.
3. Pop 2, push 3.
4. Pop 3, push 4.
5. Pop 4, stack empty.

The stack only ever holds one node at a time. The memory usage is constant regardless of the depth.

Preserving Visit Order

One subtle trap is that the order of visiting neighbors differs between recursion and iteration. In a recursive function, you process children in the order they appear in your adjacency list. In an iterative approach, if you push neighbors onto a stack, the last one pushed is the first one popped. If you need to visit neighbors in the exact order of the adjacency list, you must push them onto the stack in reverse order. This is a common point of failure in problems like Lexicographical Smallest Path.

The Rule of Thumb

• Use recursion for trees: it is faster to write and easier to read.
• Use an explicit stack for graphs: it prevents crashes on deep paths.
• If the problem involves a grid or a tree, recursion is almost always the intended solution.
• If the problem involves a large graph or a deep chain, use an iterative approach to stay safe.

You can practice these patterns on DSA Tracker by filtering for graph problems and attempting both implementations for the same input. Start by converting your next recursive tree traversal into an iterative one to see how the state management changes.

Keep going with practice problems and the online compiler.

Further reading: Linked lists on Wikipedia.