Binary Tree Level Order Traversal

Examples

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Level 0 has just the root (3). Level 1 has its two children (9, 20). Level 2 has 20's two children (15, 7).

Input: root = [1]
Output: [[1]]

A single node is its own entire level.

Input: root = []
Output: []

There are no nodes, so there are no levels at all.

Constraints

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

Approach

Grouping values by level is exactly what breadth-first search (BFS) gives you for free, as long as you know where each level ends. The trick is: right before you start processing a level, check how many nodes are currently sitting in the queue - that number is exactly how many nodes belong to this level (since none of the next level's nodes have been added yet). Process exactly that many, collecting their values and queuing up their children, then move to the next level.

Solutions

Iterative BFS

Use a queue starting with the root. At the start of each loop iteration, note the current queue size - that's how many nodes are in this level. Pop exactly that many, record their values, and enqueue their children for the next round.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function levelOrder(root) {
  if (root === null) 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) — the queue and the result both hold every node's value

Recursive DFS with Level Tracking

Do a normal depth-first traversal, but pass along the current depth as an argument. Use that depth as an index into the result array, creating a new sub-array the first time a depth is reached.

function levelOrder(root) {
  const result = [];

  function dfs(node, depth) {
    if (node === null) return;

    if (result.length === depth) {
      result.push([]);
    }

    result[depth].push(node.val);

    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }

  dfs(root, 0);
  return result;
}

Time: O(n) · Space: O(h) — recursion stack depth, plus O(n) for the result array itself