Depth-first recursion visits a tree branch by branch. Breadth-first search (BFS) instead visits it level by level, which is exactly what you need to answer questions like "which nodes are at depth 2?".
Given the root of a binary tree, return its level order traversal: a list of lists, where the i-th inner list contains the values at depth i from left to right.
Examples
3
/ \
9 20
/ \
15 7
Input: root = [3, 9, 20, None, None, 15, 7]
Output: [[3], [9, 20], [15, 7]]
1
/ \
2 3
/ \
4 5
Input: root = [1, 2, 3, 4, None, None, 5]
Output: [[1], [2, 3], [4, 5]]
Input: root = []
Output: []
Constraints
0 <= number of nodes <= 1000
Goals
- Traverse a tree breadth-first with a deque
- Process one level at a time by snapshotting the queue length
- Build a list of lists as output