Passing state & BFS level by level

Trees: DFS & BFS, lesson 2 of 3

Passing state & BFS level by level

Send information down with parameters, bring answers up with returns, and walk a tree row by row.

14 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Information in a tree DFS flows two ways:

  • Up (return values): a node's answer depends on its children. Height, subtree sum, "is this subtree balanced?". Post-order style.
  • Down (parameters): a node's answer depends on its ancestors. Current depth, the sum of the path so far, the allowed value range in a BST. Pre-order style.

Rule of thumb: if the question is about the path from the root, pass it down. If it's about the subtree below, return it up.

Example

Passing state down: root-to-leaf sums

so_far is an int, so each call gets its own copy and nothing needs undoing. If you pass a list (say, the path itself), append before recursing and pop() after, or every branch shares one list.

Walkthrough

path_sums on [5, 4, 8, 11, None, 13, 4]

5so_far 54118134
Step 1 of 6
sums = []

so_far arrives as 0. The root adds its 5 and passes 5 down to each child.

current call
leaf: sum recorded

When the answer isn't what you return. The diameter of a tree is the longest path between any two nodes (counted in edges). The best path may bend at any node: down-left plus down-right. But a parent can only extend a straight downward path.

So the function returns the height (useful to the parent) and records the bent-path candidate in an outer variable (useful to the final answer). This "return one thing, track the best of another" trick solves many hard tree problems.

Example

Diameter: return height, track the best

In the second tree the longest path (5-3-2-4-6) never touches the root. nonlocal best lets the inner function update the outer variable.

Walkthrough

diameter on [1, 2, None, 3, 4, 5, None, None, 6]

1235h=146
Step 1 of 6
best = 0

Post-order: the first call to finish is leaf 5. Both sides are 0, so the path bending here has 0 edges. It returns height 1.

returning now
longest path
Quiz

A node is "good" if no value on the path from the root down to it is bigger than it. What does this print?

Breadth-first search (BFS) visits the tree row by row using a queue (collections.deque, whose popleft() is O(1)). To know where one level ends, snapshot len(queue) at the start of each round: exactly that many nodes belong to the current level, and everything they append belongs to the next.

Reach for BFS when the problem talks about levels, rows, "closest to the root", or what you see from the side.

Example

BFS level by level

Each node enters and leaves the queue once: O(n) time. Between rounds the queue holds exactly one level (mid-round, the end of one and the start of the next), so space is O(w), the tree's maximum width.

Walkthrough

BFS on [3, 9, 20, None, None, 15, 7]

3920157
Step 1 of 6
queue = [3]
level = []
result = []

The queue starts with the root. len(queue) is 1, so round 1 pops exactly 1 node.

just popped
in the queue
done
Quiz

Why does the BFS loop use for _ in range(len(queue)) instead of while queue for the inner loop?

Quiz

You need the minimum depth (the closest leaf to the root) of a huge but shallow-on-one-side tree. Which search can stop earliest?

Exercise

Largest value in each row

Write largest_values(root) that returns a list with the largest value of each level, top to bottom. An empty tree gives [].

[1, 3, 2, 5, 3, None, 9] gives [1, 3, 9]. Values can be negative.