#102 Binary Tree Level Order Traversal
frequently reported atBloombergAmazonMicrosoftAppleOracleLinkedIn
the problem
In plain words
Return the node values level by level, left to right, as a list of lists.
in root = [3,9,20,null,null,15,7]
out [[3],[9,20],[15,7]]
in root = [1]
out [[1]]
in root = []
out []
- 0 ≤ number of nodes ≤ 2000
- -1000 ≤ Node.val ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree BFS (level order)
At the start of each round the queue holds exactly one level. Freeze its size, poll that many nodes, and the children you offer form the next level.
solutions
From brute force to optimal
Queue the root; each round polls exactly size nodes into one list.
- If root is null return [].
- Offer root.
- While the queue isn't empty: size = queue.size(); poll size nodes, add values, offer children; add the list.
Each node offered and polled once.
The queue holds one level at a time (plus the output).
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> levels = new ArrayList<>(); if (root == null) return levels; Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); // nodes on THIS 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); } levels.add(level); } return levels; }}Dry run
Preorder DFS carrying the depth; append each value to levels[depth].
- walk(node, depth).
- If depth == levels.size(), open a new list.
- levels[depth].add(val); recurse left then right with depth + 1.
One visit per node.
Recursion stack (plus the output).
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> levels = new ArrayList<>(); walk(root, 0, levels); return levels; } private void walk(TreeNode node, int depth, List<List<Integer>> levels) { if (node == null) return; if (depth == levels.size()) levels.add(new ArrayList<>()); // first visit to this depth levels.get(depth).add(node.val); // preorder keeps left-to-right walk(node.left, depth + 1, levels); walk(node.right, depth + 1, levels); }}in the room
How to say it in the interview
talk track
- Point at the
sizevariable and explain why it can't bequeue.size()inside the loop condition. - Mention the DFS version keeps left-to-right order because preorder visits the left child first.
traps
- Reading
queue.size()in the for-condition — it grows as you offer children, mixing levels. - Offering
nullchildren into anArrayDeque— it throws.
what they ask next
Follow-ups
Zigzag Level Order (LC 103)?
Same BFS; on odd levels add values at the front of a Deque (or reverse the level list).
Level order bottom-up (LC 107)?
Do the normal BFS and reverse the list of levels at the end.
Average of Levels (LC 637)?
Same loop; sum the level into a long and divide by size as a double.
before you submit
Edge cases to test
- Empty tree → [] (and never offer null into an ArrayDeque).
- A chain: every level has exactly one value.
- Gaps: in [1,2,3,4,null,null,5], level 2 is [4,5] even though 4 and 5 are far apart.
practise next
Similar problems
- #103Binary Tree Zigzag Level Order TraversalMediumin Traversals
- #637Average of Levels in Binary TreeEasyin Traversals
- #199Binary Tree Right Side ViewMediumin Traversals