House Robber III — Solution

Problem

You are robbing houses arranged as a binary tree. Each node holds an amount of money, and you cannot rob a house if you have already robbed its direct parent. Given the root of the tree, return the maximum total you can steal in one night.

[3,2,3,null,3,null,1]

• Input: root = [3, 2, 3, null, 3, null, 1]
• Output: 7
• Explanation: Rob the root (3), skip both children, then rob the two grandchildren (3 and 1) for 3 + 3 + 1 = 7.

Intuition

At every node you have two choices: rob it (locking out your direct children) or skip it (letting each child be considered independently). The key insight is that you only need two numbers per node — the best outcome when robbing it and the best outcome when skipping it — and both can be computed in a single post-order traversal from leaves up to the root, eliminating all redundant work.

Approach 1 — Naive Recursion

At each node, try both choices: rob this house (forcing children to skip) or skip it (leaving children free). Without memoization, overlapping subproblems are recomputed repeatedly — the same subtree is evaluated once from the rob branch and again from the skip branch at every ancestor.

1. If the node is null, return 0.
2. Compute skip: recurse on both children with no parent constraint.
3. If the parent was robbed, we are forced to skip — return skip immediately.
4. Compute take: add the node's value to both children's results when those children must skip.
5. Return the maximum of take and skip.

1class Solution:
2    def rob(self, root: TreeNode) -> int:
3        def dfs(node, parent_robbed):
4            if not node:
5                return 0
6            # Skip this node; children are free to be robbed
7            skip = dfs(node.left, False) + dfs(node.right, False)
8            if parent_robbed:
9                return skip  # forced to skip — no other option
10            # Rob this node; direct children cannot be robbed
11            take = node.val + dfs(node.left, True) + dfs(node.right, True)
12            return max(take, skip)
13
14        return dfs(root, False)

Time: O(2^n) — the same subtree is evaluated from both the rob and skip branches at every ancestor, causing exponential recomputation. Space: O(h) — the call stack depth equals the height of the tree.

Approach 2 — Tree DP (Paired Return)

Instead of passing the parent's decision downward, return a pair from each recursive call — the best value when robbing the node and the best value when skipping it. Both answers come from a single recursive call per child, so every node is processed exactly once.

1. If the node is null, return the pair (rob=0, skip=0).
2. Recurse to get the rob/skip pair from both children.
3. rob_this = node.val + left_skip + right_skip — robbing this node forces both children to be skipped.
4. skip_this = max(left_rob, left_skip) + max(right_rob, right_skip) — skipping this node means each child can independently be robbed or skipped for the best outcome.
5. Return the pair; at the root, return the maximum of both values.

1class Solution:
2    def rob(self, root: TreeNode) -> int:
3        def dfs(node):
4            if not node:
5                return 0, 0  # (rob_value, skip_value)
6            left_rob, left_skip = dfs(node.left)
7            right_rob, right_skip = dfs(node.right)
8            rob_this = node.val + left_skip + right_skip  # skip both children
9            skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)
10            return rob_this, skip_this
11
12        rob_root, skip_root = dfs(root)
13        return max(rob_root, skip_root)

Time: O(n) — each node is visited exactly once in a single post-order traversal. Space: O(h) — the call stack depth equals the tree height (O(log n) balanced, O(n) worst case for a skewed tree).

Complexity Summary

Common Mistakes

• Computing skip_this as left_rob + right_rob: skipping the current node does not obligate you to rob its children; each child independently contributes max(rob, skip), not automatically rob.
• Swapping array indices in the Java solution: result[0] must always be the rob value and result[1] the skip value — returning {skipThis, robThis} and then reading result[0] as rob is a silent error that produces wrong answers on trees deeper than two levels.
• Memoizing Approach 1 on node identity alone: the same node has two distinct answers depending on whether its parent was robbed; a cache keyed only on the node conflates these — you must cache on (node, parentRobbed) pairs to fix the brute force correctly.
• Missing the null base case returning (0, 0): null nodes must contribute zero to both the rob and skip sums; omitting the base case causes a crash before any meaningful computation runs.
• Thinking skipping means you must rob the children: when you skip a node, each child still gets to choose independently between rob and skip — you take the maximum per child, not the rob value blindly.

Related Problems

• house-robber — the same no-adjacent constraint on a linear array; the simpler 1D version to build the core intuition
• house-robber-ii — houses arranged in a circle; adds a boundary condition to the same DP pattern
• binary-tree-maximum-path-sum — post-order traversal that returns a per-node DP value for the parent to use, structurally identical pattern
• path-sum-iii — tree traversal accumulating path sums; another problem that requires threading state bottom-up through the tree
• path-sum — simpler tree traversal to solidify the post-order DFS pattern before tackling DP on trees