Binary Tree Level Order Traversal
Medium· BFS
Problem
Return the node values of a binary tree grouped by depth: a list for the root level, then a list for the next level, and so on, each read left to right.
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Input: root = [1]
Output: [[1]]
Constraints
- • 0 <= number of nodes <= 2000
- • -1000 <= Node.val <= 1000
Hints & approach
Hint 1
Breadth-first search naturally visits nodes in level order.
Hint 2
Before processing a level, record the current queue size; that many pops make up exactly one level.
Approachtry the hints first
Start a queue with the root. While the queue is non-empty, read its current length k, pop k nodes into a list for this level, and push each popped node's non-null children. Append the level list to the result. Snapshotting the size keeps levels from mixing.
Time O(n) · Space O(n)