Quick Overview
A queue is what makes BFS level-ordered: children join behind everything already waiting. Recording the queue's length at the start of each round is what separates one level from the next, in `O(N)`.
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.
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.
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] ]
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.Use BFS for shortest path and level-based logic. Next, let's find the Lowest Common Ancestor (LCA)!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.