Trees

Tree BFS (Level Order)

Process a tree level by level with a queue.

Easy, about 60 minutes to practise.

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

i
1
2
3
4
0123
i → index 0

Seed queue with root. Level size = len(q) at the start of the round.

q = deque([root])

Live template

Line 1 active

1q = deque([root]) if root else deque()
2while q:
3 level = []
4 for _ in range(len(q)):
5 node = q.popleft(); level.append(node.val)
6 if node.left: q.append(node.left)
7 if node.right: q.append(node.right)

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.

  1. Queue starts [3]. Level size 1 → collect [3]. Enqueue 9, 20.
  2. Level size 2 → collect [9, 20]. Enqueue 15, 7.
  3. Level size 2 → collect [15, 7]. Queue empty.
  4. 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.

All lessons