BFS vs DFS: Differences, Templates and When to Use Each

BFS vs DFS comes down to visiting order: breadth-first search (BFS) uses a queue and explores nodes level by level, so it finds the shortest path in an unweighted graph, while depth-first search (DFS) uses a stack or recursion and follows one path as deep as it goes before backtracking, which suits exhaustive search, connectivity, cycle detection and backtracking. Both run in O(V + E) time; the practical difference is which answer each one finds first and how much memory it holds.

This guide gives you the comparison table, a decision checklist, tested Python templates for both, three worked LeetCode problems (1091, 79 and 133) and a practice list. Every code block was run in Python with asserts against a brute-force check before we published it. For the tree-specific orders (preorder, inorder, postorder, level order), see our tree traversal patterns guide.

BFS vs DFS: the differences at a glance

When to use BFS and when to use DFS

Use this checklist in order. The first rule that matches usually decides it.

1. "Minimum number of steps / moves / transformations" with equal-cost moves: BFS. Examples: shortest path in a grid, word ladder, open the lock.
2. Answer depends on the level (level averages, right side view, the time at which something spreads): BFS.
3. Several starting points spreading at once (rotting oranges, distance to the nearest 0): multi-source BFS, seeding the queue with every source.
4. "Find all paths / combinations / does any path exist that uses each cell once": DFS with backtracking, because you must undo choices; see the backtracking pattern.
5. Cycle detection or topological order in a directed graph: DFS with three colors, or Kahn's BFS for topological sort; see the topological sort pattern.
6. Just counting or labeling connected regions (number of islands, max area): either. DFS is usually shorter to write; BFS avoids recursion depth limits on big grids. Union-find is a third option.
7. Edges have different weights: neither. Use Dijkstra's algorithm (non-negative weights).

The BFS template in Python

Mark a node as visited when you add it to the queue, not when you take it out. Otherwise the same node can be queued many times, which wastes time and can blow up memory on dense graphs.

from collections import deque

def bfs(graph, start):
    # graph: {node: [neighbors]}; returns the fewest-edges distance to every reachable node
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()             # FIFO: oldest (closest) node first
        for nxt in graph.get(node, []):
            if nxt not in dist:            # mark when you ENQUEUE, not when you dequeue
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

Time O(V + E), space O(V) for the distance map and queue.

The DFS templates in Python

The recursive version is the fastest to write. The iterative version uses an explicit stack, so a long chain of nodes cannot hit the recursion limit.

def dfs(graph, start, seen=None):
    # recursive: the call stack remembers where to come back to
    if seen is None:
        seen = set()
    seen.add(start)
    for nxt in graph.get(start, []):
        if nxt not in seen:
            dfs(graph, nxt, seen)
    return seen

def dfs_iterative(graph, start):
    # explicit stack: same reachability, no recursion limit to worry about
    seen = {start}
    stack = [start]
    while stack:
        node = stack.pop()                 # LIFO: newest node first
        for nxt in graph.get(node, []):
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return seen

Both run in O(V + E) time. The recursive one uses O(depth) call-stack space; the iterative one uses O(V) for seen and the stack. Note that the iterative version visits neighbors in a different order from the recursive one. That does not matter for reachability, but it does for problems that need a true depth-first order, such as postorder or cycle detection with colors.

Worked problem 1 (BFS wins): Shortest Path in Binary Matrix

Shortest Path in Binary Matrix (LeetCode 1091): in an n by n grid of 0s (open) and 1s (blocked), find the length of the shortest clear path from the top-left to the bottom-right cell, moving in 8 directions. The length counts cells, not moves.

Why BFS: every move costs the same, and the question asks for the minimum. BFS reaches the target first along a shortest path, so you can return immediately. DFS would have to explore every path and compare.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    queue = deque([(0, 0, 1)])             # (row, col, cells on the path so far)
    grid[0][0] = 1                         # mark visited (mutates the input)
    while queue:
        r, c, length = queue.popleft()
        if (r, c) == (n - 1, n - 1):
            return length                  # first arrival = shortest path
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append((nr, nc, length + 1))
    return -1

Complexity: O(n²) time and space. Each cell is queued at most once, and it has at most 8 neighbors. Mention that the code marks visited cells by writing into the grid; if the interviewer does not want the input changed, use a seen set.

Worked problem 2 (DFS wins): Word Search

Word Search (LeetCode 79): return whether a word can be traced through horizontally or vertically adjacent letters on a board, using each cell at most once per path.

