Binary Tree Level Order Traversal
Return a binary tree's values level by level with BFS: read the queue size to know how many nodes form the current level, then enqueue their children.
Problem Understanding
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.
Example: root = [3, 9, 20, null, null, 15, 7] returns [[3], [9, 20], [15, 7]].
The Intuition: The Queue Holds One Level at a Time
Breadth-first search already visits a tree level by level; the only work is knowing where each level ends.
- Start with the root in a queue.
- At the top of each pass, the queue contains exactly one level. Read
size = len(queue). - Dequeue
sizenodes, recording their values and enqueuing their children. - Append the recorded list as one row; the queue now holds the next level.
The same loop with one extra step solves Zigzag Level Order (reverse every other row) and Binary Tree Right Side View (keep the last node of each row).
Interactive Walkthrough
The tree numbers each node #n in the order it is dequeued. Beside it are the queue, the level being collected and the finished rows. Try Lopsided to see a level that holds a single node.
Dry Run Table
Input: root = [3, 9, 20, null, null, 15, 7]
| Pass | Queue at start | Size | Row | Queue after |
|---|---|---|---|---|
| 1 | [3] | 1 | [3] | [9, 20] |
| 2 | [9, 20] | 2 | [9, 20] | [15, 7] |
| 3 | [15, 7] | 2 | [15, 7] | [] |
Answer: [[3], [9, 20], [15, 7]].
The Solution Template
BFS with the queue size read at the start of each level.
Binary Tree Level Order Traversal Code
1var levelOrder = function(root) {2 const result = [];3 if (!root) {4 return result;5 }6 const queue = [root];7 let head = 0;8 while (head < queue.length) {9 const size = queue.length - head;10 const level = [];11 for (let i = 0; i < size; i++) {12 const node = queue[head++];13 level.push(node.val);14 if (node.left) {15 queue.push(node.left);16 }17 if (node.right) {18 queue.push(node.right);19 }20 }21 result.push(level);22 }23 return result;24};
Edge Cases & Common Mistakes
- Empty tree: return
[], not[[]]. - Using
len(queue)inside the loop condition: the queue grows while you iterate; read the size once before the inner loop. - Enqueuing null children: skip them, or every level fills up with nulls.
- Using a list as a queue in Python:
list.pop(0)is O(n); usecollections.deque. - Bottom-up variant (LeetCode 107): run the same loop and reverse the result at the end.
Summary
Put the root in a queue. Each pass, read the queue size, dequeue that many nodes into one row, and enqueue their children for the next pass. Append the rows until the queue is empty. O(n) time and O(w) space, where w is the widest level.
More practice: DSA interview questions with answers · patterns cheat sheet