Level order (BFS) visits nodes level by level, left to right.
def levelOrder(root):
if not root: return []
result = []
queue = [root]
while queue:
level = []
levelSize = len(queue)
for i in range(levelSize):
node = queue.pop(0)
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.