Problem Statement

Return the level order traversal of a binary tree’s node values (left to right, level by level).

Why This Problem Matters

• Classic BFS exercise on trees.
• Forms the base for zigzag, right side view, and depth grouping problems.
• Highlights queue-based traversal patterns.

Thought Process

Step-by-Step Reasoning

1. Initialise queue with root if non-null.
2. While queue not empty, capture levelSize = queue.size().
3. Dequeue levelSize nodes, add their values to level list, enqueue children.
4. Append level list to result.

Dry Run

Complexity Analysis

Annotated Solution

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class BinaryTreeLevelOrderTraversal {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
      return result;
    }

    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      int size = queue.size();
      List<Integer> level = new ArrayList<>(size);
      for (int i = 0; i < size; i += 1) {
        TreeNode node = queue.removeFirst();
        level.add(node.val);
        if (node.left != null) {
          queue.addLast(node.left);
        }
        if (node.right != null) {
          queue.addLast(node.right);
        }
      }
      result.add(level);
    }

    return result;
  }

  public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
  }
}

Queue size delineates levels, ensuring nodes at the same depth are grouped together.

Common Pitfalls

• Not isolating level size leads to mixing nodes from different levels.
• Forgetting to enqueue non-null children loses nodes.
• Returning null instead of empty list breaks client code expecting collection.

Follow-Up Questions

• How do you print zigzag order? (Reverse every other level.)
• Can you compute average values per level using same traversal?

Key Takeaways