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 is the cleanest demonstration of why a richer return type is not a convenience but a necessity. If each node returns only its best total, a parent cannot tell whether that best came from robbing the child — which would forbid robbing itself. 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.

The one-line 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 = {}
def annotate(node, par=None):
    if not node: return
    parent[node] = par
    annotate(node.left, node); annotate(node.right, node)
annotate(root)

# 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.

The same annotation solves node-to-node distance: BFS from one node until the other is found, and the level count is the distance.

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.

3. A 30-second worked example (the pair)

        3
       / \
      2   3
       \    \
        3    1

leaves:  3 (left branch) → (3, 0)
          1              → (1, 0)
node 2:  with    = 2 + 0        = 2
         without = max(3, 0)    = 3        → (2, 3)
node 3(r): with  = 3 + 0        = 3
           without = max(1, 0)  = 1        → (3, 1)
root 3:  with    = 3 + 3 + 1    = 7   ✅   ← uses each child's "without"
         without = max(2,3) + max(3,1) = 3 + 3 = 6
                                     answer = max(7, 6) = 7

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 and social hierarchies. "Everyone exactly k reporting steps away" needs upward edges, which is why real implementations build a parent index.
• 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 tree robbery under a different name.
• Database partitioning. Splitting an ordered index by key value is the BST split, returning two valid trees.
• Dependency analysis. Blast-radius queries — what is within k hops of this change — over hierarchical structures.

5. Problems in this chapter

▶ All Nodes Distance K in Binary Tree

Every node exactly k edges from a target. Build a parent map, then BFS outward level by level with a visited set.
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. The same annotation, then BFS from one until the other appears — or find the LCA and add the two depths.
Pattern: parent map + BFS, or LCA. Target: O(n) time.

▶ House Robber III

Maximum sum of non-adjacent nodes. Return (robbed, skipped) per node; the parent combines them.
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.
Pattern: recursion returning a pair of trees. Target: O(h) time.

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 — it must be max(L).
• Returning one number from the robbery recursion, which forces grandchild recomputation and goes exponential.
• Forgetting the root itself can be at distance 0 when k = 0.
• 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.

7. Key takeaways

1. Parent edges make a tree a graph, and a graph can be walked in any direction.
2. Undirected traversal needs a visited set — non-negotiable once parent links exist.
3. Batch the queue by level whenever the answer is a distance.
4. Widen the return type until the parent can decide. (robbed, skipped) is the canonical example.
5. Skipping permits, it does not require. That distinction is one max and the whole correctness of the recurrence.
6. A recursion can return structures, not just values — a pair of trees is a perfectly good return type.
7. Why interviewers like it: both escapes are small changes that are invisible until you need them, and neither can be pattern-matched from the easier tiers.

Order: All Nodes Distance K in Binary Tree → Find Distance in a Binary Tree → House Robber III → Split BST.