Binary Tree Level Order Traversal

1. Define the problem

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

Inputroot = [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.

2. Visualize the solution

One cell per node, in level order — values fill in as the queue reaches them

L03

L1—

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.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, in level order — values fill in as the queue reaches them

L03

L1—

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

4. Solution

Solution

solution.tsTypeScript

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)

5. Test cases

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

Binary Tree Level Order Traversal