Binary Tree Level Order Traversal

Problem

Given the root of a binary tree, return its nodes' values grouped by depth: a list whose first element holds the root's value, whose second holds the values at depth 1 from left to right, and so on. Return an empty list for an empty tree.

• The tree has at most 25,000 nodes and may be empty.
• Node values are integers and may repeat.

Examples

• root = [7, 4, 11, 2, None, 9, 15, None, None, None, None, 13] → [[7], [4, 11], [2, 9, 15], [13]]. Depth 2 collects one child of 4 and both children of 11, left to right; 13 is alone at depth 3.
• root = [42] → [[42]]. A single node is a single level.
• root = [] → []. No levels at all.

Hints

1. Which traversal visits all nodes at depth d before any node at depth d + 1?
2. A queue processes nodes in the order they were added. If you know how many nodes are in the queue when a level starts, what does that tell you?
3. BFS with a queue; at the start of each iteration, record len(queue) and pop exactly that many nodes, appending their children for the next round.