Why DFS: "each cell at most once" is a property of the current path, not of the whole search. DFS keeps exactly one path at a time, so you can mark a cell on the way in and unmark it on the way out (backtracking). A global BFS visited set would wrongly block cells that a different path needs.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False
        board[r][c] = '#'                  # mark as used on THIS path
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or
                 dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        board[r][c] = word[i]              # un-mark on the way back (backtrack)
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Complexity: O(R·C·3^L) time in the worst case for a word of length L (each step after the first has at most 3 new directions), and O(L) recursion depth. Pruning, such as checking that the board has enough of each letter first, helps in practice.

Worked problem 3 (either works): Clone Graph

Clone Graph (LeetCode 133): return a deep copy of a connected undirected graph given one node.

Either order works because you only need to visit every node once and copy every edge. The map from original node to copy doubles as the visited set. BFS is shown here; the recursive DFS version is the same idea with the queue replaced by a recursive call per unvisited neighbor.

from collections import deque

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}        # original -> copy, doubles as the visited set
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                queue.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

Complexity: O(V + E) time and O(V) space. Saying "either works, and here's why I picked BFS: no recursion limit" is a stronger answer than picking one silently.

Memory: the real BFS vs DFS trade-off

Both visit every node and edge once, so time rarely decides it. Memory often does:

• On a wide, shallow structure (a balanced binary tree, a social graph), BFS holds a whole level at once. The last level of a complete binary tree contains about half the nodes, so BFS can hold O(n) entries while DFS holds only O(log n).
• On a long, thin structure (a linked-list-shaped tree, a snake-like grid path), DFS depth reaches O(n), and recursive DFS in Python can raise RecursionError past the default limit of 1000 frames. Switch to iterative DFS or BFS.
• For a shortest path in a huge or infinite space (puzzle states), BFS finds a near goal without exploring deep useless branches; iterative deepening DFS is the memory-light alternative if the interviewer pushes on it.

Common bugs in BFS and DFS

• Using a Python list as a queue. list.pop(0) shifts every element; use deque.popleft().
• Marking visited on dequeue in BFS. Duplicates pile up in the queue.
• Using a global visited set in a backtracking DFS. Unmark on the way back, or paths that share cells are lost.
• Counting steps wrong in BFS. Either store the distance with each queued item or process the queue one full level at a time; mixing the two causes off-by-one errors.
• Forgetting disconnected parts. To cover every component, loop over all nodes and start a new search from each unvisited one.
• Grid bounds. Check 0 <= r < rows before reading the cell.

Practice list: 10 BFS and DFS problems

Problem numbers and difficulty labels were checked on LeetCode as of October 2026. Number of Islands, Course Schedule and Rotting Oranges are worked through in our graph algorithms guide, so they are not repeated here.

How to practice the BFS vs DFS decision

The decision is the part interviewers listen for, so practice saying it out loud before you write any code. CoPilot Interview's Mock Interview can mix coding questions into a session in your chosen language; it reads each question aloud, scores your spoken answer out of 10 with what to fix and a model answer, and coding questions never auto-submit. With nothing to install, the browser mock at /ai-mock-interview has 113 questions across 9 tracks, including coding. For a one-page review, use the free coding interview cheat sheet.

FAQ

What is the main difference between BFS and DFS?

BFS explores a graph level by level using a queue, so it reaches nodes in order of distance from the start. DFS follows one path as deep as possible using a stack or recursion, then backtracks. Both visit every node and edge once, in O(V + E) time.

Which is better for shortest path, BFS or DFS?

BFS, when every edge has the same cost. The first time BFS reaches a node, it has used the fewest edges. DFS does not guarantee that. If edges have different non-negative weights, use Dijkstra's algorithm instead of either.

Does BFS or DFS use more memory?

It depends on the shape. BFS stores the current frontier, which is large for wide graphs; the last level of a complete binary tree holds about half the nodes. DFS stores the current path, which is large for deep, thin graphs. Both can reach O(V) in the worst case.

When should I use DFS instead of BFS in an interview?

Use DFS when you need every path or combination, when choices must be undone (backtracking, such as Word Search), for cycle detection and topological order in directed graphs, or when counting connected components and recursion is simpler to write.

Can BFS and DFS both solve Number of Islands?

Yes. Any traversal that marks every land cell reachable from a starting cell works, so BFS, DFS and union-find all solve it in O(rows times columns) time. DFS is shortest to write; BFS or iterative DFS avoids recursion limits on very large grids.

What is the time complexity of BFS and DFS?

Both are O(V + E) on an adjacency list, where V is the number of nodes and E the number of edges. On a grid with R rows and C columns, that becomes O(R times C).