Binary Tree Level Order Traversal
Binary Tree Level Order Traversal is a medium Trees problem from the Blind 75. The key pattern is breadth-first search, and a good solution runs in O(n) time.
Problem
Return the values of a level-order binary tree grouped by depth.
Examples
Example 1
Input
[7,4,9,null,6]Output
[[7],[4,9],[6]]Example 2
Input
[1]Output
[[1]]Example 3
Input
[5,2,8,null,null,6,9]Output
[[5],[2,8],[6,9]]Approach
Process the tree with a queue, one level at a time, by taking exactly as many nodes as the queue held when the level began.
| Pattern | Breadth-first search |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
Return an empty list for an empty tree.