Return the level-order (BFS) traversal of a binary tree as a list of lists, one per level.
Use a queue (deque) to process nodes layer by layer. At each step, snapshot the current queue length to know exactly how many nodes belong to the current level, drain those, then enqueue their children. The result is a list of lists without any depth-tracking variable.
How to think about it
Recognise the pattern
The signal is “group by level” or “shortest path in an unweighted graph.” Any time the problem asks you to process nodes level by level — printing them, finding the minimum depth, right-side view — reach for BFS. DFS can work but it needs a depth parameter and extra bookkeeping. BFS is the natural fit because it visits nodes in the exact order they appear level by level.
Build the approach step by step
Brute force / naive DFS would carry a depth parameter and append to result[depth], growing the result list as it recurses. It works in O(n) but the recursive stack can hit O(h) (height), and it does not naturally group nodes by level.
The BFS insight: a queue always holds exactly the nodes at the current frontier. The key trick is reading len(queue) before you start processing, so you know how many nodes belong to the current level. You drain exactly that many, collect their values, then enqueue their children. Repeat until the queue is empty.
Walk through this tree:
1
/ \
2 3
\
4- Start: queue = [1]
- Level 0: snapshot size=1, pop 1 → enqueue 2, 3. level=[1]
- Level 1: snapshot size=2, pop 2 → no children; pop 3 → enqueue 4. level=[2,3]
- Level 2: snapshot size=1, pop 4 → no children. level=[4]
- Queue empty → done. Result: [[1],[2,3],[4]]
Complexity
- Time — O(n): every node is enqueued and dequeued exactly once.
- Space — O(w): the queue holds at most one full level at a time, where w is the maximum width. In the worst case (a complete binary tree’s last level) w = n/2, so O(n).