0
level #
Return the node values level by level, top to bottom. A breadth-first sweep with a queue does it — the trick is to snapshot the queue size at the start of each level so you know exactly where one row ends and the next begins.
Given a binary tree, return its node values grouped by depth: one inner array per level, ordered top-to-bottom and left-to-right within each level. For the tree [3,9,20,null,null,15,7] (root 3; children 9 and 20; 20's children 15 and 7), the answer is [[3], [9,20], [15,7]]. An empty tree returns [].
levelSize = queue.length before you start dequeuing. Those levelSize nodes are exactly the current level; every child you enqueue while draining them belongs to the next level. Loop exactly levelSize times and you carve the stream into rows.[]. Otherwise put the root in a queue.levelSize = queue.length. This freezes how many nodes are on the current level before any children are added.levelSize times: dequeue a node, push its value into the current level's array, and enqueue its non-null children for later — why: the children form the next level, which we'll process on the following outer iteration.for (k = 0; k < queue.length; k++) with the live queue.length. You mutate the queue inside the loop, so the bound keeps growing and you swallow the next level into the current one. Capture levelSize into a separate variable first.The queue holds at most one full level at a time, so space is O(w) where w is the maximum width — up to n/2 for the bottom row of a full tree, i.e. O(n) worst case. The output itself is O(n).
3. We process the tree breadth-first, one level per outer iteration.[]class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function levelOrder(root: TreeNode | null): number[][] {
const result: number[][] = [];
if (root === null) return result; // empty tree -> []
const queue: TreeNode[] = [root]; // seed with the root
while (queue.length > 0) {
const levelSize = queue.length; // SNAPSHOT this level's width
const level: number[] = [];
for (let k = 0; k < levelSize; k++) { // drain exactly levelSize nodes
const node = queue.shift()!; // dequeue from the front
level.push(node.val);
if (node.left) queue.push(node.left); // children -> next level
if (node.right) queue.push(node.right);
}
result.push(level); // one array per depth
}
return result;
}result immediately. This also keeps the loop logic clean — we never seed a null root.while loop runs once per level of the tree.const levelSize = queue.lengthcaptures the current level's node count before we touch the queue. This single line is what turns flat BFS into a level-grouped traversal.for loop dequeues exactly levelSize nodes. Each contributes its value to level and hands its children to the queue for the next round. Because the bound is the frozen levelSize, the children we just pushed are not consumed here.level array onto result. The queue now contains exactly the next level, so the loop continues until it drains.result.reverse() — or unshift each level.depth parameter and append to result[depth], creating the row on first visit. Same O(n), O(h) stack.queue.shift() performance?" Array shift is O(n); for huge trees use a head index pointer or a deque to keep dequeue O(1).| "return values level by level" | BFS with a queue |
| need per-level grouping | snapshot levelSize = queue.length |
| "right view / zigzag / level average" | same loop, tweak what you keep |
| shortest path in unweighted grid/tree | BFS counts levels = distance |
const result: number[][] = [];
if (!root) return result;
const queue: TreeNode[] = [root];
while (queue.length) {
const levelSize = queue.length; // snapshot!
const level: number[] = [];
for (let k = 0; k < levelSize; k++) {
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;const levelSize = queue.length taken at the top of each outer iteration, before any children are enqueued.