Question presented to candidate: "Given the root of a binary tree, write a Python function that returns its values level by level — the root's level first, and left to right inside each level — as a list of lists. For example, the tree [3, 9, 20, null, null, 15, 7] should give [[3], [9, 20], [15, 7]]."
What a strong answer should cover:
- Level order is breadth-first search: a FIFO queue, children added left then right.
- How to group by level: snapshot the queue size at the start of each round (or keep each level in its own list).
- O(n) time and O(w) space, where w is the widest level — about n/2 for a perfect tree.
- Python details:
collections.deque.popleft()is O(1) whilelist.pop(0)is O(n);range(len(queue))is evaluated once, so it works as the size snapshot. - The DFS alternative (pre-order with a depth index) and when BFS is preferable (stop early, very deep trees).
- The usual variants: zigzag, bottom-up, level averages, right-side view.
Code / implementation expected: Yes — level_order(root) returning a list of lists, using collections.deque, in Python 3.