House Robber III: DP on Trees With a Take and Skip Pair

Dynamic programming is usually taught on arrays: fill a table from left to right and read the answer off the end. A tree has no left and right in that sense, so the question becomes where the table lives. House Robber III is the standard problem for it: houses sit on the nodes of a binary tree, and you may not rob a house together with its direct parent. The answer is a pattern called DP on trees, where each recursive call returns a small bundle of answers instead of one number, and it transfers to a whole family of interview problems.

The problem it solves

Each node holds a non-negative value. Pick a set of nodes with the largest possible total such that no chosen node is the parent of another chosen node. In graph terms, it is a maximum-weight independent set, which is hard on general graphs and easy on trees because a tree has no cycles: every subtree is independent of everything outside it except through one edge, the one to its parent.

The linear version, House Robber on a street, keeps two rolling values while sweeping. On a tree, the sweep order is replaced by the recursion itself: children finish first, then report upward.

The intuition

Ask what a parent needs from a child. If the parent is taken, the child must be skipped, so the parent needs "the best this subtree can do without its root". If the parent is skipped, the child is free, so the parent needs "the best this subtree can do at all". One number cannot answer both questions, so every node returns two:

• take: its own value plus each child's skip value.
• skip: for each child, the larger of that child's take and skip, added up.

The empty tree returns (0, 0). The answer is the larger half of the root's pair. Every node is computed once, from values its children already finished, which is a post-order traversal.

The tempting shortcut is to return one number, "best for this subtree", and compute it as either the node plus its four grandchildren's answers or the two children's answers. It gives the right result, but the grandchildren's answers are recomputed from two directions, so calls multiply. Memoising on the node fixes it; returning the pair makes memoisation unnecessary because nothing is ever asked for twice.

Watch it run

The animation uses the lesson's tree: a worth 3 at the root, b worth 4 and c worth 5 below it, and d and e, each worth 1, under b. There is no left-to-right order to sweep, so each node will hand its parent two numbers. d is a leaf: take it for 1, or skip it for nothing, (1, 0), and e is the same. Take b and its children are off limits, so only their skip halves count: 4 + 0 + 0 = 4. Skip b and each child does what suits it: 1 + 1 = 2. c is a leaf worth (5, 0). Take a: 3 + 2 + 0 = 5, because b and c must both be skipped. Skip a: 4 + 5 = 9. The root's pair is (5, 9), so the answer is 9: skip a, take b and c. Every node was visited exactly once.

The code

The pair version, on the lesson's tree. Missing children return (0, 0), so leaves need no special case:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def rob_pair(node):
    """Returns (take, skip): best total with this node taken, and without it."""
    if node is None:
        return 0, 0
    lt, ls = rob_pair(node.left)
    rt, rs = rob_pair(node.right)
    take = node.val + ls + rs              # taking here forbids both children
    skip = max(lt, ls) + max(rt, rs)       # skipping here frees them
    return take, skip

def rob(root):
    return max(rob_pair(root))

d, e = Node(1), Node(1)
b, c = Node(4, d, e), Node(5)
a = Node(3, b, c)
print(rob_pair(d), rob_pair(b), rob_pair(a))   # (1, 0) (4, 2) (5, 9)
print(rob(a))                                   # 9

The one-number version, with a call counter, on full binary trees of 63, 511 and 4,095 nodes. The pair version makes exactly one call per node plus one per empty child; the naive one multiplies its calls by about 34 every three levels:

calls = 0

def rob_naive(node):
    """One number per node: take it plus the grandchildren, or take the children."""
    global calls
    calls += 1
    if node is None:
        return 0
    take = node.val
    for kid in (node.left, node.right):
        if kid:
            take += rob_naive(kid.left) + rob_naive(kid.right)
    return max(take, rob_naive(node.left) + rob_naive(node.right))

def full_tree(depth):
    return None if depth == 0 else Node(1, full_tree(depth - 1), full_tree(depth - 1))

for depth in (6, 9, 12):
    root, calls = full_tree(depth), 0
    rob_naive(root)
    print(depth, 2 ** depth - 1, calls)
