Q16: Binary Tree Level Order Traversal (BFS)
Perform level-order traversal on a binary tree using a Queue (Breadth-First Search) returning nodes grouped level by level.
BFS Level Order Traversal
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}💡 Queue processes nodes layer by layer. The inner loop iterates
levelSize times to group current level values into a separate output subarray.Key Takeaways
- Breadth-First Search (BFS) processes nodes level by level using a queue.
- Tracks level size (
queue.length) at loop start to process nodes layer by layer.
Knowledge Check
Which data structure is fundamentally required for Breadth-First Search (BFS)?