Binary Tree Level Order Traversal
Problem
root of a binary tree, return its node values grouped
level by level: one list per depth, starting at the root, with each level read
from left to right.[3,9,20,null,null,15,7]Output[[3],[9,20],[15,7]][1]Output[[1]][]Output[]0 ≤ nodes ≤ 2000 · -1000 ≤ Node.val ≤ 1000
Try it yourself
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
}
}
queue.size() at the start of each round — that many polls is
precisely one level, while the children you enqueue form the next one.Instinct The answer talks about levels, rows, depth order, "closest to the root" or what you see from a side? Queue the tree and process it one level at a time.
Memory hack Freeze the size, drain the row - read n = queue.size() before the loop and one level never bleeds into the next.
Open the Tree BFS (Level Order) guide →Approaches
Brute ForceHeight + DFS per Level
O(n · h)Space O(h)Compute the height h, then for every depth d run a
fresh DFS that only records nodes exactly d edges below the root
(left before right, so order is correct). Upper levels are re-walked for every
deeper level.
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); int h = height(root); for (int d = 0; d < h; d++) { List<Integer> level = new ArrayList<>(); collect(root, d, level); res.add(level); } return res; } private int height(TreeNode node) { return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right)); } private void collect(TreeNode node, int d, List<Integer> level) { if (node == null) return; if (d == 0) { level.add(node.val); return; } collect(node.left, d - 1, level); collect(node.right, d - 1, level); }
Simple, but a skewed tree (h = n) makes it O(n²).
BetterSingle DFS with Depth Index
O(n)Space O(h)One pre-order DFS that carries the current depth. The first
time a depth is reached, open a new list; then append the value to
res.get(depth). Left is visited before right, so each level fills
left-to-right even though levels are filled interleaved.
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); dfs(root, 0, res); return res; } private void dfs(TreeNode node, int depth, List<List<Integer>> res) { if (node == null) return; if (depth == res.size()) res.add(new ArrayList<>()); // first visit of this depth res.get(depth).add(node.val); dfs(node.left, depth + 1, res); dfs(node.right, depth + 1, res); }
Linear and compact, but relies on recursion and doesn't “think” in levels.
OptimalBFS with Queue (Level-Size Snapshot)
O(n)Space O(w)Iterative BFS: each node is enqueued and polled once. Reading
size before the inner loop separates the levels, so each output
list is built in one go. Space is the widest level w (≤ n/2 + 1).
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); // nodes in the current level List<Integer> level = new ArrayList<>(size); 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); } res.add(level); } return res; }
Linear, iterative (no recursion depth risk) and the template for every level-order variant.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Height + DFS per Level | O(n · h) | O(h) |
| Better | Single DFS with Depth Index | O(n) | O(h) |
| Optimal | BFS with Queue (Level-Size Snapshot) | O(n) | O(w) |
- Using
queue.size()as the loop bound while adding children — snapshot it first. - Forgetting the
root == nullcase → NPE on the first poll. ArrayDequerejectsnull— never enqueue missing children.
- Name it: “level order = BFS with a queue”, then explain the size snapshot.
- Mention the DFS-with-depth alternative and its O(h) vs O(w) space trade-off.
- Walk through the example tree, showing the queue contents after each level.