GraphsLesson 5

DFS — Iterative

The same depth-first traversal but using an explicit stack instead of recursion. Why you'd want this and how it works step by step.

What Is It?

Iterative DFS does the same thing as recursive DFS, but instead of using function calls to go deeper, it uses an explicit stack — a data structure you manage yourself.

A stack works like a stack of plates: last in, first out. You push things onto the top. You pop from the top.

Here is the key insight: swap the queue in BFS for a stack, and you get DFS. That is it. One data structure change transforms breadth-first into depth-first.

Why use iterative DFS instead of recursive? Recursive DFS can crash on very deep graphs because the computer's function call system has a limited depth. An explicit stack does not have that limitation.

Analogy

Imagine a stack of sticky notes, each with a room number — rooms you still need to explore in a building.

You grab the top note, go to that room, and write new notes for each unexplored connecting room, putting them on top of the stack. You always grab the top note next. This means you keep going deeper into one part of the building before exploring others. That is depth-first.

If you used a line (queue) instead — taking from the front and adding to the back — you would explore rooms level by level. That is breadth-first.

How It Works

Same graph as the BFS and recursive DFS lessons:

pseudocode

    0 --- 1 --- 2
    |           |
    3 --- 4 --- 5

Adjacency List:

pseudocode

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

Iterative DFS Pseudocode

pseudocode

function DFS_iterative(graph, start):
    visited = empty set
    stack = empty stack
    stack.push(start)
    while stack is not empty:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        process(node)              // e.g., print it
        for each neighbor in graph[node]:
            if neighbor not in visited:
                stack.push(neighbor)

Notice: We check visited after popping, not before pushing. The same node can end up on the stack more than once (pushed by different neighbors). When we pop it and see it is already visited, we just skip it.

Step-by-Step Trace (starting from node 0)

pseudocode

Push 0
  Stack: [0]            Visited: {}
Pop 0. Not visited. Visit 0. Neighbors: 1, 3
  Push 1, push 3.
  Stack: [1, 3]         Visited: {0}
Pop 3. Not visited. Visit 3. Neighbors: 0, 4
  0 already visited. Push 4.
  Stack: [1, 4]         Visited: {0, 3}
Pop 4. Not visited. Visit 4. Neighbors: 3, 5
  3 already visited. Push 5.
  Stack: [1, 5]         Visited: {0, 3, 4}
Pop 5. Not visited. Visit 5. Neighbors: 2, 4
  4 already visited. Push 2.
  Stack: [1, 2]         Visited: {0, 3, 4, 5}
Pop 2. Not visited. Visit 2. Neighbors: 1, 5
  Push 1. 5 already visited.
  Stack: [1, 1]         Visited: {0, 3, 4, 5, 2}
Pop 1. Not visited. Visit 1. Neighbors: 0, 2
  Both already visited.
  Stack: [1]            Visited: {0, 3, 4, 5, 2, 1}
Pop 1. Already visited. Skip.
  Stack: []             Visited: {0, 3, 4, 5, 2, 1}
Done! Processing order: 0, 3, 4, 5, 2, 1

Comparison of All Three Traversal Orders

BFS (Queue)

Order: 0, 1, 3, 2, 4, 5, 6, 7

Level by level, breadth first

FIFO — process neighbors before going deeper

DFS Recursive

Order: 0, 1, 2, 5, 4, 3, 6, 7

Follow first neighbor as deep as possible

implicit call stack

DFS Iterative

Order: 0, 3, 4, 6, 5, 7, 2, 1

LIFO stack reverses neighbor order

explicit stack — last pushed = first processed

Notice that recursive DFS and iterative DFS give different orders on the same graph. Recursive DFS processes the first neighbor in the adjacency list first. Iterative DFS pushes all neighbors then pops the last one first (LIFO), so it effectively goes through neighbors in reverse order.

To make iterative DFS match recursive DFS, push neighbors in reverse order:

pseudocode

for each neighbor in reversed(graph[node]):
    if neighbor not in visited:
        stack.push(neighbor)

BFS vs Iterative DFS — Side by Side

The code is almost identical. Only the data structure changes:

pseudocode

// BFS uses a queue             // DFS uses a stack
queue.enqueue(start)            stack.push(start)
while queue not empty:          while stack not empty:
    node = queue.dequeue()          node = stack.pop()
    // mark visited on enqueue      // mark visited on pop
    process(node)                   process(node)
    for neighbor in ...:            for neighbor in ...:
        queue.enqueue(neighbor)         stack.push(neighbor)

Queue = BFS. Stack = DFS. That is the fundamental insight.

Time: O(V + E) — same as recursive DFS and BFS.

Space: O(V) — the visited set plus the stack.

Examples

Iterative DFS with Path Tracking

pseudocode

function DFS_path(graph, start, target):
    visited = empty set
    stack = empty stack
    parent = empty hashmap
    stack.push(start)
    parent[start] = null
    while stack is not empty:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        if node == target:
            path = []
            current = target
            while current is not null:
                path.prepend(current)
                current = parent[current]
            return path
        for each neighbor in graph[node]:
            if neighbor not in visited:
                stack.push(neighbor)
                parent[neighbor] = node
    return null   // target not reachable

Unlike BFS, this does NOT guarantee the shortest path — just a path.

Common Mistakes

Thinking iterative DFS and recursive DFS always give the same order. They process neighbors in opposite order by default. Reverse the neighbor order when pushing if you need them to match.

Assuming DFS finds shortest paths. DFS finds a path, not the shortest one. Use BFS for shortest paths.

Forgetting that stack.pop() gives the LAST pushed item. If you push neighbors left to right, the rightmost neighbor is processed first.

Not handling disconnected graphs. Same as BFS and recursive DFS — you need an outer loop to visit all components.

Best Practices

Use iterative DFS for production code when input size is unpredictable. Stack overflows are hard to debug.
Remember the key insight: Queue = BFS, Stack = DFS. If you know one, you know the other.
Use recursive DFS in interviews unless stack overflow is a concern — it is shorter and cleaner to write.
Push neighbors in reverse order if you need iterative DFS to match recursive DFS behavior.

DFS — Recursive Understanding Recursion