Level Order Traversal — BFS by Depth

Use a queue (collections.deque) to visit nodes shallow to deep; inner loops can collect each depth level as a batch.

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None

from collections import deque


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

r = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))
print(level_order(r))

Key takeaways

• Process len(queue) nodes per outer iteration for clean levels.
• Width of tree affects memory, not just height.
• Zigzag variants just reverse alternating levels.