Binary Tree Level Order Traversal
The Prompt
Given the `root` of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Understanding the Problem
Level order means reading the tree like lines of text: the root first, then all depth-1 nodes left to right, then all depth-2 nodes, each level grouped into its own list.
DFS naturally dives deep before wide, so the natural fit here is BFS with a queue. The one twist over plain BFS: snapshot the queue size at the start of each round — exactly that many nodes belong to the current level — so you know where one level ends and the next begins.
The Interview Flow
Interviewer
How would you perform a level order traversal of a binary tree?
Candidate
Level order traversal implies a Breadth-First Search (BFS) approach. A queue is the perfect data structure for this.
Interviewer
Can you walk me through the process?
Candidate
Sure. I'd initialize a queue and add the root node to it. I'll also have a main result list. I'll loop as long as the queue is not empty. Inside this loop, I'll process one level at a time.
Interviewer
How do you ensure you only process one level per iteration?
Candidate
Before starting to dequeue nodes for the current level, I'll get the current size of the queue. Let's say it's `levelSize`. Then I'll run a for-loop `levelSize` times. In each iteration of this inner loop, I dequeue a node, add its value to a temporary list for the current level, and then enqueue its left and right children if they exist. After the inner loop finishes, I'll have processed all nodes for that level, so I add the temporary list to my main result list.
Interviewer
That's a very clear and correct algorithm. It perfectly separates the levels. Please implement it.
Why does the queue-size snapshot separate levels?
The invariant: at the moment a round begins, the queue contains exactly the nodes of one level, in left-to-right order. Dequeuing that snapshot count emits the level, and every child enqueued during the round has depth exactly one greater — so when the round ends, the invariant holds again for the next level. FIFO order preserves left-to-right within each level.
Every node is enqueued and dequeued once: O(n) time. The queue holds at most one level at a time, up to O(n) nodes for the widest level (roughly n/2 in a full tree).
Iterative BFS using a Queue
- Handle the edge case: if `root` is null, return an empty list.
- Initialize a queue and add the `root` node.
- Initialize a `result` list to store the lists of node values for each level.
- Start a `while` loop that runs as long as the queue is not empty.
- Inside the loop, get the current size of the queue, `levelSize`.
- Initialize a `currentLevel` list to store the values for the current level.
- Start a `for` loop that runs `levelSize` times.
- Dequeue a node from the front of the queue.
- Add the node's value to the `currentLevel` list.
- If the node has a left child, enqueue it.
- If the node has a right child, enqueue it.
- After the `for` loop, add the `currentLevel` list to the `result` list.
- After the `while` loop, return the `result` list.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function levelOrder(root) {
if (!root) return [];
const queue = [root];
const result = [];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}Explanation
Traverse [3, 9, 20, null, null, 15, 7] level by level — one queue round per output row.
1Queue = [3], size snapshot 1. Dequeue 3, emit level [3], and enqueue its children 9 and 20. Output so far: [[3]].
2Queue = [9, 20], snapshot 2. Dequeue both in FIFO order — 9 has no children; 20 enqueues 15 and 7. Output: [[3], [9, 20]].
3Queue = [15, 7], snapshot 2. Both are leaves, so nothing new is enqueued. Output: [[3], [9, 20], [15, 7]] — the queue is empty, traversal complete.
Complexity Analysis
TIME
O(n)
SPACE
O(w)
Finished working through this one?
Mark it complete to track it on your Data Structures path.