BFS Level-Order Traversal

Detailed answer

Logic: Use a queue: dequeue node, process, enqueue children. Process level-by-level by tracking queue size per level or recording depth. Complexity notes included in code section when present. Pros: Finds shortest path in unweighted graphs; natural for level-wise aggregation. Cons: O(V+E) memory for queue; DFS uses less memory on deep skinny trees. Core: Use a queue: dequeue node, process, enqueue children. Process level-by-level by tracking queue size per level or recording depth. Real-time example: Org chart: print employees level by level from CEO downward for headcount reports. Pros: Finds shortest path in unweighted graphs; natural for level-wise aggregation. Cons: O(V+E) memory for queue; DFS uses less memory on deep skinny trees. Common mistakes: Pushing null children without check; mixing BFS with recursive stack mindset. Best practices: Use collections.deque; snapshot len(q) for per-level loops. Audience level: Senior.

Full explanation

Use a queue: dequeue node, process, enqueue children. Process level-by-level by tracking queue size per level or recording depth.

Code example

from collections import deque

class Node:
    def __init__(self, val: int, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def level_order(root: Node | None) -> list[list[int]]:
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level, n = [], len(q)
        for _ in range(n):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

Practice code · python (view only · no execution)

from collections import deque

class Node:
    def __init__(self, val: int, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def level_order(root: Node | None) -> list[list[int]]:
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level, n = [], len(q)
        for _ in range(n):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

Follow-up questions

• How would you test BFS Level-Order Traversal?
• What metrics prove BFS Level-Order Traversal is healthy in prod?
• How does BFS Level-Order Traversal change at 10× traffic?