Tree Breadth-First Search

// Template: BFS with a level-size loop. At the start of each level, the queue holds exactly that level's nodes,
// so snapshot its size and process that many; everything they enqueue belongs to the next level.
export function levelMaxes(root) {
  const result = [];
  const queue = root ? [root] : [];
  let head = 0;                                // queue[head] is the front: no shift(), so dequeue is O(1)
  while (head < queue.length) {
    const size = queue.length - head;          // nodes waiting right now = one full level
    let max = -Infinity;
    for (let i = 0; i < size; i++) {
      const node = queue[head++];
      max = Math.max(max, node.val);           // per-level work goes here: sum, count, first, last…
      if (node.left) queue.push(node.left);    // children line up behind the rest of this level
      if (node.right) queue.push(node.right);
    }
    result.push(max);
  }
  return result;
}

// The same loop with two arrays: build the next level while walking the current one, then swap.
export function levelValues(root) {
  const levels = [];
  let level = root ? [root] : [];
  while (level.length) {
    levels.push(level.map((node) => node.val));
    const next = [];
    for (const node of level) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;
  }
  return levels;
}

// Early exit: BFS meets nodes in order of depth, so the first node that matches is a shallowest one.
// Return as soon as you see it: nothing deeper can beat it, so the rest of the tree is never touched.
export function shallowestDepth(root, matches) {
  const queue = root ? [root] : [];
  let head = 0;
  let depth = 0;
  while (head < queue.length) {
    depth++;
    const size = queue.length - head;
    for (let i = 0; i < size; i++) {
      const node = queue[head++];
      if (matches(node)) return depth;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return -1;                                   // nothing matched
}

export const isLeaf = (node) => node.left === null && node.right === null;

// A queue on top of an array and a head index. push() is O(1) and so is shift() here: it only moves head.
// Array.prototype.shift() moves every remaining element down one slot, so a big BFS that uses it is O(n²).
export class Queue {
  #items = [];
  #head = 0;

  push(item) {
    this.#items.push(item);
  }

  shift() {
    if (this.#head === this.#items.length) return undefined;
    const item = this.#items[this.#head++];
    if (this.#head > 1024 && this.#head * 2 > this.#items.length) {
      this.#items = this.#items.slice(this.#head); // now and then, drop the used prefix to free memory
      this.#head = 0;
    }
    return item;
  }

  get size() {
    return this.#items.length - this.#head;
  }
}