Binary Tree Level Order Traversal

1. The obvious way

   Compute the depth of every node recursively and bucket by depth: works, but BFS is the natural tool.

2. The key insight

   Put the root in a queue. Repeat: note how many nodes are in the queue right now (that is exactly one level), take that many from the front, record their values, and append their children to the back. Continue until the queue is empty.

3. The algorithm
   1. Queue starts with the root (if any).
   2. Count how many are in the queue now: that is this level's size.
   3. Take that many from the front: record values, add children to the back.
   4. Save the level; repeat until the queue is empty.

Watch it run

levels: [[3]]   queue: 9, 20

from collections import deque

def level_order(root):
    levels = []
    queue = deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):               # exactly one level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.