BFS vs DFS — When to Use Which Traversal, with Three Walkthroughs

BFS and DFS are the same algorithm with different queues — literally. Swap deque.popleft() for list.pop() and you've traded one for the other. The interesting question isn't "how do I write DFS?" It's "which visit order preserves the invariant I need?" That's a decision, not a template — and it's the last recognition step in the pattern-recognition series before graph-specific work (topological sort, union-find, shortest paths) begins.

Recognition — when either technique is the tool

Graph traversal is the right tool when any of these hold:

1. You're exploring a graph or tree, visiting nodes to compute a property (component sizes, reachability, distances, structural clones).
2. The problem restates as "for every node, do X" — count something per node, mark it, or use it to build a bigger answer.
3. You need to enumerate all reachable states from a start (game trees, state-space search).

If the problem passes the graph-traversal recognition step, the only remaining question is the visit order. That's what the rest of this post is about.

Mental model — same algorithm, different data structure

Both BFS and DFS execute the same loop shape:

mark start as visited
push start onto a container
while container is not empty:
    pop a node
    for each unvisited neighbour:
        mark visited
        push onto container

The difference is one line: what's the container?

• BFS: a FIFO queue. Pop the earliest node still pending. Nodes are visited in order of distance from the start — depth 0, then all of depth 1, then all of depth 2. The queue at any moment contains at most two consecutive depths' worth of nodes.
• DFS: a LIFO stack. Pop the most recent node pushed. The algorithm dives to the deepest reachable node before backtracking. The stack at any moment is a path from the start to the current node (for iterative DFS; recursive DFS uses the call stack, which is the same thing in different clothes).

Both visit every reachable node exactly once, both are O(V + E) time, both are O(V) space in the worst case. Asymptotically they're identical — the reason to pick one over the other is which invariant they preserve as they run.

• BFS invariant. At any point, the queue contains nodes at depth d or d + 1 (never mixed further). This is what makes BFS the shortest-path algorithm in unweighted graphs.
• DFS invariant. At any point, the recursion stack is a path from the start to the current node. This is what makes DFS the natural tool for cycle detection, topological sort, and any "carry state along the path" problem.

The two templates

BFS — iterative with a deque

from collections import deque

def bfs(start, neighbours):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        # ... process node here ...
        for nxt in neighbours(node):
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)

Use collections.deque, not a Python list — list.pop(0) is O(n) (see the language-gotchas section of the Big-O cheat sheet); a deque's popleft() is O(1).

DFS — iterative or recursive

Recursive is shorter to write but stack-depth-limited. Iterative uses an explicit stack and can handle graphs that would blow Python's default recursion limit of 1000.

# Recursive
def dfs(node, visited, neighbours):
    if node in visited:
        return
    visited.add(node)
    # ... process node here ...
    for nxt in neighbours(node):
        dfs(nxt, visited, neighbours)

# Iterative
def dfs_iter(start, neighbours):
    visited = {start}
    stack = [start]
    while stack:
        node = stack.pop()
        # ... process node here ...
        for nxt in neighbours(node):
            if nxt not in visited:
                visited.add(nxt)
                stack.append(nxt)

Two subtle points about the iterative version:

• Mark visited when you push, not when you pop. Marking on pop (as some tutorials teach) can push the same neighbour multiple times before any of them are processed — you'll still visit each node once effectively, but the stack bloats.
• Iterative DFS visits in reverse-of-push order. If neighbour order matters (e.g., "leftmost path first" for a tree), reverse the neighbour list before pushing. Recursive DFS doesn't have this problem because the recursion order matches the neighbour-list order.

The decision — which one, and why

The choice is driven by the invariant you need, not by preference. This table is the whole art of the post:

Two failure modes worth naming so you can spot them in your own drafts:

