Level-order traversal — BFS with queue — Coding notes

What it is

HOW it works — derive the algorithm from scratch

Start from the requirement: visit floor 0, then floor 1, then floor 2…

We can only "see" a node's children once we process that node. So we need to remember nodes we've discovered but not yet processed.
We must process them in discovery order (root first, then root's children left→right, etc.). That ordering demand = FIFO = a queue.
So the recipe writes itself:

Formula The BFS-with-queue procedure

enqueue(root)
while queue not empty:
    node = dequeue()           # take FRONT (oldest)
    visit(node)                # record / print
    if node.left:  enqueue(node.left)
    if node.right: enqueue(node.right)

Why this gives level order: by induction, when all of level $k$ has been enqueued, none of level $k+1$ has been processed yet. Since we always dequeue the oldest, every level- $k$ node is processed (and its children enqueued) before any level- $(k+1)$ node — so children of the whole level $k$ form a contiguous block = level $k+1$ , in left-to-right order.

Figure — Level-order traversal — BFS with queue

Getting one list per level (level grouping)

Plain BFS gives a flat list. To group by level, snapshot the queue size at the start of each round — that size is exactly the count of nodes on the current level.

Formula Level-by-level (grouped) BFS

enqueue(root)
while queue not empty:
    n = size(queue)            # how many nodes on THIS level
    level = []
    repeat n times:
        node = dequeue()
        level.append(node.val)
        if node.left:  enqueue(node.left)
        if node.right: enqueue(node.right)
    output.append(level)

Why snapshot n first? During the inner loop we add children, growing the queue. If we didn't freeze n, we'd bleed into the next level. Freezing it draws a clean fence between floors.

Complexity — reasoned, not memorized

Time $O(n)$ : each node is enqueued exactly once and dequeued exactly once. Constant work per node ⇒ linear total.
Space $O(w)$ where $w$ is the maximum width (most nodes on any single level). Worst case the bottom level of a complete tree holds $\approx n/2$ nodes ⇒ $O(n)$ .

Worked examples

Worked example Example 1 — flat BFS

Tree:

Step	Dequeue	Visit so far	Queue after
init			[1]
1	1	1	[2,3]
2	2	1 2	[3,4,5]
3	3	1 2 3	[4,5,6]
4	4	1 2 3 4	[5,6]
5	5	1 2 3 4 5	[6]
6	6	1 2 3 4 5 6	[]

Output: 1 2 3 4 5 6. Why step 2 enqueues 4,5 behind 3? FIFO appends to the back, so 3 (enqueued earlier) is still served before 4,5. That's what keeps levels in order.

Worked example Example 3 — skewed tree (BFS still correct)

Queue trace: [1]→visit1, [2]→visit2, [3]→visit3, []. Output 1 2 3. Max queue size = 1, so space $O(1)$ here — BFS shines on wide, suffers on... nothing here; it's a path, so width=1.

Common mistake Steel-manning the classic errors

Mistake A: Using a stack instead of a queue. Why it feels right: "I just need a container to hold pending nodes." A stack also holds them — and DFS code looks almost identical. Why it's wrong: a stack is LIFO; it pops the most recently added node, diving deep into the rightmost path first. You get pre-order-ish DFS, not level order. Fix: level order demands FIFO. Use a queue (e.g. collections.deque + popleft()).

Mistake B: Forgetting to snapshot the level size when grouping. Why it feels right: "I'll just loop while the queue isn't empty." But the queue keeps growing as you add children mid-loop. Fix: capture n = len(queue) before the inner loop; iterate exactly n times.

Mistake C: Enqueuing None children. Why it feels right: uniform code ("just push both kids"). Why it bites: you later dereference None.left. Fix: guard if node.left: before enqueue, or check for None when dequeuing.

Mistake D: Using a Python list with list.pop(0) as the queue. Why it feels right: lists are the default container. Why it's slow: pop(0) is $O(n)$ (shifts everything), making BFS $O(n^2)$ . Fix: use deque.popleft() which is $O(1)$ .

Recall Feynman: explain to a 12-year-old (click to reveal)

Picture a family tree drawn on a wall. You want to read out names one row at a time, left to right. You hold a line of people waiting (a queue). You call the first person in line, write their name, and tell them: "send your kids to the BACK of the line." Then you call the next person in line. Because new kids always go to the back, you finish reading a whole row before any kid from that row gets called. That's level order — and the waiting line is the queue!

Active recall

What data structure makes level-order traversal natural, and why?

A queue (FIFO); it serves nodes in discovery order so closer/leftmost nodes are processed first, producing level-by-level order.

Why does using a stack instead of a queue break level-order traversal?

A stack is LIFO, so it dives into the most recently added (deepest) node first — that yields depth-first order, not level order.

In grouped (level-by-level) BFS, why must you snapshot len(queue) before the inner loop?

Because the queue grows as you enqueue children; freezing the count fences off exactly the current level's nodes so you don't spill into the next level.

What is the time complexity of BFS on a tree and why?

O(n)

— each node is enqueued once and dequeued once with

O(1)

work each.

What is the space complexity of BFS and what determines it?

O(w)

where

w

is the maximum level width; worst case

O(n)

(bottom level of a complete tree ≈ n/2 nodes).

Why is list.pop(0) a bad queue for BFS in Python?

It is

O(n)

(shifts all elements), degrading BFS to

O(n^2)

; use collections.deque.popleft() for

O(1)

On a tree, how is BFS related to "distance from root"?

Level/depth equals distance from root, so BFS (which expands by increasing distance) visits nodes in level order.

What guard prevents a crash when a node lacks a child during BFS?

Check if node.left / if node.right (or skip None) before enqueuing/dereferencing.

Connections

Breadth-First Search (BFS) — the general graph algorithm; level-order is its tree special case.
Depth-First Search (DFS) — the stack/recursion counterpart (pre/in/post-order).
Queue (FIFO) data structure — the engine of BFS; contrast with Stack (LIFO).
Binary Tree representation — nodes with .left / .right.
Shortest path in unweighted graphs — BFS's killer app; level = hop count.
Tree height vs width — explains the DFS-stack vs BFS-queue space trade-off.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Level-order traversal ka matlab hai tree ko floor by floor padhna — sabse upar root, fir uske niche wale bachche, fir unke bachche. Yeh exactly BFS hai. Iske liye hum queue use karte hain kyunki queue FIFO hai: jo pehle line mein aaya, woh pehle serve hota hai. Isi wajah se upar wale aur left wale nodes pehle process hote hain aur output sahi order mein aata hai.

Algorithm bilkul simple hai: root ko queue mein daalo. Jab tak queue khaali na ho — front se node nikaalo (dequeue), use visit karo, aur uske left aur right child (agar exist karte hain) ko queue ke peeche daal do. Bas! Kyunki naye bachche hamesha peeche jaate hain, ek poora level khatam hone se pehle agle level ka koi node process nahi hota. Agar tumhe har level ki alag list chahiye, to inner loop se pehle n = len(queue) snapshot le lo — yahi current level ke nodes ki ginti hai, aur tum theek utni baar loop chalao.

Do badi galtiyan yaad rakhna: (1) Stack mat use karna queue ki jagah — stack LIFO hai, woh deep chala jayega aur DFS ban jayega, level order nahi. (2) Python mein list.pop(0) mat use karna kyunki woh $O(n)$ hai aur poora BFS $O(n^2)$ ho jata hai; iski jagah collections.deque ka popleft() use karo jo $O(1)$ hai.

Complexity samajhna easy hai: har node ek baar andar, ek baar bahar — isliye time $O(n)$ . Space queue ke max size par depend karta hai, jo tree ki maximum width ( $w$ ) hota hai. Yaad rakho: DFS stack ek path (height) rakhta hai, BFS queue ek level (width) rakhta hai — yahi dono ka basic trade-off hai. BFS unweighted graph mein shortest path nikalne ke liye bhi sabse zaroori tool hai, isliye yeh concept pakka karna.

Level-order traversal — BFS with queue

What it is

HOW it works — derive the algorithm from scratch

Getting one list per level (level grouping)

Complexity — reasoned, not memorized

Worked examples

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections