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: . Space: where is maximum width. For a complete tree, the last level has about nodes, so space is worst case.