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

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.

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.

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. The queue holds at most one level, so space is O(w), the tree's maximum width.

Quiz

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

range() is faster than while

It processes exactly the nodes of the current level; children added meanwhile wait for the next round

It stops the queue from growing too large

deque cannot be used in a while 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?

DFS pre-order

DFS post-order

BFS

In-order

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.