The problem
Return the values of a binary tree level by level: a list of lists, one per level, from the root down. Inside a level, list the values from left to right.
tree [3, 9, 20, None, None, 15, 7] -> [[3], [9, 20], [15, 7]]
tree [1, 2, 3, None, 4, None, 5] -> [[1], [2, 3], [4, 5]]
empty tree -> []
The tests write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. So [3, 9, 20, None, None, 15, 7] is 3 with children 9 and 20, where 20 has children 15 and 7. An empty tree is None.
Limits
- Up to 100,000 nodes.
- The tree can be 5,000 levels deep, so a recursive solution will stop with RecursionError. Use a queue.
Builds on TREE-1 Vocabulary and TREE-2 Traversals.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small tree | Not run | |
| 2 | Empty tree | Not run | |
| 3 | One node | Not run | |
| 4 | The lessons' tree | Not run | |
| 5 | Gaps | Not run | |
| 6 | Leaning left | Not run | |
| 7 | Perfect tree of 15 | Not run | |
| 8 | 5,000 levels | Not run | |
| 9 | 100,000 nodes | Not run |