Binary Tree Level Order Traversal

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

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)

Use BFS with a queue. For each level, process exactly the current queue size.

Invariant: the queue contains nodes for the current 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

• Invariant: the queue contains nodes for the current level.
• The queue holds exactly the current level’s nodes before each level pass.
• Processing size nodes and enqueueing children builds the next level correctly.
• Collected level results therefore match the required traversal.

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.

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.