Binary Tree Level Order Traversal

1. Problem Summary

You are given the root of a binary tree.
Your task is to return the level order traversal, meaning:

Visit nodes level by level
From left to right within each level
Output should be a list of lists, where each inner list represents one tree level

Example interpretation:

Given tree:

Output:

[
  [3],
  [9,20],
  [15,7]
]

2. Key Insights

Level order traversal is essentially a breadth-first traversal

We must explore the tree breadth-first rather than depth-first.

A queue naturally processes nodes level by level

As we dequeue nodes of one level, we enqueue their children to process next.

Knowing level boundaries is important

We determine the number of nodes in current level using queue size.

Order is guaranteed by insertion order

Left child enqueued before right child ensures left-to-right traversal.

Works for:

empty tree
skewed trees
balanced trees
trees with any values

3. Approach

Breadth-First Search (BFS) using queue

Steps:

If root is null → return empty list.
Initialize a queue and add root.
While queue not empty:
- determine level size: number of nodes currently in queue
- create an empty list for current level
- loop levelSize times:
  - dequeue node
  - add value to level list
  - enqueue left child if exists
  - enqueue right child if exists
- append level list to result
Return result

4. Time and Space Complexity

Time Complexity:

O(N)

Each node processed exactly once.

Space Complexity:

O(N)

Queue holds up to a full level of nodes.

5. Java Solution

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(level);
        }

        return result;
    }
}

6. Dry Run Examples

Example 1

Input:

[3,9,20,null,null,15,7]

Processing:

Level 1: [3]
Level 2: [9,20]
Level 3: [15,7]

Output:

[[3],[9,20],[15,7]]

Example 2

Input:

[1]

Only one node → single level

Output:

[[1]]

Example 3

Input:

[]

Empty tree

Output:

[]

Example 4

Input:

[1,2,3,4,null,null,5]

Tree:

Levels:

[1]
[2,3]
[4,5]

Output:

[[1],[2,3],[4,5]]

Example 5

Input:

[5,4,8,3,null,7,9]

Output:

[[5],[4,8],[3,7,9]]

7. Why This Solution Works

BFS guarantees left-to-right layer traversal
Queue preserves visiting order
Level size tracking correctly isolates each depth
Efficient and minimal complexity
Works universally on any binary tree shape

8. Common Mistakes

Using DFS and expecting natural level grouping
Forgetting to check for null root
Adding child nodes before polling current level fully
Not resetting level list each iteration
Using stack instead of queue