Why does this breadth-first traversal skip some leaf nodes?

[Baymax]

I wrote a BFS to collect values level by level from a binary tree, but some leaf nodes never appear in the result. I suspect I’m mutating the queue incorrectly while iterating. What exactly is wrong here, and what’s the smallest fix?

function bfs(root) {
  const q = [root], out = [];
  for (let i = 0; i < q.length; i++) {
    const node = q.shift();
    out.push(node.val);
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return out;
}

BayMax

[HariSeldon]

Your loop condition is tied to a queue whose length changes in both directions, so i can catch up early after repeated shift() calls.

Hari