Binary Tree Level Order Traversal

Learning goal: Recognize level order traversal as a breadth-first search that preserves the tree's depth structure.

Core idea A binary tree has natural layers: the root is level 0, its children are level 1, and so on. We want one output array per layer, with values appearing from left to right. A queue is ideal because nodes are processed in the same order they are discovered.

Algorithm plan

• Return [] immediately when the root is null.
• Put the root into a queue.
• Repeatedly process one complete level.
• Append each level's collected values to the answer.

Micro-example For [3,9,20,null,null,15,7], begin with queue [3]. The first batch produces [3]; its children prepare the next batch [9,20].

Pitfalls

• Forgetting the empty-tree case.
• Processing a child in the same output batch as its parent.
• Reversing left and right child insertion order.

Recap

• BFS naturally visits nodes by increasing depth.
• The queue controls left-to-right order.
• The key challenge is separating batches into levels.

Learning goal: Understand why snapshotting the queue length separates one tree level from the next.

Core idea At the beginning of a level, the queue contains exactly the nodes belonging to that level. Save this count as levelSize. Dequeue exactly levelSize nodes; while doing so, enqueue their children. Those newly enqueued children belong to the next level and must not be consumed until the next outer-loop iteration.

Algorithm plan

• Set levelSize = queue.length before the inner loop.
• Repeat levelSize times.
• Pop one node and append its value to levelValues.
• Enqueue its non-null left and right children.
• Append levelValues to answer.

Micro-example Queue [9,20] means the next level has two nodes, so levelSize = 2. Even after processing 20 and adding 15 and 7, the loop still stops after two dequeues.

Pitfalls

• Reading queue.length in the inner-loop condition.
• Updating levelSize after children are enqueued.
• Treating the queue's changing size as the current level's size.

Recap

• Snapshot first: levelSize = queue.length.
• Drain exactly that many nodes.
• Children wait in the queue for the next batch.

Learning goal: Translate the level-boundary idea into a complete BFS algorithm.

Core idea The queue contains a frontier of discovered but unprocessed nodes. At each outer iteration, its first levelSize entries are precisely the current depth because every parent was processed during the previous iteration. Processing those entries left to right records the level, while appending children creates the next frontier.

Algorithm plan

if root is null: return []
queue = [root]
answer = []
while queue is not empty:
    levelSize = queue.length
    levelValues = []
    repeat levelSize times:
        node = dequeue()
        append node.value to levelValues
        enqueue node.left if it exists
        enqueue node.right if it exists
    append levelValues to answer
return answer

Micro-example Starting with [3], snapshot 1 and output [3]. Then [9,20] has snapshot 2 and outputs [9,20], while [15,7] waits.

Pitfalls

• Enqueueing null children, which creates meaningless work.
• Omitting the left-before-right order.
• Returning the queue contents instead of grouped levelValues.

Recap

• Outer loop means “one level.”
• Inner loop drains the saved count.
• Each child is enqueued once, giving linear work.

Learning goal: Trace the queue, level size, and output across the complete example.

Core idea Use the tree 3 with children 9 and 20; node 20 has children 15 and 7. The queue shows the frontier, while levelSize records how many nodes belong to the current batch. Every dequeue contributes one value to the current level, and every enqueue prepares future work.

Algorithm plan

• Seed the queue with node 3.
• Snapshot and drain one level at a time.
• Enqueue left children before right children.
• Stop when the queue is empty.

Micro-example [3], size 1 → output [3], enqueue 9,20. [9,20], size 2 → output [9,20], enqueue 15,7. [15,7], size 2 → output [15,7], then finish.

Pitfalls

• Counting nodes after enqueuing children.
• Assuming the queue is always the current level only; it also holds the next frontier.
• Losing left-to-right order by enqueuing right children first.

Recap

• Queue state and levelSize work together.
• The example produces three batches.
• The final answer is [[3],[9,20],[15,7]].

Learning goal: Diagnose the queue-length mistake and handle boundary cases confidently.

Core idea The most important implementation detail is taking the queue-length snapshot before the inner loop. If the inner loop checks the live queue length, newly enqueued children extend the loop and get mixed into their parent's level. The algorithm still visits every node, but the grouping becomes wrong.

Algorithm plan

• Check root == null before seeding the queue.
• Store levelSize = queue.length once per outer iteration.
• Use a counter from 0 through levelSize - 1.
• Add only existing children.
• Preserve left child, then right child order.

Micro-example For queue [9,20], the correct snapshot is 2. After processing 20, children [15,7] may be present, but they must wait for the next outer iteration.

Pitfalls

• Empty tree: return [], not [[]].
• Single node: return [[value]].
• Sparse children: skip null pointers.
• Live-length loop: incorrectly turns multiple levels into one batch.

Recap

• Snapshot before dequeueing.
• Queue growth is expected, not an error.
• Edge cases follow directly from the same invariant.

Learning goal: Explain why queue-based level order traversal runs in linear time and uses linear auxiliary space.

Core idea Every node enters the queue once and leaves it once. The work performed while processing a node is constant aside from examining its two child pointers, so the total time is O(n). The queue can contain an entire level, and the answer itself also stores all n values, giving O(n) space overall.

Algorithm plan

• Count each enqueue and dequeue once.
• Treat child checks as constant work.
• Include the output and queue in the space discussion.
• Report the target bounds as time O(n) and space O(n).

Micro-example For five nodes, five nodes are dequeued and each has at most two child checks. The answer stores five values grouped into three arrays.

Pitfalls

• Calling the space O(1) while ignoring the queue and output.
• Confusing tree height with the number of stored nodes.
• Claiming O(n^2) because there is a nested loop; the inner work is partitioned across nodes.

Recap

• Time: O(n).
• Auxiliary queue and output: O(n) space.
• Snapshotting the queue length is the central correctness invariant.