Overview

Given the root of a binary tree, return its level order traversal — an array of arrays, where each inner array contains the values of nodes at that depth level, from left to right.

Implement levelOrder(root).

Constraints

• Tree nodes have shape { val, left, right }.
• A null root returns an empty array [].
• Each level's nodes are listed left to right.
• Aim for $O(n)$ time and $O(n)$ space.

Examples

//     3
//    / \\
//   9  20
//     /  \\
//    15   7
levelOrder(root);  // [[3], [9, 20], [15, 7]]

//   1
levelOrder(root);  // [[1]]

levelOrder(null);  // []

Notes

• Classic BFS with a queue. For each level, drain all current queue items (one level's worth) and collect their values, then enqueue their children.
• Track the level boundary by recording the queue length at the start of each iteration.
• Can also be solved with DFS by passing depth as a parameter and building the result array by index.

Solution

function levelOrder(root) {
  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;
}

Resources

• Binary Tree Level Order Traversal — LeetCode
• Breadth-First Search — Wikipedia