Level-Order Traversal

How it works, step by step

1. 1

   Put the root into a queue. The queue always holds the nodes waiting to be read.

2. 2

   Before each round, read `queue.length` once and save it as `size`. Exactly that many nodes belong to the current level.

3. 3

   Dequeue `size` nodes one by one. Each dequeued node joins the current level's array.

4. 4

   As you dequeue a node, push its left child, then its right child, to the back of the queue. They belong to the next level, safely behind the frozen count.

5. 5

   After `size` nodes, the level is complete. Push its array into the result and start the next round.

6. 6

   When the queue is empty, every node was read exactly once - O(n) time. The queue held at most one level, up to about n/2 nodes on a bushy tree.

The code, in JavaScript

const node = (val, left = null, right = null) => ({ val, left, right });

// The tree from the animation. Level sizes: 1, 2, 3, 2.
const root = node(3,
  node(9, null, node(12)),
  node(20, node(15, node(10), node(18)), node(7))
);

function levelOrderFlat(root) {
  if (!root) return [];
  const queue = [root];
  const order = [];
  let head = 0;                       // index pointer instead of shift()

  while (head < queue.length) {
    const cur = queue[head++];        // "dequeue" without moving memory
    order.push(cur.val);
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }

  return order;
}

levelOrderFlat(root);
// → [3, 9, 20, 12, 15, 7, 10, 18]

Dry run: reading the tree level by level

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Read `const size = queue.length` before the inner loop. Checking `queue.length` live inside the loop counts the children you just pushed, and levels silently merge into one giant row. This is the number one bug in this problem.
• `array.shift()` is O(n) - it moves every remaining element one slot left. Called n times, it turns the traversal into O(n²). Use an index pointer (`queue[head++]`) on big trees.
• No BST needed. Level order never compares values, so it works on any binary tree. Do not confuse it with in-order, whose sorted-output trick only works on a BST.
• Level order alone cannot serialize a tree: [3, 9, 20] does not say which child is left and which is right, or where a child is missing. To rebuild the shape you must also record the `null` children - that is exactly LeetCode's `[3,9,20,null,null,15,7]` format.

Level-Order Traversal vs. its closest relatives