House Robber III (LeetCode 337)

The problem

Houses form a binary tree. Each node has a value (the money inside). You cannot rob two houses that are directly connected, that is, a parent and its child. Return the most money you can collect.

Input:  root = [3, 2, 3, null, 3, null, 1]

        3
       / \
      2   3
       \   \
        3   1

Output: 7

Rob the root (3) and the two grandchildren (3 and 1): 3 + 3 + 1 = 7. No robbed pair is parent and child.

How to think about it

Start with brute force. For each node, either rob it or not, and check the “no adjacent” rule. That is 2ⁿ choices. A smarter recursion is best(node) = max(node.val + best of grandchildren, best of children), but it calls each grandchild from two places, and the repeated calls blow up on deep trees.

The key insight: return two numbers per node, not one. The parent needs to know two things about each child: the best total if the child is robbed, and the best if it is skipped. So dfs(node) returns the pair (rob_this, skip_this).

• If you rob this node, both children must be skipped: node.val + left.skip + right.skip.
• If you skip this node, each child is free to do whichever is better: max(left) + max(right).

Now each node is visited exactly once, in a single post-order pass.

Which pattern is this? Tree DP. The tell is an optimisation over a tree where a node’s choice constrains its neighbours: compute a small tuple per node from its children’s tuples.

Approach

1. dfs(None) returns (0, 0): nothing to rob.
2. For a real node, first get l = dfs(node.left) and r = dfs(node.right) (post-order).
3. with_ = node.val + l[1] + r[1]: rob this node, so take the children’s “skip” values.
4. without = max(l) + max(r): skip this node, so each child picks its own best.
5. Return (with_, without). The answer is max(dfs(root)).

Solution

def rob(root):
    def dfs(node):
        if not node: return (0, 0)
        l = dfs(node.left); r = dfs(node.right)
        with_ = node.val + l[1] + r[1]       # rob node: children must be skipped
        without = max(l) + max(r)            # skip node: children choose freely
        return (with_, without)
    return max(dfs(root))
# tree [3,2,3,null,3,null,1] -> rob(root) -> 7

TreeNode is the usual LeetCode class with .val, .left and .right.

Dry run

Post-order on the example tree. Each row shows the pairs from the children and the pair returned.

max(7, 6) is 7: rob the root, skip both children.

Complexity

• Time: O(n). Each node is visited once and does constant work.
• Space: O(h). The recursion stack is as deep as the tree height h: O(log n) for a balanced tree, O(n) for a chain.

Edge cases and pitfalls

• Empty tree returns 0, since max((0, 0)) is 0.
• “Rob every other level” is wrong. Taking all even depths or all odd depths misses mixed choices, such as robbing a left grandchild and a right child.
• The naive grandchildren recursion without memo is exponential. Either memoise on the node or use the pair trick.
• skip does not force the children to be robbed. Use max(l), not l[0], or you miss cases where skipping two levels in a row is best.
• Deep skewed trees can hit Python’s recursion limit; an iterative post-order fixes that.

Related problems

• House Robber (LeetCode 198): the same rob/skip choice on a line instead of a tree.
• House Robber II (LeetCode 213): the circular version.
• Binary Tree Maximum Path Sum (LeetCode 124): another tree DP that returns one value up and tracks another.