</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Tree recursion: parent map plus BFS, or return a tuple

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)

House Robber III pair example: answer max(7,6) equals 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 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 be max(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

  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. 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 k levels. A visited set stops the search from walking back over the edge it just used. Whatever sits in the queue after k levels 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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.