Exercises — Level-order traversal — BFS with queue

Read floor by floor:

• Floor 0: 1
• Floor 1: 2 3
• Floor 2: 4 5 6
• Floor 3: 7

Output: 1 2 3 4 5 6 7. That is literally reading the picture top-to-bottom, left-to-right — which is exactly what BFS with a queue produces.

A queue (FIFO). We remove from the front with dequeue (popleft in Python). A Stack (LIFO) would pop the most-recently-added node and dive deep, giving Depth-First Search (DFS) order instead.

Levels: 0,1,2,3 → 4 levels. Height counts edges on the longest path (root → 2 → 5 → 7): that is 3 edges, so $h=3$. Note: number of levels = $h+1$. A common slip is to confuse the two.

Snapshot n = len(queue) at the start of each round:

• Round 1: n=1, process 1, enqueue 2,3 → [1]
• Round 2: n=2, process 2,3, enqueue 4,5 (from 2) and 6 (from 3) → [2,3]
• Round 3: n=3, process 4,5,6; node 5 enqueues 7 → [4,5,6]
• Round 4: n=1, process 7 → [7]

Output: [[1],[2,3],[4,5,6],[7]].

Max queue size reached = 3 (after step 2). This equals the tree's max width $w=3$ (floor 2 holds 4,5,6).

Index → value: 0:1, 1:2, 2:3, 3:4, 4:5, 5:null, 6:6.

• 1 (idx 0): children idx 1,2 = 2,3
• 2 (idx 1): children idx 3,4 = 4,5
• 3 (idx 2): children idx 5,6 = null,6 → only right child 6

Tree:

      1
     / \
    2   3
   / \    \
  4   5    6

Flat BFS = read the array skipping null: 1 2 3 4 5 6.

Stack, push order = left then right, so right is on top and pops first.

• push 1. Pop 1; push 2,3 → stack [2,3] (3 on top).
• Pop 3; 3 has right child 6 → push 6 → [2,6].
• Pop 6 (leaf) → [2].
• Pop 2; push 4,5 → [4,5] (5 on top).
• Pop 5; 5 has child 7 → push 7 → [4,7].
• Pop 7 (leaf) → [4].
• Pop 4 (leaf) → [].

Order: 1 3 6 2 5 7 4. This is a depth-first pre-order that follows the right branch first (because we pushed left first, so right sits on top). It is not level order — proving the container choice is what encodes the traversal.

From the trace in 2.2 the queue sizes were 1,2,3,2,2,1,0 → max = 3.

• Width $w=3$ (floor 4,5,6). Height $h=3$.
• The queue holds ~one level's worth of nodes, so BFS space is $O(w)$, here $3$.
• Contrast: DFS's stack holds one path, so $O(h)$, here also $\le 3$.

They happen to match on this small tree, but they diverge on shape: see Tree height vs width. On a wide tree BFS costs more; on a deep skewed tree DFS costs more.

Each outer round starts by snapshotting n = len(queue). Claim: at the start of round $k$ (1-indexed) the queue contains exactly all nodes of level $k-1$, and nothing else.

Base: round 1 starts with just the root = all of level 0. ✓ Inductive step: suppose round $k$ starts holding exactly level $k-1$. The inner loop processes all $n$ of them, and enqueues only their children, which are precisely the nodes of level $k$ (a tree node has a unique parent, so no duplicates, no gaps). After the inner loop the queue holds exactly level $k$. ✓

The loop stops when the queue is empty — i.e. after the round that processed the last non-empty level. So the outer loop runs once per level. $■$

Keep normal BFS (children always enqueued left→right so the queue stays honest); only reverse the emitted list on odd levels.

• Level 0 (even): [1]
• Level 1 (odd): natural [2,3] → reversed [3,2]
• Level 2 (even): [4,5,6]
• Level 3 (odd): natural [7] → reversed [7]

Output: [[1],[3,2],[4,5,6],[7]]. Change: keep a boolean left_to_right; after building each level list, if not left_to_right: level.reverse(), then flip the boolean. Do not reverse the enqueue order — that would corrupt the next level's ordering.

During grouped BFS, the last node dequeued in each round is that level's rightmost.

• Level 0 last: 1
• Level 1 last: 3
• Level 2 last: 6
• Level 3 last: 7

Output: [1,3,6,7]. Because we process each level as a contiguous block of size n, the node at inner-loop index n-1 is exactly the rightmost — no extra bookkeeping needed.

Tag each node with dist = parent.dist + 1, root dist = 0. 1→0, 2→1, 3→1, 4→2, 5→2, 6→2, 7→3. Distance to 7 = 3 edges. BFS expands nodes in increasing distance order, so the first time you reach a node you have used the fewest edges — that is the shortest path in an unweighted graph. On a tree the answer is just the node's depth.

(a) 0:3, 1:9, 2:20, 3:null, 4:null, 5:15, 6:7.

• 3 (idx0) children idx1,2 = 9,20
• 9 (idx1) children idx3,4 = null,null → leaf
• 20 (idx2) children idx5,6 = 15,7

      3
     / \
    9   20
       /  \
     15    7

(b) Grouped: [[3],[9,20],[15,7]]. (c) Widths per level: 1,2,2 → $w=2$. Max queue size during flat BFS = 2. (d) Nodes present $n=5$. Time $O(n)=O(5)$ (each node enqueued/dequeued once). Space $O(w)=O(2)$.

(a) Bottom level (level $h$) has $2^h$ nodes. (b) The queue peaks holding the whole bottom level, so space $\approx 2^h$. Since $n=2^{h+1}-1$, we get $\frac{2^h}{2^{h+1}-1}=\frac{2^h}{2\cdot 2^h-1}\underset{h\to \infty }{\to }\frac{1}{2}.$ So BFS space is $\approx n/2=O(n)$ in the worst case. (c) $h=3$: $n=2^4-1=15$, bottom level $=2^3=8$. Indeed $8/15\approx 0.533$, close to $\frac{1}{2}$.

A left path: root → child → child → … ($n$ nodes, one per level, so the queue never holds more than 1 waiting element after each step).

• With deque: popleft() is $O(1)$. Total work $=n\cdot O(1)=O(n)$. ✓
• With list.pop(0): each pop(0) shifts all remaining elements → $O(\text{len})$. Even though this path keeps the list short, take instead the complete tree where the queue holds up to $\sim n/2$ nodes: each of the $\sim n/2$ dequeues at the widest level costs up to $O(n/2)$ to shift → summed cost $\Theta (n^2)$.

Concrete count for a complete tree of $15$ nodes: the widest queue state has $8$ elements; the total element-shifts across all pop(0) calls grows quadratically, whereas deque.popleft() performs exactly $15$ constant-time removals. Fix: always use collections.deque + popleft() for BFS queues.