• Reaching for BFS on a weighted graph and calling it "shortest path". BFS assumes every edge costs 1. On weighted graphs, the answer is Dijkstra (positive weights) or Bellman-Ford (negative weights allowed).
• Reaching for recursive DFS on a graph with >10⁴ nodes. Python's default recursion limit is 1000; deep chains stack-overflow. Switch to iterative DFS or sys.setrecursionlimit(10**6) — but the iterative form is the safer habit.

Walkthrough 1 — LeetCode 102, Binary Tree Level Order Traversal

Given the root of a binary tree, return its node values level by level.

Recognition. "Level by level" is the giveaway. BFS.

Trick. Snapshot the queue length at the top of each outer iteration. That length is exactly the number of nodes on the current level; drain that many nodes, then move on.

from collections import deque

def levelOrder(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

Trace the tree [3, 9, 20, null, null, 15, 7]:

Result: [[3], [9, 20], [15, 7]]. Without the for _ in range(level_size) snapshot, you'd get a flat pre-order traversal — the snapshot is what buys you the level grouping.

Walkthrough 2 — LeetCode 200, Number of Islands

Given an m × n grid of '1' (land) and '0' (water), return the number of islands. An island is a maximally connected group of '1' cells (four-directional).

Recognition. Count connected components. Either BFS or DFS. On a grid where the longest snake could reach m × n, recursive DFS in Python risks a stack overflow; either iterative DFS or BFS is the safer choice for competitive inputs. For LeetCode's default constraints, recursive DFS is fine and shorter.

Approach. Iterate every cell. When you hit a '1', launch a traversal, mark every reachable land cell as visited (overwrite with '0' — the input is already a mutable char grid), and increment the island counter.

def numIslands(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited in place
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1

    return count

Trace the grid

1 1 0
1 0 0
0 0 1

• Scan hits (0, 0) = '1' → DFS marks (0, 0), (0, 1), (1, 0) (all connected via up/down/left/right). count = 1.
• Continue scanning — (0, 1), (1, 0) already '0'.
• Scan reaches (2, 2) = '1' → DFS marks (2, 2) only (isolated). count = 2.

Result: 2. The "mark visited by overwriting the input" trick is the interview-classic space optimisation — no separate visited set, O(1) extra space beyond the recursion stack.

If you wanted BFS instead, swap the dfs function for the BFS template above; the outer loop stays identical. Same O(m × n) time and space, different failure modes on adversarial inputs.

Walkthrough 3 — LeetCode 133, Clone Graph

Given a reference to a node in a connected, undirected graph, return a deep copy of the graph.

Recognition. Graph traversal ✓. Need to carry state (a mapping from original nodes to their clones) across the traversal. That "carry state along the recursion" affinity is DFS's home turf.

Approach. Recursive DFS with a memo dictionary. When we visit an original node, either we've already cloned it (return the clone from the memo) or we clone it, memoise, and recurse on its neighbours.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def cloneGraph(node):
    if not node:
        return None

    old_to_new = {}

    def dfs(orig):
        if orig in old_to_new:
            return old_to_new[orig]
        clone = Node(orig.val)
        old_to_new[orig] = clone  # memoise BEFORE recursing, to break cycles
        for neighbour in orig.neighbors:
            clone.neighbors.append(dfs(neighbour))
        return clone

    return dfs(node)

The load-bearing line is old_to_new[orig] = clone before the recursive calls. If you memoise after the recursion, a cycle in the graph loops forever — DFS revisits orig from a neighbour, sees no entry, creates a second clone, and the two clones diverge.

Could you do this with BFS instead? Yes: two-pass BFS — first pass creates all clones, second pass wires up the neighbours. It works, but the DFS version reads cleaner because the recursion naturally interleaves creation and wiring. This is the "recursion is the path" invariant paying off in code brevity.

Common bugs

• Marking visited on pop instead of push. Same neighbour gets pushed multiple times before any of them is popped; the container bloats even though the algorithm's still correct. Mark on push (or, equivalently, right before pushing).
• BFS with list.pop(0). O(n) per pop turns O(V + E) BFS into O(V² + V·E). Always use collections.deque for the BFS queue.
• Recursive DFS on adversarial inputs. A 10,000-node snake overflows Python's recursion limit. Convert to iterative or bump sys.setrecursionlimit — the iterative habit is safer.
• DFS for shortest-path in unweighted graphs. DFS finds a path, not the shortest. If the problem asks "fewest steps", you want BFS.
• Forgetting to mark the start as visited. In graphs with self-loops or immediate cycles, the start gets re-visited, and depending on the container the algorithm either loops or duplicates work.

When neither is the tool

Same recognition checklist, failure modes made explicit:

• Weighted-graph shortest path. BFS assumes unit weights. Use Dijkstra (non-negative weights) or Bellman-Ford (negative weights allowed).
• All-pairs shortest paths. Running BFS/Dijkstra from every node works but is O(V · (V + E) log V). Floyd-Warshall is O(V³) and often simpler code.
• Minimum spanning tree. Not really a traversal problem. Kruskal (with union-find) or Prim (with a heap).
• Dynamic connectivity under edge insertions. Union-Find with path compression + union by rank — nearly O(1) per operation. See the specialised-structures row of the Big-O cheat sheet.
• Enormous implicit state space with cost function. A* or IDA* — informed search that uses a heuristic to prune the frontier.

How the Algotrek tutor would prompt you here

When a learner opens a graph-traversal problem on Algotrek, the tutor doesn't reveal which template. It asks three questions, and only advances when each is answered in one sentence:

1. "What are you traversing, and what does 'visit' mean?" — Nodes of a graph? Cells of a grid? Board states of a game? Naming the state space is what turns an abstract problem into a concrete traversal.
2. "Which invariant do you need — path or layer?" — Path invariant (recursion stack is the path) points at DFS. Layer invariant (queue holds one or two levels) points at BFS. Naming this is the decision.
3. "Does your problem measure distance in edges?" — If yes and edges are unweighted, BFS gives shortest paths for free. If no, DFS is fine. If yes and edges are weighted, you're out of the BFS/DFS toolbox and into Dijkstra territory.

Answer all three and the template picks itself. Try the Binary Tree Level Order Traversal lesson on Algotrek to see the prompt-then-reveal flow on the friendliest BFS problem, the Number of Islands lesson for grid DFS, and the Clone Graph lesson for the "recursion carries state" affinity that separates a DFS solution from a template dump.

Where to go next

• LC 207, Course Schedule. Cycle detection in a directed graph. DFS with a three-colour marker (white / grey / black) — grey-to-grey is a cycle. The classic bridge into topological sort.
• LC 210, Course Schedule II. Same graph, return a valid topological order. Two clean solutions: BFS (Kahn's algorithm) or DFS post-order. Comparing them is the fastest way to see how each traversal's invariant maps to a real problem.
• LC 994, Rotting Oranges. Multi-source BFS — enqueue every rotten orange at the start, then BFS from all of them simultaneously. "The queue starts non-empty" is the recognition wrinkle; the rest is LC 102 in a grid.
• LC 127, Word Ladder. Unweighted shortest path on an implicit graph (words are nodes; edges connect words differing by one letter). BFS shines.
• LC 417, Pacific Atlantic Water Flow. Reverse-flow DFS from each ocean. A great study in "traverse from the answer, not toward it" as a problem-reframing move.

Cross-reference the sliding-window, two-pointer, binary-search, monotonic-stack, and backtracking posts. All five prior posts pruned by proving certain candidates or branches never mattered; BFS and DFS don't prune at all — they visit every reachable state — but they order the visit so that the property you care about (shortest path, level grouping, path-carried state) falls out of the visit order for free. That's a different kind of invariant, and it's the last one the pattern series covers before problem-specific graph algorithms (topological sort, Dijkstra, union-find) take over.

For the O(V + E) accounting that both templates cash in on — and the deque-vs-list gotcha that decides whether your BFS is actually O(V + E) or accidentally O(V²) — the Big-O cheat sheet is the reference.