# 6 63 1203
# 9 511 40755
# 12 4095 1381171

A tree can be a path. With 100,000 nodes in a line, the recursive version runs past CPython's default recursion limit of 1,000 frames. An explicit stack does the same post-order walk without the call stack:

import sys
print(sys.getrecursionlimit())              # 1000

def rob_iterative(root):
    """Post-order with an explicit stack: children are finished before parents."""
    pair, stack = {None: (0, 0)}, [(root, False)]
    while stack:
        node, children_done = stack.pop()
        if node is None:
            continue
        if not children_done:
            stack += [(node, True), (node.left, False), (node.right, False)]
            continue
        lt, ls = pair[node.left]
        rt, rs = pair[node.right]
        pair[node] = (node.val + ls + rs, max(lt, ls) + max(rt, rs))
    return max(pair[root])

chain = None
for _ in range(100_000):                    # a 100,000-node path, 1 per house
    chain = Node(1, chain)
try:
    rob(chain)
except RecursionError:
    print("RecursionError")                 # RecursionError
print(rob_iterative(chain))                 # 50000

Checked on 1,500 seeded random trees of up to 11 nodes: both versions must match a brute force that tries every subset of nodes and rejects any subset containing a node together with its parent:

import random

def random_tree(n):
    """n nodes, each new one hung under a random free slot of an earlier node."""
    nodes, parent = [Node(random.randint(0, 20)) for _ in range(n)], {0: None}
    for i in range(1, n):
        while True:
            p, side = random.randrange(i), random.choice(("left", "right"))
            if getattr(nodes[p], side) is None:
                setattr(nodes[p], side, nodes[i])
                parent[i] = p
                break
    return nodes, parent

def rob_brute(nodes, parent):
    best = 0
    for mask in range(1 << len(nodes)):
        chosen = [i for i in range(len(nodes)) if mask >> i & 1]
        if any(parent[i] is not None and mask >> parent[i] & 1 for i in chosen):
            continue                        # a node and its parent: not allowed
        best = max(best, sum(nodes[i].val for i in chosen))
    return best

random.seed(26)
ok = True
for _ in range(1_500):
    nodes, parent = random_tree(random.randint(1, 11))
    ok &= rob(nodes[0]) == rob_iterative(nodes[0]) == rob_brute(nodes, parent)
print(ok)                                   # True

The complexity

• Time: O(n). Each node does constant work per child, and each node is visited once.
• Space: O(h) for the recursion, where h is the height: O(log n) for a balanced tree, O(n) for a path. The iterative version stores a pair per node, O(n).
• Naive one-number recursion: far worse. On full trees it grows by about 3.24 per level, roughly n^1.7, and on a path it grows exponentially, like the Fibonacci numbers.

Where it goes wrong

• Returning one number. The parent needs both answers; with one, you either recompute or get it wrong.
• Adding the children's take values to take. Taking a node forbids its children; only their skip halves may be added.
• Using take alone for skip. A skipped node's child is free, so it gets max(take, skip), not take.
• Memoising on the value. Two nodes can share a value; memoise on the node itself, or better, return the pair.
• Deep trees. Recursion depth equals tree height, and a skewed input hits the recursion limit. Say so, and offer the explicit stack.

When it shows up in interviews

House Robber III is the usual opener, and the same "return a pair or a small tuple" shape solves binary tree diameter, maximum path sum, the minimum number of cameras to cover a tree, and the classic party problem where no employee attends with their direct manager. Interviewers also like the follow-up "which houses did you rob?", answered by walking down from the root and taking a node only when its take value won. The DP section of the Big-O cheat sheet lists the linear house robber next to the other one-dimensional recurrences this one generalises.

How to say it in an interview

"Each node returns two numbers: the best total for its subtree if it is robbed, and if it is not. If I rob it, I add its value to both children's not-robbed values. If I skip it, each child contributes the larger of its two values. An empty child returns zero and zero. I compute these in post-order, so every node is done once: linear time, and height-deep recursion. If the tree could be a long path, I would switch to an explicit stack to stay under the recursion limit."