1Understand
The idea
Process the tree level by level with a queue. At the start of each level, the queue holds exactly that level's nodes, so for _ in range(len(queue)) processes one level at a time. Level averages, right-side views and the minimum depth all fall out naturally.
Intuition
Process the tree level by level with a queue. At the start of each level, the queue holds exactly that level's nodes, so for _ in range(len(queue)) processes one level at a time.
Level averages, zigzag order, right-side views and minimum depth all fall out of the same loop. The first time you reach a leaf in BFS is the minimum depth.
Use collections.deque and popleft, never list.pop(0).
What you will be able to do
- Snapshot the level size before iterating
- Use deque
When to use it
- Level-by-level output
- Right side view, zigzag, averages per level
- Minimum depth
2See it
Walkthrough
Level order
Tree [1, 2, 3, 4], queue processes one level at a time.
1 / 4
Seed queue with root. Level size = len(q) at the start of the round.
Live template
Line 1 active
Complexity: time O(n), space O(w)
Time O(n), space O(w) for the widest level. DFS can build levels with a depth argument too, but BFS matches the problem statement more directly and finds shortest root-to-leaf paths naturally.
Read the walkthrough as text
Level order values. Tree: 3 with children 9 and 20, and 20 has 15 and 7.
- Queue starts
[3]. Level size 1 → collect[3]. Enqueue9,20. - Level size 2 → collect
[9, 20]. Enqueue15,7. - Level size 2 → collect
[15, 7]. Queue empty. - Answer
[[3],[9,20],[15,7]].
Right-side view is "last node in each level"; min depth stops at the first leaf.
3Recognise it
Kinds of problems (9)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Level order lists
Example. Return list of levels as lists of values.
How. Snapshot len(q) each round; drain that many nodes into one level list.
Right / left side view
Example. Values visible from the right side.
How. Last node processed in each level (or first for left view).
Zigzag order
Example. Level order alternating left-to-right and right-to-left.
How. Alternate append vs prepend on the level list, or reverse every other level.
Per-level aggregates
Example. Average of values at each depth.
How. Sum and count per level while doing standard BFS rounds.
Minimum depth
Example. Shortest root-to-leaf path length.
How. BFS stops at first leaf, first hit is minimum depth.
Connect next pointers
Example. Populate each node’s next to right neighbour in perfect tree.
How. BFS level order; link previous node in the level to current.
Completeness check (first gap)
Example. Is the tree complete?
How. BFS until you see a null; after that, every node must be a leaf.
Tree as a graph (distance K with parent links)
Example. All nodes distance K from target in a tree.
How. Build parent map, BFS from target up and down through parents/children.
Vertical order (column index)
Example. Column-order traversal with column offsets.
How. BFS with (node, col); sort by col then row, or bucket by column.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Levels mixed
Why it happens. Iterating `while q:` without snapshot mixes nodes from the next level.
How it fails. Children enqueued during iteration inflate `len(q)`, level 2 nodes appear in level 1 output.
Fix. Each level: `for _ in range(len(q)):` process exactly that many nodes.
Empty root
Why it happens. Queue initialised with root even when root is None.
How it fails. root = None but q = deque([root]), you dequeue None and crash on .left.
Fix. If not root: return []; else start with deque([root]).
List as queue
Why it happens. list.pop(0) looks like a queue but shifts the whole array.
How it fails. n nodes: each pop(0) is O(n), BFS becomes O(n²).
Fix. Use collections.deque with popleft() for O(1) pops.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.