Algorithm1 Practice7 Interview

Breadth-first Search

GuideCode Labs

Explore states level by level, yielding shortest unweighted path lengths from the source set. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Breadth-first Search when the prompt's constraints and required operations match this shape: Explore states level by level, yielding shortest unweighted path lengths from the source set.

On this page · Explore One Distance Layer at a Time

Checking your account…

Explore One Distance Layer at a Time

Breadth-first search processes all states at distance (d) before any state at distance (d + 1). In an unweighted graph, the first discovery therefore gives a shortest edge distance.

Own the Queue Frontier

The queue contains discovered nodes whose outgoing edges are not fully processed. Capturing the queue length before a level loop isolates one layer even as children are appended behind it.

Trace BFS Layers

Reference

from collections import deque

def bfs_layers(adjacency, start):
    if start == -1: return []
    queue = deque([start])
    seen = {start}
    layers = []
    while queue:
        layer = []
        for _ in range(len(queue)):
            node = queue.popleft()
            layer.append(node)
            for neighbor in adjacency[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append(neighbor)
        layers.append(layer)
    return layers

Practice

Implement bfs_layers(adjacency, start). Return reachable node indexes grouped by unweighted distance, preserving neighbor order.

def bfs_layers(adjacency, start):
    pass

Public tests

Separate queue layers

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Mark Visited on Enqueue

Mark a node when it enters the queue, not when it leaves. That prevents two parents in the same layer from enqueueing the same neighbor and keeps both work and memory bounded by vertices plus edges.

Find Unweighted Distances

Reference

from collections import deque

def shortest_distances(adjacency, start):
    distances = [-1] * len(adjacency)
    if start == -1: return distances
    distances[start] = 0
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in adjacency[node]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    return distances

Practice

Implement shortest_distances(adjacency, start). Return a list of shortest edge distances, using -1 for unreachable nodes.

def shortest_distances(adjacency, start):
    pass

Public tests

Assign first-discovery distance

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose BFS or DFS

Choose BFS for shortest unweighted paths, minimum moves, or explicit level order. Choose DFS when branch completion, postorder aggregation, or lower frontier width matters. Both traverse reachable graphs in O(V + E); BFS may hold an entire wide layer.

Explain It in an Interview

Say: “The queue is ordered by distance. I mark on enqueue, so each node enters once, and first discovery fixes its shortest unweighted distance.” Mention disconnected nodes and multi-source initialization. Binary Tree Level Order(opens in a new tab) applies the same layer boundary to a tree.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Breadth-first Search proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Breadth-first Search complete workflow	`O(n)`	`O(n)`	Level-oriented tree output needs a queue plus the number of nodes present before the next frontier is appended. At the start of each outer iteration, the queue contains exactly the current level in left-to-right order.

Space

O(w) for maximum frontier width for the focused Expand One Tree Level implementation.

Assumptions

Capturing the current queue length isolates one level before children are appended. Summing exactly those nodes and enqueueing their children constructs the next level, so one correct sum is emitted per depth.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Breadth-first Search invariant before coding and preserve it after every update, traversal step, or recursive return.
The frontier contains exactly discovered work that has not yet been fully processed.
Visited state prevents a node or state from being processed through the same role twice.
Level-oriented tree output needs a queue plus the number of nodes present before the next frontier is appended. Preserve this claim after every transition.
At the start of each outer iteration, the queue contains exactly the current level in left-to-right order. Preserve this claim after every transition.

When To Use Or Avoid Breadth-first Search

Use It When

Use Breadth-first Search when this precondition is stated or can be proved: The graph or state space has an explicit neighbor relation and repeated states can be identified.
Use it when this maintained state removes repeated work: The frontier contains exactly discovered work that has not yet been fully processed.

Choose Another Tool When

Avoid Breadth-first Search when this precondition is absent: The graph or state space has an explicit neighbor relation and repeated states can be identified.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The graph or state space has an explicit neighbor relation and repeated states can be identified.

Avoid

def tree_level_sums(values, children, root):
    pass

Use instead

from collections import deque

def tree_level_sums(values, children, root):
    if root == -1:
        return []
    queue = deque([root])
    sums = []
    while queue:
        level_sum = 0
        for _ in range(len(queue)):
            node = queue.popleft()
            level_sum += values[node]
            queue.extend(children[node])
        sums.append(level_sum)
    return sums

Where you will hit this: Expand One Tree Level(opens in a new tab)

Breaking the state transition

Consumes the entire frontier in one pass and returns one total instead of preserving breadth-first level boundaries.

Prevent it: Preserve this proof obligation: Every reachable state enters the frontier under the traversal policy, while visited state prevents duplicate work.

Avoid

from collections import deque

def tree_level_sums(values, children, root):
    if root == -1:
        return []
    queue = deque([root])
    total = 0
    while queue:
        node = queue.popleft()
        total += values[node]
        queue.extend(children[node])
    return [total]

Use instead

from collections import deque

def tree_level_sums(values, children, root):
    if root == -1:
        return []
    queue = deque([root])
    sums = []
    while queue:
        level_sum = 0
        for _ in range(len(queue)):
            node = queue.popleft()
            level_sum += values[node]
            queue.extend(children[node])
        sums.append(level_sum)
    return sums

Where you will hit this: Expand One Tree Level(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

from collections import deque

def tree_level_sums(values, children, root):
    if root == -1:
        return []
    queue = deque([root])
    total = 0
    while queue:
        node = queue.popleft()
        total += values[node]
        queue.extend(children[node])
    return [total]

Use instead

from collections import deque

def tree_level_sums(values, children, root):
    if root == -1:
        return []
    queue = deque([root])
    sums = []
    while queue:
        level_sum = 0
        for _ in range(len(queue)):
            node = queue.popleft()
            level_sum += values[node]
            queue.extend(children[node])
        sums.append(level_sum)
    return sums

Where you will hit this: Binary Tree Level Order(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python collections.deque(opens in a new tab)
python-docs · checked 2026-07-12
Python deque Recipes(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…