Tree Recursion
What is this?
Tree recursion normally flows one way: a parent asks its children, children answer, done. Two things break that, and this chapter is both of them.
The first is direction. "Which nodes are exactly k steps from this one?" includes nodes above and sideways, and a downward recursion simply cannot see them. The second is insufficiency: sometimes a child's single best answer is not enough for the parent to decide, because the parent's choice depends on how the child achieved it.
Fun fact: House Robber III shows why a richer return type is a necessity, not a convenience. If each node returns only its best total, a parent cannot tell whether that best came from robbing the child, which would forbid robbing the parent. Returning the pair
(best if I rob this node, best if I skip it)gives the parent everything it needs, and the whole tree is solved in one post-order pass. Returning a single number forces you to recompute grandchildren at every level, which is exponential.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: if the answer lies upward, give the tree parent edges and treat it as a graph. If the parent cannot choose from what a child returns, widen the return type until it can.
1. Parent edges turn a tree into a graph
parent = {root: None}
stack = [root]
while stack: # iterative, so no recursion limit
node = stack.pop()
for child in (node.left, node.right):
if child:
parent[child] = node
stack.append(child)
# now BFS outward from the target, treating parent as a third neighbour
queue, seen, dist = deque([target]), {target}, 0
while queue and dist < k:
for _ in range(len(queue)):
node = queue.popleft()
for nxt in (node.left, node.right, parent[node]):
if nxt and nxt not in seen:
seen.add(nxt); queue.append(nxt)
dist += 1
return [n.val for n in queue]
Two disciplines make it correct. The visited set is mandatory: with parent edges the graph is undirected, so without it BFS walks straight back where it came from. And the queue must be drained one level at a time, because the answer is a distance ring, not a set of reachable nodes. Key the maps by node, not by value, so duplicate values cannot break it.
Node-to-node distance does not need the parent map. The path between two nodes climbs to their lowest common ancestor (the deepest node whose subtree holds both) and then descends, so distance = depth(p) + depth(q) - 2 * depth(LCA).
2. Widen the return type
def rob(node):
if not node: return (0, 0) # (with this node, without it)
L, R = rob(node.left), rob(node.right)
with_node = node.val + L[1] + R[1] # robbing here forbids robbing children
without_node = max(L) + max(R) # skipping here frees the children to choose
return (with_node, without_node)
return max(rob(root))
without_node uses max(L) rather than L[1]: skipping a node does not require skipping its children, it merely permits either. Getting that one line wrong is the standard bug, and it produces answers that are too small rather than obviously broken.
Split BST is the same instinct with a different payload. Each call returns a pair of trees (<= target, > target), and a parent reattaches the halves according to its own value. A node that is <= target takes the returned small half as its right child and passes the big half up. A node that is > target takes the returned big half as its left child and passes the small half up.
3. A 30-second worked example (the pair)
Notice the root's with uses 3 and 1, the children's skipped values, while without is free to take each child's better option. That asymmetry is the entire recurrence.
4. Where you'll actually meet this
- Org charts. "Everyone exactly k reporting steps from this person" includes managers and peers, so it needs upward edges.
- Network topology. Distance queries on tree-shaped networks, where traffic travels both up and down.
- Resource allocation. Choosing non-adjacent nodes to activate (transmitters, sensors, staff) is House Robber III under a different name.
- Range partitioning. Cutting a key-ordered index at a cutoff key is the BST split: two valid trees come back.
- Dependency analysis. "What is within k hops of this change" over a hierarchical structure.
5. Problems in this chapter
All Nodes Distance K in Binary Tree
Every node exactly k edges from a target. Build a parent map keyed by node, then BFS outward level by level with a visited set. The lesson also covers an adjacency-list version and a three-direction DFS.
Pattern: parent map + level-batched BFS. Target: O(n) time, O(n) space.
Find Distance in a Binary Tree
Number of edges between two nodes. Find the LCA (the deepest node that sees both targets) and use depth(p) + depth(q) - 2 * depth(LCA), first in two passes and then in one combined DFS.
Pattern: LCA plus depths. Target: O(n) time, O(h) space.
House Robber III
Maximum sum of non-adjacent nodes. Return (robbed, skipped) per node; the parent combines them. An iterative follow-up covers very deep trees.
Pattern: tuple-returning post-order DP. Target: O(n) time, O(h) space.
Split BST
Split a BST into two valid trees by a target value. Each call returns a pair of subtrees and the parent reattaches them by comparing its own value. An iterative version does it in O(1) extra space.
Pattern: recursion returning a pair of trees. Target: O(h) time, O(h) stack (O(1) iterative).
6. Common pitfalls
- No visited set after adding parent edges. The graph is undirected and BFS immediately walks backwards.
- Draining the queue without level batching, which loses the distance and returns everything reachable.
- Using
L[1]for the skipped case in the robbery recurrence. Skipping a node permits, but does not require, skipping its children, so it must bemax(L). - Returning one number from the robbery recursion, which forces grandchild recomputation and goes exponential.
- Forgetting the target itself is the answer when
k = 0. - Letting an ancestor overwrite the distance in the one-pass distance DFS. The LCA is the deepest node that sees both targets, so record the answer once, at the first node that does.
- Losing the BST invariant in the split by reattaching the wrong half. The returned pair's order matters and must be consistent.
- Recursion depth on a skewed tree of 10⁵ nodes. Mention the iterative alternative (iterative parent-map build, explicit-stack robbery DP, iterative split).
7. Key takeaways
- Parent edges make a tree a graph, and a graph can be walked in any direction.
- Undirected traversal needs a visited set, non-negotiable once parent links exist.
- Batch the queue by level whenever the answer is a distance.
- Widen the return type until the parent can decide.
(robbed, skipped)is the canonical example. - Skipping permits, it does not require. That distinction is one
maxand the whole correctness of the recurrence. - A recursion can return structures, not just values; a pair of trees is a perfectly good return type.
- Both escapes are small changes that are invisible until you need them, so name them out loud when you spot the need.
Order: All Nodes Distance K in Binary Tree → Find Distance in a Binary Tree → House Robber III → Split BST.
All Nodes Distance K in Binary Tree
Core idea: Distance in a tree runs in both directions, but child pointers only go down. So make the tree behave like a graph: one pass records every node's parent, then a BFS from the target follows left, right and parent for
klevels. A visited set stops the search from walking back over the edge it just used. Whatever sits in the queue afterklevels is the answer. Two linear passes, O(n) time and space.
Problem, rephrased
An HR tool models a company as a binary reporting tree: each node is an employee, each edge a direct manager-report link. When an employee's role is under review, the tool must notify everyone exactly k links away, and the effect spreads up through managers as well as down through reports. You get the root, the target node (the employee under review) and an integer k.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson