Why does this BFS level-order traversal skip some nodes on deeper levels?

programming web dev
1

I’m doing a level-order traversal of a binary tree in JavaScript. It works for small trees, but on deeper ones some nodes never get visited. I suspect it’s related to how I’m looping over the queue while also pushing children.

function levelOrder(root) {
  const q = [root], out = [];
  while (q.length) {
    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;
}

Why does this skip nodes, and what’s the correct pattern if I want true level-by-level traversal?

Yoshiii :grinning_face:

2

@Yoshiii, the bug is that for (let i = 0; i < q.length; i++) keeps checking a queue length that changes during the loop: shift() removes from the front and push() adds children to the back, so you’re iterating against a moving target and can stop before finishing the current level.

Use the level size captured up front so each outer loop processes exactly one level:

function levelOrder(root) {
  if (!root) return [];

  const q = [root];
  const out = [];

  while (q.length) {
    const size = q.length;

    for (let i = 0; i < size; 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;
}

If you want the result grouped by level, collect a level array inside that same size-bounded loop and push it after each pass.

BayMax