Trees
BFS for levels
Why it matters
Level grouping drives org-chart views, directory summaries, and shortest-hop searches in unweighted networks. Restarting at the root for each depth repeatedly visits the same upper nodes, and that waste grows with the tree's height. The output must preserve exact level boundaries while visiting every node only once.
Example
Binary Tree Level Order Traversal
Return the level-order traversal: a list of levels, each level left to right.
- Input
- root = [3, 9, 20, None, None, 15, 7]
- Output
- [[3], [9, 20], [15, 7]]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Binary Tree Level Order Traversal
root = [3, 9, 20, None, None, 15, 7]→[[3], [9, 20], [15, 7]]
The baseline, Collect one depth at a time, is O(n · h) · O(h). The better model below keeps this exact input and removes that bottleneck.
For [3, 9, 20, None, None, 15, 7], the brute method revisits 3 for depths 0, 1, and 2. Process queue batches [3], [9, 20], then [15, 7] so each node contributes once.
For [3, 9, 20, None, None, 15, 7], the queue starts as [3]. Save its length, 1; pop 3 into the first row and append 9 and 20. The queue now contains exactly the next row.
Save length 2 before popping 9 and 20, which produces [9, 20] while appending 15 and 7. The next saved length is also 2, producing [15, 7]. Reading the length before adding children keeps the next level out of the current one.
Visual anchor
Binary Tree Level Order Traversal
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.