102. Binary Tree Level Order Traversal

At a Glance

Topic: Tree
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 102

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

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

Example 2:

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

Example 3:

Input: root = [] Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Approach & Solution Steps

Brute force — O(n²) — repeated depth scans for each level height (terrible).
Better — BFS with sentinel # between levels — O(n) time / O(w) space — works but clunky.
Optimal — O(n) time / O(w) queue space — process queue in chunks: levelSize = len(queue) each outer iteration.

Optimal JS Solution

class TreeNode {
  constructor(val = 0, 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 levelValues = [];
    for (let count = 0; count < levelSize; count++) {
      const node = queue.shift();
      levelValues.push(node.val);
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
    result.push(levelValues);
  }
  return result;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.