level-order-traversal.ts

import { TreeNode } from "../lib/tree-node.js";

/**
 * 102. Binary Tree Level Order Traversal  (Medium)
 * Link: https://leetcode.com/problems/binary-tree-level-order-traversal/
 *
 * Return the values of the nodes level by level, from left to right, as an
 * array of arrays (one inner array per depth level).
 *
 * Example:
 *   Input:  [3, 9, 20, null, null, 15, 7]
 *   Output: [[3], [9, 20], [15, 7]]
 *
 * Approach:
 *   Breadth-first search with a queue. Process the tree one level at a time:
 *   capture the current queue size, drain exactly that many nodes into a row
 *   while enqueueing their children for the next level.
 *
 * Time:  O(n)  — every node enqueued/dequeued once.
 * Space: O(n)  — the queue holds up to a full level.
 */
export function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = [];
  if (!root) return result;

  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const row: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      row.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(row);
  }

  return result;
}