House Robber III — Tree DP with Pair Return (LC 337)

Problem Statement#

LeetCode 337 — House Robber III | Difficulty: Medium

The thief has found a new neighborhood to rob — houses arranged in a binary tree. Each house has a certain amount of money. The thief cannot rob two directly connected houses (parent-child edge). Return the maximum amount of money the thief can rob without triggering alarms.

Constraints:

• The number of nodes is in the range [1, 10^4]
• 0 <= Node.val <= 10^4

Input:  root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Rob node 3 (root) + 3 (right-left) + 1 (right-right) = 7

Input:  root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Rob node 4 + 5 = 9 (skipping root 3)

Why This Problem Matters#

House Robber III is the tree variant of the classic House Robber DP problem (LC 198) and is a staple at Amazon and Microsoft interviews. It tests whether you can generalize linear DP to tree structures — a critical skill for problems involving recursive substructure on trees.

The naive approach (memoized recursion with a hashmap) is O(n) but uses O(n) extra space. The optimal approach returns a pair from each recursive call and avoids any memoization overhead. This pair-return pattern is fundamental to tree DP: instead of recomputing "what if we rob/skip this node," you return both answers simultaneously as you unwind the recursion.

This pattern appears in LC 968 (Binary Tree Cameras), LC 979 (Distribute Coins), LC 543 (Diameter of Binary Tree), and many other tree DP problems.

The Core Insight#

For any node, there are exactly two choices:

1. Rob this node: Cannot rob its children. Gain = node.val + skip_left + skip_right
2. Skip this node: Children can be robbed or not — take the best of each. Gain = max(rob_left, skip_left) + max(rob_right, skip_right)

Each recursive call returns a pair (rob_this, skip_this) for the subtree rooted at that node. The parent combines the children's pairs using the above formulas. No memoization needed — each node is computed exactly once in post-order.

The pair-return technique avoids the classic mistake of calling dfs(node) and dfs(node.child) separately, which causes exponential recomputation.

Visual Dry Run#

Tree: [3, 4, 5, 1, 3, null, 1]

Post-order DFS:

Answer: max(8, 9) = 9.

Solution (Optimal)#

class Solution:
    def rob(self, root) -> int:
        def dfs(node):
            if not node:
                return 0, 0  # (rob_this, skip_this)
 
            rob_left, skip_left = dfs(node.left)
            rob_right, skip_right = dfs(node.right)
 
            # Rob this node: children must be skipped
            rob_this = node.val + skip_left + skip_right
 
            # Skip this node: children can be robbed or not
            skip_this = max(rob_left, skip_left) + max(rob_right, skip_right)
 
            return rob_this, skip_this
 
        return max(dfs(root))

var rob = function(root) {
    function dfs(node) {
        if (!node) return [0, 0];  // [rob_this, skip_this]
 
        const [robLeft, skipLeft] = dfs(node.left);
        const [robRight, skipRight] = dfs(node.right);
 
        const robThis = node.val + skipLeft + skipRight;
        const skipThis = Math.max(robLeft, skipLeft) + Math.max(robRight, skipRight);
 
        return [robThis, skipThis];
    }
 
    return Math.max(...dfs(root));
};

Time: O(n) — each node visited exactly once in post-order Space: O(h) — recursion stack depth equals tree height; O(log n) balanced, O(n) skewed

Common Mistakes#

• Calling dfs(node) and dfs(node.left) separately, leading to O(2^n) recomputation without memoization
• Using a hashmap for memoization when the pair-return approach makes it unnecessary
• Forgetting the base case return 0, 0 for null nodes — every tree recursion needs this
• Taking max(rob_left, rob_right) instead of max(rob_left, skip_left) + max(rob_right, skip_right) when computing skip_this

Interview Tips#

• State "tree DP with pair return" as the approach name — it signals familiarity with the pattern
• Draw the recurrence: rob_this = node.val + skip_left + skip_right and skip_this = max(rob_left, skip_left) + max(rob_right, skip_right) before coding
• Explain why the pair-return avoids memoization — each node is processed exactly once
• Mention the connection to House Robber I (linear) and how the DP state generalizes to trees

Follow-up Questions#

• How does this differ from House Robber I (array)? Array version uses O(n) DP table. Tree version uses pair-return DFS because the tree structure defines the "adjacency" naturally.
• What if the tree can have cycles (a general graph)? You cannot use tree DP. You would need maximum independent set algorithms, which are NP-hard for general graphs.
• How would you reconstruct which nodes were robbed? Track the choice (rob or skip) at each node and backtrack from the root using the stored choices.
• What if multiple parents can share a child (DAG)? Add memoization indexed by node to avoid recomputation in a DAG structure.

Key Takeaways#

• House Robber III uses post-order DFS that returns a pair: (rob this node, skip this node)
• The recurrence: rob_this = node.val + skip_left + skip_right, skip_this = max(rob_left, skip_left) + max(rob_right, skip_right)
• Returning a pair eliminates the need for memoization — each node computed exactly once
• Time is O(n), space is O(h) for the call stack
• The pair-return pattern is fundamental to tree DP: it appears in LC 968, LC 979, LC 543, and many others
• Null nodes return (0, 0) — the base case that seeds all leaf computations
• The final answer is max(rob_root, skip_root) at the top of the recursion