This page is the stress-test for level-order BFS . The parent taught the recipe on one friendly tree. Here we deliberately throw every awkward shape at it — empty trees, single nodes, one-sided skews, fat bottom levels — and watch the queue behave correctly in each. If you can hand-trace all of these, no interviewer's tree will surprise you.
Before we begin, one shared vocabulary reminder so no symbol sneaks in undefined:
Definition The three words we lean on
Enqueue = push a node to the back of the waiting line.Dequeue = remove and return the node at the front (the oldest one waiting).Level (depth) = how many steps down from the root a node sits. Root is level 0 n w width , i.e. the largest number of nodes on any single level. h height , the deepest level index.
Every tree BFS problem falls into one of these cells. The examples below each carry a tag like (Cell C3) so you can see the coverage is complete.
Cell
Case class
What's tricky about it
Covered by
C1
Empty tree (root is null)Loop must never start; output empty
Ex 1
C2
Single node (root only)One dequeue, no children enqueued
Ex 2
C3
Balanced / bushy tree Queue swells to width w
Ex 3
C4
Left-skewed path Width stays 1
Ex 4
C5
Right-skewed path Same but mirror; test the None-guard on left
Ex 4b
C6
Zig-zag / lopsided Levels have different sizes; snapshot test
Ex 5
C7
Complete tree, wide bottom Peak queue ≈ n /2
Ex 6
C8
Word problem (shortest hops)BFS = distance-from-root in disguise
Ex 7
C9
Exam twist (right-side view)Use last node of each level snapshot
Ex 8
Run level-order BFS on a tree whose root is None. What is the output?
Forecast: guess before reading — does the code crash, loop forever, or return []?
Steps:
We are told root = None. The very first thing the grouped procedure does is enqueue(root)… but a careful implementation guards this: if not root: return [].
Why this step? Enqueuing None and then trying None.left is Mistake C from the parent. The empty case must be caught before the loop.
With the guard, we never enter while queue not empty because we never enqueued anything (or the guard returned first).
Why this step? An empty queue means the while condition is false on line one — zero rounds run.
Output is [].
Verify: n = 0 O ( n ) = O ( 0 )
Tree is just 7 (no children). Trace flat BFS.
Forecast: how many dequeues happen, and how big does the queue ever get?
Steps:
enqueue(7) → queue [7].
Why? We always seed the queue with the root.
Round 1: dequeue 7, visit it. Check 7.left → None, skip. Check 7.right → None, skip.
Why the checks? The if node.left / if node.right guards stop us from pushing None — this is exactly the safety net that lets Example 1 and the skewed cases work.
Queue is now [], loop ends. Output 7.
Verify: peak queue size = 1 = w = O ( n ) n = 1
Trace both flat and grouped BFS on the tree in the figure:
A
/ \
B C
/ \ / \
D E F G
Forecast: flat output should be alphabetical here — why? And what are the three level-groups?
Steps (flat):
enqueue(A) → [A].Dequeue A, visit; enqueue B, C → [B, C].
Why B before C? We enqueue left first, so B sits ahead of C in the line — left-to-right order is baked in here.
Dequeue B, visit; enqueue D, E → [C, D, E].
Why do D,E go behind C? FIFO appends to the back. C (enqueued in step 2) is still ahead, so C is served before any of B's children.
Dequeue C, visit; enqueue F, G → [D, E, F, G].
Dequeue D, E, F, G in turn; each has no children.
Steps (grouped): snapshot n = len(queue) at each round.
Round 1: n = 1. Process A, enqueue B,C. Level [A].
Round 2: n = 2. Process exactly B, C, enqueue D,E,F,G. Level [B, C].
Why snapshot n=2? We froze the count before processing. Mid-loop the queue grew to 4, but we only touch the 2 we fenced off — no bleeding into level 2.
Round 3: n = 4. Process D, E, F, G. Level [D, E, F, G].
Grouped output: [[A], [B, C], [D, E, F, G]].
Verify: n = 7 O ( 7 ) = 4 = w 1 , 2 , 4 7 = n
1
/
2
/
3
Every node has only a left child.
Forecast: what is the peak queue size — and does that make BFS behave like Depth-First Search (DFS) here?
Steps:
enqueue(1) → [1].Dequeue 1; 1.left = 2 exists → enqueue; 1.right = None → skip . Queue [2].
Why does the right-guard matter? Without if node.right we'd push None and later crash. On a skew, the guard fires every single round.
Dequeue 2; enqueue 3; skip right. Queue [3].
Dequeue 3; both children None, skip both. Queue []. Output 1 2 3.
Verify: peak queue size = 1 O ( 1 ) not O ( w ) w w = 1 same order (1 2 3), but that's a coincidence of the shape, not a rule. ✓
1
\
2
\
3
Forecast: which guard fires now — left or right?
Steps:
enqueue(1) → [1].Dequeue 1; 1.left = None → skip left ; 1.right = 2 → enqueue. Queue [2].
Why? This is the mirror of Ex 4: now the left guard fires every round.
Dequeue 2 → enqueue 3 on the right. Dequeue 3 → both null, skip. Output 1 2 3.
Verify: peak queue = 1 = w 1 2 3 identical to Ex 4 — the values match but the geometry is mirrored. Enqueues = 3 = n
1
/ \
2 3
/ \
4 5
/
6
Levels have sizes 1 , 2 , 2 , 1
Forecast: grouped BFS must produce four groups of unequal size. Which snapshot values n appear?
Steps:
Round 1: n = 1. Process 1, enqueue 2,3 → [[1]].
Round 2: n = 2. Process 2, 3. 2.left=4 enqueue, 2.right=None skip; 3.left=None skip, 3.right=5 enqueue. Queue [4, 5]. Group [2, 3].
Why mixed guards here? Node 2 only has a left child, node 3 only a right — both single-child guards fire in the same round. This is where naive "push both" (Mistake C) would blow up twice.
Round 3: n = 2. Process 4, 5. 4 has no children. 5.left = 6 enqueue, 5.right = None skip. Queue [6]. Group [4, 5].
Round 4: n = 1. Process 6, no children. Group [6].
Output: [[1], [2, 3], [4, 5], [6]].
Verify: snapshot values were 1 , 2 , 2 , 1 6 = n = 2 = w 3 0..3 Tree height vs width for why these two numbers can differ so much. ✓
A complete tree with n = 15 1 , 2 , 4 , 8 peak queue size during flat BFS, and why is this the worst case for BFS memory?
Forecast: guess the peak before computing — is it closer to log 2 n n /2
Steps:
The queue holds "discovered-but-not-yet-processed" nodes. The moment it is fullest is when we have finished enqueuing an entire wide level but not yet dequeued much of it .
Why? Children of level k k
The bottom level of this complete tree has 8 8 8
Why 8 In a complete tree the last level holds up to ⌈ n /2 ⌉ = ⌈ 15/2 ⌉ = 8
So peak queue = 8 = w O ( w ) = O ( n )
Verify: ⌈ 15/2 ⌉ = 8 1 + 2 + 4 + 8 = 15 = n = 3 2 3 + 1 − 1 = 15 h = 3
An org chart is a tree: the CEO is the root, each manager's reports are their children. A rumor starts at the CEO and each person passes it to all their direct reports in one "round." Using the tree of Example 3 (root A, leaves D,E,F,G), after how many rounds does everyone hear it, and who hears it in round 2?
Forecast: what does "round number" correspond to in tree language?
Steps:
Recognize the disguise: "round of passing" = level of the tree = distance from root. This is exactly Shortest path in unweighted graphs — BFS layers are shortest-hop distances.
Why BFS and not DFS? BFS expands strictly by increasing distance; it answers "how far?" questions. DFS would dive down one branch and give the wrong first-arrival times.
Grouped BFS on the Ex 3 tree gave [[A], [B, C], [D, E, F, G]]. Round 0 1 2
Everyone (all 7) has heard by the end of round 2
Verify: number of rounds = = 2 = { D , E , F , G } 4 = 1 + 2 + 4 = 7 = n
Return the values visible when looking at the tree from the right — i.e. the last node of each level. Use the lopsided tree of Example 5.
Forecast: is the answer just "all rightmost children"? (Careful — node 5 hangs under 3, and 6 hangs under 5.)
Steps:
Run grouped BFS but, in each round, remember only the node dequeued last (index n-1 of that round).
Why the last of the round? The snapshot n fences one level; within it we process left→right, so the final dequeue is the rightmost node on that level — precisely what the eye sees from the right.
From Ex 5's groups [[1], [2,3], [4,5], [6]], take the last of each: 1, 3, 5, 6.
Why not "rightmost child every time"? Level 2's rightmost is 5 (child of 3, on the right), and level 3 has only 6 — BFS finds these automatically because it already orders each level left→right. No special-casing needed.
Right-side view: [1, 3, 5, 6].
Verify: four levels ⇒ four values, one per level. Values 1 , 3 , 5 , 6 1 , 2 , 2 , 1 same snapshot trick as grouping — the twist is only "keep the last, drop the rest." ✓
Common mistake Cross-example pitfalls to reread
Ex 5 & 8 both fail loudly if you skip the None-guard (Mistake C) — mixed single-child levels push a None twice per round.Ex 6 is where a list.pop(0) queue (Mistake D) hurts most: peak queue ≈ n /2 pop(0) shifts ∼ n /2 O ( n 2 ) deque.popleft().Ex 1 proves why the empty-tree guard belongs before the loop, not inside it.
Recall Self-test across the matrixCover the answers below and reconstruct each.
Which cell has peak queue size ≈ n/2, and why? ::: The complete-tree case (Cell C7); the fat bottom level holds ⌈n/2⌉ nodes that all sit in the queue at once.
On a skewed path, what is BFS's space complexity and why? ::: O ( 1 ) w = 1 n per level, but keep only the last-dequeued (rightmost) node of each round.
Why is a word "rounds of rumor spreading" a BFS problem? ::: Round number equals distance from root equals tree level, and BFS expands by increasing distance — the unweighted shortest-path structure.
What single guard makes the empty tree, skewed trees, and lopsided levels all safe? ::: Checking if node.left / if node.right (skip None) before enqueuing.
Parent: Level-order BFS — the recipe these examples stress-test.Breadth-First Search (BFS) — general algorithm; every example is its tree instance.Depth-First Search (DFS) — contrast in Ex 4 and Ex 6 (path order coincidence; stack vs queue space).Queue (FIFO) data structure — the FIFO behavior that keeps every level in order.Stack (LIFO) — what you'd wrongly get with Mistake A.Binary Tree representation — the node/left/right model all traces assume.Shortest path in unweighted graphs — the disguise behind Ex 7.Tree height vs width — why Ex 5's height (3) and width (2) differ, and why Ex 6's do too. 
