Binary Tree Level Order Traversal

Why it belongs on this sheet

This is the main BFS template for trees, and it shows up in many variations.

Pattern

Queue by level size

Approach

Push the root into a queue. For each level, process exactly the current queue size, collect those values, and push the next layer of children.

Java solution

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

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

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

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

      for (int i = 0; i < size; 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);
        }
      }

      answer.add(level);
    }

    return answer;
  }
}

Complexity

• Time: O(n)
• Space: O(n)

Interview note

The queue size at the start of the loop is what isolates one level from the next.