Binary Tree Level Order Traversal
Given the root of a binary tree, return the values of its nodes grouped by level, from top to bottom, left to right within each level. Use breadth-first search with a queue : measure how many nodes belong to the current level before dequeueing any of them, so children never get mixed into the level that produced them.
Constraints
- The number of nodes in the tree is in the range [0, 2000]
- -1000 ≤ Node.val ≤ 1000
Example
Input
root = [3, 9, 20, null, null, 15, 7]Output
[[3], [9, 20], [15, 7]]Explanation Level 0 is the root, level 1 holds 9 and 20, level 2 holds 15 and 7.
One cell per node, in level order — values fill in as the queue reaches them
L03
L1—
L1—
L2—
L2—
Statuslevel 0
Queue starts with the root. Level 0 = [3].
What happens in this step
queue = [3] levelSize = queue.length = 1 Dequeue 3, push its value onto this level's list, enqueue its children. level = [3] → result = [[3]]
Step 1 of 4
Steps to visualize
- The row has one slot for each of the tree's five nodes, top to bottom, left to right. A slot shows — until the queue reaches that node.
- Start a queue holding just the root.
- Before dequeueing anything, note the current queue size — that many nodes make up this level.
- Dequeue exactly that many nodes, collecting their values into this level's list and enqueueing their children.
- Push the finished level list onto the result.
- Repeat until the queue is empty.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
L03
L1—
L1—
L2—
L2—
Statuslevel 0
Queue starts with the root. Level 0 = [3].
What happens in this step
queue = [3] levelSize = queue.length = 1 Dequeue 3, push its value onto this level's list, enqueue its children. level = [3] → result = [[3]]
Step 1 of 4
Solution
function levelOrder(values) {
function buildTree(vals) {
if (vals.length === 0 || vals[0] === null) return null;
const root = { val: vals[0], left: null, right: null };
const queue = [root];
let i = 1;
while (queue.length > 0 && i < vals.length) {
const node = queue.shift();
if (i < vals.length) {
const leftVal = vals[i++];
if (leftVal !== null) {
node.left = { val: leftVal, left: null, right: null };
queue.push(node.left);
}
}
if (i < vals.length) {
const rightVal = vals[i++];
if (rightVal !== null) {
node.right = { val: rightVal, left: null, right: null };
queue.push(node.right);
}
}
}
return root;
}
const root = buildTree(values);
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
root = [3, 9, 20, null, null, 15, 7] | [[3], [9, 20], [15, 7]] | example from the docstring |
root = [] | [] | empty tree edge case |
root = [1] | [[1]] | smallest valid input, a single node |
root = [1, 2, null, 3, null] | [[1], [2], [3]] | left-skewed chain, one node per level |
root = [1, 2, 3, 4, 5, 6, 7] | [[1], [2, 3], [4, 5, 6, 7]] | balanced full tree, every level completely filled |
root = [1, 2, 3, null, 4, null, 5] | [[1], [2, 3], [4, 5]] | missing children partway through the tree |
root = [-1, -2, -3] | [[-1], [-2, -3]] | negative node values |