Stack vs Queue = Depth vs Breadth (A Preview)

"Here's the secret that makes the Trees and Graphs tracks feel easy: DFS and BFS share one traversal skeleton. Swap the frontier from a stack to a queue and depth flips into breadth. Visited timing and duplicate handling complete it, but the container is the switch that changes its temperament."

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.

The frontier container is the central difference, but changing one method call is not always the whole implementation. Neighbor order, discovery timing, duplicate suppression, and parent or distance recording affect correctness, efficiency, and the exact traversal order.

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 separate spells and mixed them up whenever pressure arrived. Then Dad wrote one explore function and swapped its stack for a queue; depth flipped into breadth in front of me, and the two fused into one 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 chooses the traversal's temperament; visited timing and duplicate handling turn that skeleton into a complete algorithm.

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