Level Order Traversal

Level order (BFS) visits nodes level by level, left to right.

function levelOrder(root):
    if root == null: return []
    result = []
    queue = [root]
    while queue:
        level = []
        levelSize = queue.length
        for i from 0 to levelSize - 1:
            node = queue.dequeue()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

The trick: process exactly levelSize nodes per iteration. This groups output by level.

Time: $O(n)$. Space: $O(w)$ where $w$ is maximum width. For a complete tree, the last level has about $n/2$ nodes, so space is $O(n)$ worst case.