Stack vs Queue = Depth vs Breadth (A Preview)

"Here's a secret that'll make the Trees and Graphs tracks feel easy: depth-first and breadth-first search are the same algorithm. The only difference is whether the to-do list is a stack or a queue."

The Frontier

Whenever you explore a structure — a maze, a tree, a network — you keep a frontier: the set of places you've discovered but not yet explored. The algorithm is always the same shape: take a place from the frontier, look at it, add its undiscovered neighbors to the frontier, repeat until the frontier is empty. The entire character of the search comes down to one question: which place do you take next?

The Single Swap That Changes Everything

That "which next?" is answered by the data structure holding the frontier:

Frontier is a stack → you take the most recently discovered place → you keep plunging down the newest path → depth-first search (DFS). You go as deep as possible before backing up.
Frontier is a queue → you take the oldest discovered place → you finish everything close before going further → breadth-first search (BFS). You sweep outward in rings, level by level.

That's it. Same code skeleton; swap stack.pop() for queue.popleft() and depth-first becomes breadth-first. Two of the most important algorithms in computing differ by a single line.

Search is: pull from the frontier, visit, add neighbors, repeat. A stack frontier gives depth-first (newest first, plunge deep); a queue frontier gives breadth-first (oldest first, sweep wide). The data structure choice IS the algorithm.

Why Each One Matters

BFS explores in order of distance, so it naturally finds the shortest path (in number of steps) — which is why it's the backbone of the Graphs track. DFS dives deep, which suits exhaustively exploring all possibilities, detecting cycles, and topological ordering — and it's exactly the backtracking you'll meet in the Recursion track (where the stack is the call stack itself). The same stack/queue duality you just learned is the engine under both trees and graphs. You've already built the hard part.

Pippa's Confession

I learned DFS and BFS as two separate algorithms, memorized independently, and promptly mixed them up under pressure. Then Dad wrote one explore function and showed me that swapping the stack for a queue flipped depth into breadth — and they fused into a single idea I could never un-see. It's my favorite kind of lesson: not two facts to memorize, but one fact that dissolves the need to memorize. The frontier's data structure is the whole story.

Code

One skeleton, stack vs queue = DFS vs BFS·python

from collections import deque

# A tiny tree as a dict: node -> children
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}

def explore(start, use_stack):
    """ONE skeleton. Stack frontier = DFS; queue frontier = BFS."""
    frontier = [start]                # for stack we use a list (.pop)
    order = []
    while frontier:
        node = frontier.pop() if use_stack else frontier.pop(0)
        order.append(node)
        # add children to the frontier
        for child in tree[node]:
            frontier.append(child)
    return order

print("DFS (stack):", explore("A", use_stack=True))   # plunges deep
print("BFS (queue):", explore("A", use_stack=False))  # sweeps by level
# DFS visits a deep path before siblings; BFS visits level by level (A, then
# B C, then D E F). The ONLY change is which end of the frontier we pull from.
# (In real BFS use deque.popleft() for O(1); list.pop(0) here is for clarity.)

Exercise

Using the tree A→(B,C), B→(D,E), C→(F): write the visit order for DFS (stack frontier) and for BFS (queue frontier), by hand. Then state in one sentence why BFS is the natural choice when you want the fewest steps to a target, and DFS when you want to exhaust one path fully before trying another.

Hint

BFS visits by distance from the start (A; then B,C; then D,E,F), so the first time it reaches a target, that's the shortest step-count. DFS commits to one branch all the way down before backtracking — ideal for 'explore every possibility' problems.

The Frontier

The Single Swap That Changes Everything

Why Each One Matters

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0