Level-order traversal — BFS with queue — Hinglish notes

3.4.3 · Coding › Trees

Yeh hai kya

HOW it works — algorithm scratch se derive karo

Requirement se shuru karo: floor 0 visit karo, phir floor 1, phir floor 2…

Hum kisi node ke children tab hi "dekh" sakte hain jab hum us node ko process kar lein. Toh humein un nodes ko yaad rakhna hoga jo discover ho chuke hain par abhi process nahi hue.
Humein unhe discovery order mein process karna hai (pehle root, phir root ke children left→right, etc.). Yeh ordering demand = FIFO = ek queue.
Toh recipe khud likh jaati hai:

Formula BFS-with-queue procedure

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

Yeh level order kyun deta hai: induction se, jab level $k$ ke saare nodes enqueue ho jaate hain, tab level $k + 1$ ka koi bhi node abhi process nahi hua hota. Kyunki hum hamesha sabse purane ko dequeue karte hain, har level- $k$ node process ho jaata hai (aur uske children enqueue ho jaate hain) kisi bhi level- $(k + 1)$ node se pehle — isliye puri level $k$ ke children ek contiguous block banate hain = level $k + 1$ , left-to-right order mein.

Figure — Level-order traversal — BFS with queue

Har level ki ek alag list banana (level grouping)

Plain BFS ek flat list deta hai. Level ke hisaab se group karne ke liye, har round ke start mein queue ka size snapshot lo — woh size exactly us current level ke nodes ki count hai.

Formula Level-by-level (grouped) BFS

enqueue(root)
while queue not empty:
    n = size(queue)            # IS level par kitne nodes hain
    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)

n pehle snapshot kyun karo? Inner loop ke dauran hum children add karte hain, queue grow hoti hai. Agar hum n freeze nahi karte, toh hum agले level mein ghus jaate. Freeze karna floors ke beech ek saaf fence kheenchta hai.

Complexity — reasoned, not memorized

Time $O (n)$ : har node exactly ek baar enqueue aur ek baar dequeue hota hai. Har node par constant work ⇒ linear total.
Space $O (w)$ jahan $w$ maximum width hai (kisi bhi single level par sabse zyada nodes). Worst case mein ek complete tree ke bottom level par $\approx n /2$ nodes hote hain ⇒ $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. Step 2 mein 4,5 ko 3 ke peeche kyun enqueue kiya? FIFO back mein append karta hai, isliye 3 (jo pehle enqueue hua tha) 4,5 se pehle serve hota hai. Yahi levels ko order mein rakhta hai.

Worked example Example 3 — skewed tree (BFS phir bhi correct)

Queue trace: [1]→visit1, [2]→visit2, [3]→visit3, []. Output 1 2 3. Max queue size = 1, toh yahan space $O (1)$ — BFS wide trees par shine karta hai, suffers on... yahan kuch nahi; yeh ek path hai, isliye width=1.

Common mistake Classic errors ko steel-man karna

Mistake A: Queue ki jagah stack use karna. Kyun sahi lagta hai: "Mujhe bas pending nodes rakhne ke liye ek container chahiye." Stack bhi unhe rakhta hai — aur DFS code almost identical lagta hai. Kyun galat hai: stack LIFO hai; yeh sabse recently add hue (deepest) node ko pehle pop karta hai, aur rightmost path mein deep dive karta hai. Tumhe pre-order-ish DFS milega, level order nahi. Fix: level order ke liye FIFO chahiye. Queue use karo (jaise collections.deque + popleft()).

Mistake B: Grouping karte waqt level size snapshot karna bhool jaana. Kyun sahi lagta hai: "Main bas loop chalaunga jab tak queue empty nahi ho jaata." Par queue mid-loop mein children add karte karte badhti rehti hai. Fix: inner loop se pehle n = len(queue) capture karo; exactly n baar iterate karo.

Mistake C: None children ko enqueue karna. Kyun sahi lagta hai: uniform code ("bas dono kids push kar do"). Kyun problem hoti hai: baad mein tum None.left dereference karte ho. Fix: enqueue se pehle if node.left: guard lagao, ya dequeue karte waqt None check karo.

Mistake D: Python list mein list.pop(0) queue ki tarah use karna. Kyun sahi lagta hai: lists default container hain. Kyun slow hai: pop(0) $O (n)$ hai (sab kuch shift karta hai), BFS ko $O (n^{2})$ bana deta hai. Fix: deque.popleft() use karo jo $O (1)$ hai.

Recall Feynman: 12-saal ke bachche ko samjhao (click to reveal)

Socho ek family tree deewar par bani hai. Tum names ek row at a time, left se right padhna chahte ho. Tumhare paas waiting mein khade logon ki ek line hai (ek queue). Tum line mein pehle waale ko bulao, unka naam likho, aur unhe kaho: "apne bachche line ke PEECHE bhej do." Phir line mein agla banda bulao. Kyunki naye bachche hamesha peeche jaate hain, tum ek poori row padh lete ho pehle, aur us row ka koi bhi bachcha tab tak nahi bulaya jaata. Yahi level order hai — aur waiting line hi queue hai!

Active recall

Level-order traversal ke liye kaun sa data structure natural hai, aur kyun?

Queue (FIFO); yeh nodes ko discovery order mein serve karta hai isliye paas/leftmost nodes pehle process hote hain, level-by-level order produce hoti hai.

Queue ki jagah stack use karna level-order traversal kyun tod deta hai?

Stack LIFO hai, isliye yeh sabse recently add hue (deepest) node mein pehle jaata hai — isse depth-first order milti hai, level order nahi.

Grouped (level-by-level) BFS mein, inner loop se pehle len(queue) snapshot kyun karna zaroori hai?

Kyunki queue children enqueue karte waqt badhti hai; count freeze karna exactly current level ke nodes ko fence karta hai taaki tum agले level mein na ghuso.

Tree par BFS ki time complexity kya hai aur kyun?

O (n)

— har node ek baar enqueue aur ek baar dequeue hota hai jisme

O (1)

work lagta hai.

BFS ki space complexity kya hai aur use kya determine karta hai?

O (w)

jahan

w

maximum level width hai; worst case

O (n)

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

Python mein BFS ke liye list.pop(0) bura queue kyun hai?

Yeh

O (n)

hai (saare elements shift karta hai), BFS ko

O (n^{2})

bana deta hai;

O (1)

ke liye collections.deque.popleft() use karo.

Tree par, BFS ka "root se distance" se kya relation hai?

Level/depth root se distance ke barabar hai, isliye BFS (jo badhte distance se expand karta hai) nodes ko level order mein visit karta hai.

BFS ke dauran child missing hone par crash rokne wala guard kya hai?

Enqueue/dereference se pehle if node.left / if node.right check karo (ya None skip karo).

Connections

Breadth-First Search (BFS) — general graph algorithm; level-order uska tree special case hai.
Depth-First Search (DFS) — stack/recursion counterpart (pre/in/post-order).
Queue (FIFO) data structure — BFS ka engine; Stack (LIFO) se contrast karo.
Binary Tree representation — .left / .right wale nodes.
Shortest path in unweighted graphs — BFS ka killer app; level = hop count.
Tree height vs width — DFS-stack vs BFS-queue space trade-off explain karta hai.