171. Binary Tree Level Order

Why this mechanism works

A FIFO queue already visits nodes in depth order, but grouping requires an explicit boundary. Capture the queue length before processing a level. Children appended during that loop belong to the next level and must wait until the next outer iteration.

State and boundaries

At each outer-loop start the queue contains exactly the next level, left to right. level holds the current layer's emitted values.

Protocol

1. Return [] for None.
2. Enqueue the root.
3. Capture the current queue length.
4. Remove exactly that many nodes, recording values and enqueuing left then right children.
5. Append the completed level.

Visualization

queue [1] -> level [1], next queue [2,3]
capture 2 -> level [2,3], next queue [4,5]
new children wait for the next outer loop

Python implementation

from collections import deque
from structures import build_tree

def level_order(root):
    if root is None:
        return []
    queue, output = deque([root]), []
    while queue:
        level = []
        width = len(queue)
        for _ in range(width):
            node = queue.popleft()
            level.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        output.append(level)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 level_order: if root is None:
root=N1(val=1,left=N2,right=N3)

L7 level_order: queue, output = deque([root]), []
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]

L9 level_order: level = []
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]; level=[]

L10 level_order: width = len(queue)
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]; level=[]; width=1

L11 level_order: for _ in range(width):
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]; level=[]; width=1; _=0

L12 level_order: node = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[]; level=[]; width=1; _=0; node=N1(val=1,left=N2,right=N3)

L13 level_order: level.append(node.val)
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[]; level=[1]; width=1; _=0; node=N1(val=1,left=N2,right=N3)

L15 level_order: queue.append(node.left)
root=N1(val=1,left=N2,right=N3); queue=deque([N2(val=2,left=N4,right=N5)]); output=[]; level=[1]; width=1; _=0; node=N1(val=1,left=N2,right=N3)

... 16 intermediate state changes omitted ...

L11 level_order: for _ in range(width):
root=N1(val=1,left=N2,right=N3); queue=deque([N5(val=5,left=None,right=None)]); output=[[1], [2, 3]]; level=[4]; width=2; _=1; node=N4(val=4,left=None,right=None)

L12 level_order: node = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[[1], [2, 3]]; level=[4]; width=2; _=1; node=N5(val=5,left=None,right=None)

L13 level_order: level.append(node.val)
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[[1], [2, 3]]; level=[4, 5]; width=2; _=1; node=N5(val=5,left=None,right=None)

L18 level_order: output.append(level)
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[[1], [2, 3], [4, 5]]; level=[4, 5]; width=2; _=1; node=N5(val=5,left=None,right=None)

L5 level_order: if root is None:
root=None

Why the solution is correct

Initially the queue is the root level. Processing exactly that prefix emits the whole current level; appending its children in parent order creates the next level in left-to-right order. Induction over depth proves every group correct. Every node enters and leaves once.

Time and space

O(n) time, O(n) output and O(w) queue space, where w is maximum level width.

Common mistakes

Using a changing queue length as the level limit can consume newly appended children in the same group. A list pop(0) adds linear shifting cost.

Reasoning card

Transfer exercise

Return each level's average while keeping only its sum and node count.