Level order — BFS

Queue — shallow to deep; batch per level.

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

• len(queue) per level.
• Memory — width.
• Zigzag — alternate reverse.