When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Minimum unweighted steps
- Level order
- Nearest target
When another approach fits better
- Edges have unequal costs
- The answer depends on postorder aggregation rather than minimum layer
How it works#
Enumerate paths or run a new search from each candidate source.
Choose one source or enqueue every simultaneous source at distance zero.
Mark visited when enqueued to prevent duplicate frontier entries.
Process one queue layer or store distances explicitly.
InvariantWhen a node is first dequeued, its recorded layer is the minimum number of unweighted edges from the source set.
Example and template#
Binary Tree Level Order Traversal
Capture each queue level before adding the next one.
Open the full problem brief- Layer 0
queue: [A]A is the only distance-zero source.
- Layer 1
queue: [B, C]First discovery assigns the minimum one-edge distance.
queue = all sources
mark all sources visited
while queue not empty:
node = dequeue
for neighbor of node:
if unseen:
mark seen
distance[neighbor] = distance[node] + 1
enqueue neighbor- Time
- O(V + E)
- Space
- O(V)
- Assumptions
- Adjacency enumeration is linear in edges and all traversed edges have equal unit cost.
Pitfalls#
Common wrong approaches
Several parents can enqueue the same node, inflating work and obscuring distance ownership.
Queue order no longer guarantees nondecreasing total cost.
Edge cases
- No sources
- Disconnected target
- Multiple sources
- Implicit neighbors and boundary checks
Interview narration
- “Because every move costs one, queue layers are distance layers.”
- “I mark on enqueue so each node enters the frontier once.”
- “The first time I reach the target is therefore optimal.”
Practice#
Binary Tree Level Order Traversal
Capture each queue level before adding the next one.
Practice this problemSeveral infected cells spread to orthogonal neighbors once per minute; find when all reachable cells are infected.
Reveal the pattern decision
Seed a multi-source BFS so all origins share the same distance clock.
Transfer problem
Find the fewest one-letter transformations between valid dictionary words.
Checkpoint: Model words as implicit nodes and generate only valid unseen neighbors.
Follow-up variations
- Reconstruct one minimum path with parent pointers
- Use bidirectional BFS when both endpoints and branching justify it
Error-log prompts
- When did a node become visited?
- Why were all edges effectively equal cost?