Tree BFS¶
Also known as: Level-Order Traversal, Breadth-First Search, Queue-Based Traversal
Visit the tree in rings — everything at depth 0, then depth 1, and so on — using a queue. The one idea worth internalising: record the queue's size at the top of each round, and that count is the current level, which is how you get level-by-level output from a flat queue.
Before you start¶
What 'solved properly' looks like
Target: O(n) time, O(w) space where w is the tree's maximum width. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You use a queue instead of a stack. Push the root, then repeatedly pop a node, process it, and push its children. The trick for level-by-level output: at the start of each round, the queue's current size tells you exactly how many nodes belong to the current level. Process exactly that many, pushing their children as you go, and the queue now holds only the next level.
Why it matters: Anything phrased as "level," "closest," or "minimum steps" wants BFS. It's also the tree-shaped rehearsal for graph BFS in Stage 9, where the same queue-and-visited pattern handles connectivity and shortest-path problems.
When to reach for it¶
Reach for it when you need to process nodes level by level, find the right side view, compute minimum depth, zigzag order, or find the shallowest node satisfying some condition.
When not to use it
On a wide, bushy tree BFS holds an entire level in memory, which can be far worse than DFS's O(h). Also: if you need full subtree information at each node, DFS is simpler — BFS is for when distance from the root is what matters, not when each node needs its children's answers.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Average of Levels in Binary Tree | LeetCode | Easy | 15 mins | teaching |
| 2 | Minimum Depth of Binary Tree | LeetCode | Easy | 15 mins | teaching |
| 3 | Binary Tree Level Order Traversal | LeetCode | Medium | 20 mins | consolidation |
| 4 | Binary Tree Right Side View | LeetCode | Medium | 20 mins | consolidation |
| 5 | Binary Tree Zigzag Level Order Traversal | LeetCode | Medium | 25 mins | challenge |
Already know this? Test out.
If you can solve Binary Tree Zigzag Level Order Traversal cleanly in one sitting — handling the direction toggle and the level-by-level queue — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.