Trees · Stage 3 of 3
Level-Order BFS
Visit one level at a time; a queue holds exactly the next level
Foundations
So far, recursion went deep first: one child's whole subtree finished before the other child started. Now, what if you need the tree level by level, every node at depth 1 before any node at depth 2?
A queue gives that order. It is first in, first out: items join at the back and leave from the front, and Python's deque does both in O(1). Breadth-first search, BFS, starts with the root in the queue; each step takes the front node, handles it, and puts its children at the back. A level's children join behind the whole level, so nodes leave in level order.
On the tree read from nums = [7, 1, 5, 3, 6], the queue starts as [7]. Taking 7 adds 1 and 5; taking 1 adds 3 and 6; taking 5, 3, and 6 adds nothing. Nodes leave as 7, 1, 5, 3, 6, the level-order list itself. Reading len(queue) before a level starts tells you how many nodes it has: 1, then 2, then 2.
1: 1 and 5, reached through the root's left and right pointers. Taking each one adds its children at the back.Case Scenario
The problem
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]]
Binary Tree Level Order Traversal returns the values grouped by level, top to bottom and left to right within each level. BFS produces exactly that order, and reading len(queue) at the start of each level marks where one group ends. For root = [3, 9, 20, None, None, 15, 7], the answer is [[3], [9, 20], [15, 7]].
The direct approach collects one depth at a time: for depth 0, 1, 2, and so on, it walks the whole tree from the root and keeps the nodes at that depth. It works, but every level restarts at the root, so upper nodes are visited again and again: O(n · h) visits for a tree of height h.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.