Binary Tree Level Order Traversal

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(W)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Standard FIFO BFS queue: snapshot `qLen = len(q)` at the start of every outer loop iteration so the inner loop consumes strictly one depth level.

2. Complexity Bounds & Proof

Every node is enqueued and dequeued once; queue holds at most the widest level W <= N/2.

3. Minimal Idiomatic Code

def levelOrder(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

4. Failure Modes & Interview Follow-ups

Pitfalls:- Reading `len(q)` dynamically inside the inner loop merges multiple levels together. - Skipping initial `if not root: return []` pushes `None` into the queue.
Follow-ups:- Binary Tree Right Side View appends only the last element `level[-1]` of each BFS batch.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Depth of Binary Tree (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.