Binary Tree Level Order Traversal (LC 102)

Pattern: BFS - Level-by-Level Processing
Difficulty: Medium
Key Concept: Use a Queue to process all nodes at each depth before moving deeper

Problem Statement

Given a binary tree, return the level-order traversal of its nodes’ values (left to right, level by level).

• Input: TreeNode root
• Output: List<List<Integer>> e.g., [[3], [9, 20], [15, 7]]

---

Clarifying Questions

• Input size: up to 10^4 nodes
• Empty tree: return empty list []
• Return type: List<List<Integer>>

---

Brute Force: DFS with Level Tracking

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) return;
        if (level == result.size()) result.add(new ArrayList<>());
        result.get(level).add(node.val);
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}

---

Optimal: BFS with Queue

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.add(root);

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

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

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }
}

---

Dry Run

Tree:     3
         / \
        9   20
           / \
          15   7

Initial: Queue=[3], Result=[]

Level 0 (levelSize=1):

• Poll 3 → currentLevel=[3]
• Add children: Queue=[9, 20]
• Result: [[3]]

Level 1 (levelSize=2):

• Poll 9 → currentLevel=[9] (no children)
• Poll 20 → currentLevel=[9, 20]
• Add children of 20: Queue=[15, 7]
• Result: [[3], [9, 20]]

Level 2 (levelSize=2):

• Poll 15, 7 → currentLevel=[15, 7]
• No children → Queue=[]
• Result: [[3], [9, 20], [15, 7]]

---

Queue State Visualization

Level 0: | 3 |           ← process, add children
Level 1: | 9 | 20 |      ← process both, add 20's children
Level 2: | 15 | 7 |      ← process both, done

---

Pattern Recognition

• Pattern: BFS Level-by-Level
• Trigger: “Level order”, “average of each level”, “right side view”, “connect siblings”
• Key Trick: Capture queue.size() BEFORE the inner loop to freeze the level boundary

---

Complexity

Metric	Value	Explanation
Time	O(n)	Every node enqueued and dequeued once
Space	O(w)	w = max width; last level of perfect tree has n/2 nodes