Level-Order Traversal (BFS) using Queues

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Level-by-Level Exploration

While DFS dives deep along tree branches, Breadth-First Search (BFS) visits all nodes at depth $0$, then all nodes at depth $1$, then depth $2$, level-by-level.

2. Why Queues Power BFS

A FIFO queue naturally preserves the level-order sequence: when a node is dequeued, its left and right children are enqueued at the back for the next level.

3. Level-Order Traversal Implementation

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

  const result = [];
  const queue = [root]; // Initialize queue with root node

  while (queue.length > 0) {
    const levelSize = queue.length; // Number of nodes in current level
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // Dequeue front node
      currentLevel.push(node.val);

      if (node.left) queue.push(node.left);   // Enqueue left child
      if (node.right) queue.push(node.right); // Enqueue right child
    }

    result.push(currentLevel);
  }

  return result;
}

// Example Tree:
//        3
//       / //      9  20
//        /  //       15   7
// Output: [ [3], [9, 20], [15, 7] ]

4. Applications of BFS on Trees

• Shortest Distance / Minimum Depth: BFS finds the shortest path to a leaf node first.
• Zigzag Level Order: Alternate pushing left-to-right and right-to-left.
• Tree Serialization: Encoding hierarchical trees for network transmission.

5. Common Mistakes

• Dynamic Queue Length Bug: Writing for (let i = 0; i < queue.length; i++) inside the while loop causes a bug because queue.length changes as children are pushed! Always capture const levelSize = queue.length BEFORE the level loop.

6. Next Steps

Use BFS for shortest path and level-based logic. Next, let's find the Lowest Common Ancestor (LCA)!