House Robber III LeetCode 337 Guide

House Robber III (LeetCode 337) places the houses on a binary tree instead of a linear street. Each node in the tree holds an amount of money. The constraint is the same as the original: you cannot rob two directly connected houses — meaning a parent and its child cannot both be robbed on the same night.

The objective is to maximize the total amount robbed. Unlike the array versions, the neighborhood graph is a tree, so the adjacency structure is parent-child relationships rather than consecutive indices. This changes the recurrence significantly and rules out the simple dp[i] = max(dp[i-1], dp[i-2] + nums[i]) approach.

House Robber III extends the House Robber problem family to trees. It is a medium-difficulty tree DP problem that tests your ability to propagate state upward through a recursive structure rather than linearly through an array.

In House Robber I, the classic DP is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). When you rob house i, you look back two steps to dp[i-2]. When you skip it, you carry forward dp[i-1]. The two-step lookback is a direct consequence of the no-adjacent constraint.

On a binary tree, the equivalent of "two steps back" is the grandchildren. If you rob a node, you can only use loot from its grandchildren — its children must be skipped. If you skip a node, its children are free to be either robbed or skipped independently. Naively implementing this by re-traversing subtrees leads to exponential recomputation.

The fix is to return two values per recursive call instead of one. Rather than computing rob(node) and rob(node) separately and calling each subtree twice, you return the pair (rob, skip) from a single DFS pass. This collapses the exponential into a linear O(n) traversal.

The algorithm is a single post-order DFS. Post-order means you process both children before the current node, which is exactly what you need: the current node's rob and skip values depend on the children's rob and skip values.

For each node, call dfs on the left and right children first, receiving a pair from each. Then compute the current node's rob value as node.val + leftSkip + rightSkip — you can only add grandchild loot when robbing this node, so children must be skipped. Compute skip as max(leftRob, leftSkip) + max(rightRob, rightSkip) — when you skip this node, each child independently takes whichever of its rob or skip value is larger.

Return (rob, skip) up to the caller. At the root, the answer is max(rob, skip). Base case: a null node returns (0, 0) — robbing or skipping nothing yields nothing.

When computing the skip value for a node, the formula is max(leftRob, leftSkip) + max(rightRob, rightSkip). A common mistake is to write leftRob + rightRob instead — assuming that if the parent is skipped, both children should be robbed. This is incorrect.

Skipping the parent removes the adjacency constraint between parent and child, but it does not force the children to be robbed. Each child is still adjacent to its own children, and the optimal choice for a child might be to skip it too and rob its grandchildren instead. The max ensures each child independently picks its best outcome.

This independence is the structural reason tree DP differs from naive recursion: neither child's decision affects the other's. They share only the constraint with the parent, which the skip already handles by not adding node.val.

Consider the tree [3, 2, 3, null, 3, null, 1]: root is 3, left child is 2 with a right grandchild of 3, right child is 3 with a right grandchild of 1. This is the canonical example from the LeetCode problem statement.

Starting post-order from the leaves: the lone grandchild nodes (3 and 1) each return (rob=3, skip=0) and (rob=1, skip=0) respectively since they have no children. Their parents (2 and 3) compute: node 2 has no left child and right grandchild 3, so rob=2+0+0=2, skip=max(0,0)+max(3,0)=3 — skip is better. Node 3 (right of root) has no left child and right grandchild 1, so rob=3+0+0=3, skip=max(0,0)+max(1,0)=1.

At the root (value 3): rob = 3 + skip(left) + skip(right) = 3 + 3 + 1 = 7. Skip = max(rob(left), skip(left)) + max(rob(right), skip(right)) = max(2,3) + max(3,1) = 3 + 3 = 6. Answer = max(7, 6) = 7.

In Python, define a nested dfs(node) that returns a tuple (rob, skip). Base case: if not node: return (0, 0). Then left_rob, left_skip = dfs(node.left) and right_rob, right_skip = dfs(node.right). Compute rob = node.val + left_skip + right_skip and skip = max(left_rob, left_skip) + max(right_rob, right_skip). Return (rob, skip). Call rob_root, skip_root = dfs(root) and return max(rob_root, skip_root). Time O(n), space O(h) for the call stack where h is tree height.

In Java, define a private int[] dfs(TreeNode node) returning a two-element array [rob, skip]. Base case: return new int[]{0, 0}. Compute int[] left = dfs(node.left), right = dfs(node.right). Return new int[]{node.val + left[1] + right[1], Math.max(left[0], left[1]) + Math.max(right[0], right[1])}. In the public method: int[] result = dfs(root); return Math.max(result[0], result[1]).

Both solutions run in O(n) time — every node is visited exactly once. Space is O(h) for the recursion stack, where h is the tree height. For a balanced tree that is O(log n), and for a skewed tree (degenerate linked list) it is O(n). No extra data structures are needed.

House Robber I (LeetCode 198) and House Robber II (LeetCode 213) are the linear-array predecessors. Problem 198 is the foundational dp[i] = max(dp[i-1], dp[i-2]+nums[i]) recurrence. Problem 213 extends it to a circular array, requiring two passes. Problem 337 extends the family to trees, where the pair-return technique replaces the linear DP table.

Binary Tree Maximum Path Sum (LeetCode 124) is structurally similar: a post-order DFS where you return a value per node and compute a global maximum at each step. The pattern of propagating upward the best value achievable from a subtree appears in both problems. Diameter of Binary Tree (LeetCode 543) is another member of this family.

The tree DP pattern — post-order traversal returning state per node — covers a wide class of problems: tree diameter, tree DP with multiple states, subtree-rooted optimization. Recognizing that House Robber III fits this pattern, rather than treating it as a memoization problem, is the key insight that leads to the clean O(n) pair-returning solution.