LeetCode 102 · Medium · Trees

Binary Tree Level Order Traversal

Given the root of a binary tree, return its node values level by level, left to right, as a list of lists.

O(n)time
O(w)space · widest level
BFSqueue · size per level

level order as on LeetCode, null = no child · up to 15 nodes, 4 levels · values −99 to 99

Queue ArrayDeque · poll() at the front (left), add() at the back · yellow = the level being read

res one list per level

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> q = new ArrayDeque<>(); if (root != null) { q.add(root); } while (!q.isEmpty()) { List<Integer> level = new ArrayList<>(); int size = q.size(); for (int i = 0; i < size; i++) { // this level only TreeNode node = q.poll(); level.add(node.val); if (node.left != null) { q.add(node.left); } if (node.right != null) { q.add(node.right); } } res.add(level); } return res;}
level #
—
size
—
node
—
level
—
q
[]

Why it works

  1. A queue visits nodes in order of distance from the root: first in, first out, so every node of level d leaves before any node of level d + 1.
  2. Freeze size = q.size() at the start of each level. At that moment the queue holds exactly one level. The children appended during the loop wait for the next pass, so the levels never mix.
  3. Pitfall: writing i < q.size() as the loop condition. The size grows as children are added, so the levels mix; read it once into size. Also avoid an ArrayList with remove(0) as the queue: O(n) per pop, while ArrayDeque.poll() is O(1).
  4. Cost: each node is appended and popped once, O(n) time. The queue holds at most one level plus part of the next: O(w), up to about n/2 for a full tree.
  5. DFS alternative: recurse with the depth and add to res.get(depth). Same output, O(h) stack. The level loop is reused by Right Side View (LeetCode 199), Zigzag Order (103) and Maximum Depth (104).