Promote the street robbery to a tree and the same rob-or-skip decision becomes a rule about edges: rob a house and both of its directly-linked neighbors (in this hierarchy, its two children) go off-limits for the night. Two patterns carry the solution. Trees supplies the recursion skeleton — every node owns one small subtree, and a choice made at a node can only constrain the subtree hanging below it. 1-D DP supplies the state — a node matters only through two numbers: the best this subtree can do when the node is robbed and the best when it is skipped. Because the two choices touch disjoint parts of the children, those two numbers can be computed bottom-up and recombined exactly once per node.
Brute Force: Recursion That Re-solves Subtree
Time O(2^n)Space O(h)Transcribe the rule as a plain recursive function. For each node, compute the two options separately: skip it (then both children are free to pick their own best) or rob it (then root.val must be added to the best of the grandchildren, since the children are blocked). Take the max.
class Solution: def rob(self, root: Optional[TreeNode]) -> int: if root is None: return 0 skip_root = self.rob(root.left) + self.rob(root.right) # skip this house rob_root = root.val # rob this house if root.left: rob_root += self.rob(root.left.left) + self.rob(root.left.right) if root.right: rob_root += self.rob(root.right.left) + self.rob(root.right.right) return max(skip_root, rob_root)The two options do not look at the same children: the skip option re-solves the children, the rob option re-solves the grandchildren — and those grandchildren are exactly the subtrees the children’s own branches are already re-solving. Every node is recomputed once for each ancestor that can reach it, and the overlap compounds. The file examples show it immediately: 5–6 nodes already trigger 23 and 29 calls. On a degenerate right-only chain the call count follows a Fibonacci-shaped recurrence — measured at about 1.6^n — so a 30-node chain costs roughly 7 million calls. Bound it loosely by O(2^n); either way it is hopeless for the constraint of up to 10⁴ nodes. Space is just the O(h) recursion depth.
Post-Order Pair DP
OptimalTime O(n)Space O(h)Make every node return two numbers: (skip, rob).
skip— best money in this subtree when the node is not robbed. Then its children are unconstrained, so each contributes its own best:skip = max(left) + max(right).rob— best money when the node is robbed. Then both children must be skipped:rob = node.val + skip(left) + skip(right).
The root’s answer is max(skip(root), rob(root)). A post-order walk computes each node’s pair from its children’s pairs, so every node is touched exactly once — the recursion order does the memoization for free, with no hash map.
class Solution: def rob(self, root: Optional[TreeNode]) -> int: def dfs(node: Optional[TreeNode]) -> tuple[int, int]: if node is None: return (0, 0) # (skip, rob) left = dfs(node.left) right = dfs(node.right) skip = max(left) + max(right) # node skipped: children free rob = node.val + left[0] + right[0] # node robbed: children skipped return (skip, rob) return max(dfs(root))Watch the post-order unwind of the first example ([3,2,3,null,3,null,1]): a leaf gets its pair first, then each parent — the child pairs light up in indigo while they feed the parent’s own (skip, rob) chips.
each card pairs a house value with its (skip, rob) totals — slate chip = this house skipped, amber chip = this house robbed; an indigo ring marks the child pairs feeding the node computed this step
The constraint runs along edges: rob a house and its two children are off-limits. That makes each node face exactly two futures — robbed or skipped — and a choice only constrains the subtree below the node. Two small patterns do the work: Trees gives the recursion skeleton (a node owns one subtree), and 1-D DP supplies the state (two numbers per node). Solve every subtree bottom-up and glue the pairs together once each.
The same sweep on the second example ([3,4,5,1,3,null,1]) — watch the root closely: its skip value beats its rob value, and the pair-DP is what lets the answer ditch the largest house on the tree.
each card pairs a house value with its (skip, rob) totals — slate chip = this house skipped, amber chip = this house robbed; an indigo ring marks the child pairs feeding the node computed this step
Second example, [3, 4, 5, 1, 3, null, 1]. Same post-order sweep, but watch which chip wins at the root — this tree is the case where the big value up top loses. The left subtree unwinds first: the leaves 1 and 3 under node 4.
Correctness (induction): at the leaves, a nil child contributes (0, 0) and a real leaf gets (0, leaf.val) — trivially correct. If both children of a node return correct pairs, the two returns above enumerate the only two feasible behaviors at the node — rob it (children forced to skip) or skip it (children at their best) — so max is best money in the subtree. Inducting bottom-up covers the whole tree, and the root’s max is the answer by the same argument.
Complexity: visiting each of the n nodes once and combining its children’s pairs in O(1) gives O(n) time. The recursion stack is the tree height h, so space is O(h) — worst case O(n) on a degenerate chain. Space is also O(n) per the statement’s bound; either way the difference from the brute force is the difference between one pass and an exponential number of calls.