Binary Tree Level Order Traversal

Return the level order traversal of a binary tree's nodes' values (from left to right, level by level).

Why this is worth learning

A queue orders nodes by distance from the root. Capturing its current length freezes one level before newly discovered children are added.

Before coding: one-minute experiment

Why must the level loop use a saved size rather than a changing len(queue) while children are appended?

Function signature

func LevelOrder(root *TreeNode) [][]int

Inputs / outputs

• root: root of the tree.
• Return: slice of levels.

Example

    3
   / \
  9  20
     / \
    15  7
Output: [[3],[9,20],[15,7]]

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

A DFS carrying depth can collect nodes into depth-indexed slices. A queue offers another route: finish one depth before expanding the next. Suppose the queue starts [A,B]. Removing A may append its children, so a changing queue length no longer identifies the original depth. Freeze the initial size and remove exactly that many nodes. Appending each left child before its right child preserves left-to-right order in the next frontier. Only the boundary needs extra state; there is no need to attach a depth integer to every queue entry.

Invariant: at the start of each outer iteration, the queue contains exactly the current level. During processing it contains the unprocessed part of that level followed by discovered children for the next level.

Algorithm (step-by-step)

1. If root is nil, return empty.
2. Push root into queue.
3. While queue not empty:
   • Record current size n.
   • Pop n nodes to form one level, pushing their children.
   • Append level list to result.

Correctness sketch

At the start of each outer iteration, the queue contains exactly the next level's nodes in left-to-right order. Freeze that count and remove exactly that many nodes. Appending each node's left child before its right child builds the next level in the same left-to-right order, because all children of an earlier parent precede children of a later parent. The frozen count prevents these new nodes from being consumed as part of the current level. Recording the removed values therefore gives one correct level, and induction processes all depths exactly once.

Trace (hand walkthrough)

Example input:
    3
   / \
  9  20
     / \
    15  7
Output: [[3],[9,20],[15,7]]

Walk:
- level 0 queue [3] -> output [3]
- level 1 queue [9,20] -> output [9,20]
- level 2 queue [15,7] -> output [15,7]

Pitfalls to avoid

• Not capturing the level size before the inner loop (mixes levels).
• Appending children after using a changing queue length.

Debugging lens

Test an empty tree and a sparse tree where parents have different child counts. A complete tree can hide mistakes that happen only at irregular level boundaries.

Complexity

• Time: O(n)
• Extra space: O(n).

Implementation notes (Go)

• Use a slice queue with a head index for O(1) pops.
• Capture the level size before iterating to keep levels separate.

Reconstruction checkpoint

A level starts with queue [A,B]. A is a leaf; B has children C,D. The code runs for i=0; i<len(queue); i++ while removing the front. Which current-level node is skipped, and what invariant repairs the loop?

Return to Binary Tree BFS · Module quiz