Free lesson · DSA Mastery - Interview Prep, End to End

House Robber III

Hard7 min readdsadynamic-programming

House Robber III

House Robber III is the canonical state-augmented tree DP: given a binary tree where each node has a value (the "loot"), maximize the total looted across selected nodes, subject to the constraint that no two adjacent nodes (parent-child) can both be robbed. The DP defines dp[node] = (robValue, notRobValue) where robValue = max loot with this node robbed (and both children NOT robbed), notRobValue = max loot without this node robbed (children free to choose). Transition: robValue = node.val + child.notRobValue (each child), notRobValue = sum over children of max(child.robValue, child.notRobValue). It's House Robber (the 1-D sub-group's 30.5 problem) lifted to trees - same include/exclude logic, applied via post-order traversal. We present the state-augmented post-order DP (canonical).

The insight: at each node, two decisions are available - rob (take the value, but constrain children) or not-rob (skip, children free). The DP returns both possibilities to the parent, which combines them under its own decision. Returning a pair of values (one per state) is the cleanest way to encode the two-state DP without explicit per-node memoization.

The Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

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

       3
      / \
     2   3
      \   \
       3   1

Output: 7

Explanation: Maximum amount = 3 + 3 + 1 = 7 (rob root 3, leaf 3 under left's right, leaf 1 under right's right).

Example 2:

Input:  root = [3,4,5,1,3,null,1]

       3
      / \
     4   5
    / \   \
   1   3   1

Output: 9

Explanation: Maximum = 4 + 5 = 9 (rob left child 4 and right child 5, skip root).

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	State-augmented post-order DP (return pair)	O(n)	O(h) recursion	Canonical

For each node, return (rob, notRob):

rob = node.val + leftChild.notRob + rightChild.notRob - robbing this node requires both children not robbed.
notRob = max(leftChild.rob, leftChild.notRob) + max(rightChild.rob, rightChild.notRob) - skipping this node leaves children free.

Recurse post-order; the answer is max(root.rob, root.notRob). Time O(n) (each node visited once), space O(h) for the recursion stack (h = tree height).

Approach: State-Augmented Post-Order DP - Canonical

The Idea

Return a pair from each recursive call: the maximum loot under "rob this node" and "don't rob this node" assumptions. The parent combines its children's pairs according to its own choice. The constraint "no two adjacent robbed" is encoded by reading only the notRob value of children in the rob branch.

Logic Flowchart

graph TD
    A["robHelper(node):"] --> B{"node == null?"}
    B -->|Yes| C["return (0, 0)"]
    B -->|No| D["(leftRob, leftNot) = robHelper(left)"]
    D --> E["(rightRob, rightNot) = robHelper(right)"]
    E --> F["rob = node.val + leftNot + rightNot"]
    F --> G["notRob = max(leftRob, leftNot) + max(rightRob, rightNot)"]
    G --> H["return (rob, notRob)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows House Robber III: post-order recursion returning a (rob, notRob) pair per node, where the rob branch reads only the notRob values of children and the notRob branch maxes over both child states.

Code

public static int rob(TreeNode root) {
    int[] result = robHelper(root);
    return Math.max(result[0], result[1]);
}

private static int[] robHelper(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = robHelper(node.left);
    int[] right = robHelper(node.right);
    int rob = node.val + left[1] + right[1];                                // children must not be robbed
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // free choice
    return new int[]{rob, notRob};
}

// TreeNode definition assumed: class TreeNode { int val; TreeNode left, right; }
// Usage:
// rob(buildTree([3,2,3,null,3,null,1])) -> 7
// rob(buildTree([3,4,5,1,3,null,1])) -> 9

This Java code computes the max loot in House Robber III with a post-order traversal returning a (rob, notRob) pair per node, taking the max of the two at the root.

Step-by-Step Walkthrough

Tracing on Example 2 ([3,4,5,1,3,null,1]):

graph LR
    F0["leaves: dp(1) = (1, 0); dp(3) = (3, 0); dp(1) = (1, 0)"]
    F1["left child (4): rob = 4 + 0 + 0 = 4; notRob = max(1,0) + max(3,0) = 1 + 3 = 4; dp = (4, 4)"]
    F2["right child (5): rob = 5 + 0 + 0 = 5; notRob = 0 + max(1,0) = 1; dp = (5, 1)"]
    F3["root (3): rob = 3 + 4 + 1 = 8; notRob = max(4,4) + max(5,1) = 4 + 5 = 9; answer = max(8, 9) = 9"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough computes the max loot for Example two: skipping the root and robbing both children gives nine, which beats robbing the root and the grandchildren.

Result: 9.

Complexity

Time: O(n) - each node visited once. Space: O(h) recursion stack where h is tree height; O(n) worst case for a skewed tree.

Complexity Comparison

Approach	Time	Space	Key Idea
State-augmented post-order DP	O(n)	O(h)	per-node (rob, notRob) pair; constraint encoded by reading only notRob in the rob branch

The state-augmented DP is the canonical solution. The pair return cleanly encodes the two states; the recurrence enforces the no-adjacent constraint by selective reads.

Variations & Follow-ups

How does this generalize House Robber (1-D)?

The 1-D House Robber (30.5 in the 1-D DP sub-group) had a similar two-state recurrence: at each house, dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - either skip or take. The state was implicit (whether the previous house was robbed) because the linear ordering made the constraint trivial: "don't rob this if the previous was robbed." Tree DP makes the state explicit because trees have multiple children, and the constraint must be enforced separately for each. The pair return (rob, notRob) per node is the tree analog of "two adjacent dp values" in 1-D. The general principle: include/exclude tree DPs return a pair of values per node, with the constraint enforced via which child state is read in each branch.

Why post-order rather than pre-order or BFS?

The recurrence reads from children, so children must be computed first. Post-order (DFS) naturally achieves this: recurse into children, then combine for the parent. Pre-order (parent first) doesn't work because the parent's DP depends on its children. BFS would require a separate layer for combining. The general lesson: tree DP fill order is post-order - children before parent - unless the problem is naturally a "spread information from root" type, where pre-order can work. Most tree DPs are post-order.

What if the tree had K children instead of 2?

The same recurrence generalizes:

rob = node.val + sum over children of child.notRob
notRob = sum over children of max(child.rob, child.notRob)

The K-child case has the same O(n) total complexity. The general principle: binary tree DPs extend to N-ary tree DPs by iterating over children instead of hardcoding left, right. Most LeetCode problems use binary trees, but the technique is general.

What about iterative DP via explicit stack?

For trees with very deep recursion (skewed tree, height ≈ n = 10⁴), the JVM's default stack might overflow. An iterative DP using an explicit stack avoids this: do post-order traversal iteratively, maintaining a map from node to its (rob, notRob) pair. More code, but no stack-overflow risk. For LeetCode's constraints, recursion typically works; production code on deep trees may need the iterative form.

How does this preview Binary Tree Cameras (30.71)?

Binary Tree Cameras (30.71) uses a three-state tree DP - each node is in one of three states (has-camera, covered-by-child, uncovered). The recurrence is more complex (parent's state depends on children's states under multiple cases), but the framework is the same: state-augmented post-order DP returning a tuple per node. House Robber III's two-state version is the gentle introduction; Binary Tree Cameras is the harder application. The general lesson: state-augmented tree DPs scale to richer state spaces by enlarging the per-node tuple; the post-order traversal remains the same.

What about edge cases?

Single node: Just rob it; answer = root.val.
All zeros: Answer is 0 regardless of structure.
Highly unbalanced (skewed) tree: Still O(n) time; O(n) stack space.
Empty tree (null root): Answer 0.

Common Interview Pitfalls

Forgetting notRob includes the option to take child's rob value. notRob = max(child.rob, child.notRob) per child, not just child.notRob.
Mixing up rob and notRob in the read. When this node is robbed, children must be notRob; when this node is not robbed, children are free (max).
Single int return type. A single value can't capture both states; you'd need separate calls or memoization. The pair return is the clean approach.
Returning the pair as a List or Map. Use int[] of size 2 for speed; collections have allocation overhead.

Why This Topic Matters

House Robber III is the canonical state-augmented tree DP. Each node returns a pair of values (rob, notRob) capturing the two local choices; the parent combines its children's pairs according to its own choice, with the constraint enforced by which child state is read. The post-order traversal is the natural fill order. The two-state pair pattern extends to richer state spaces (Binary Tree Cameras with three states) and to N-ary trees. House Robber III is the bridge from 1-D include/exclude DP (House Robber, House Robber II) to tree-structured DP.

The next topic, Unique Binary Search Trees II, is a constructive enumeration problem rather than a traditional optimization DP: given n, generate all structurally unique BSTs with values from 1 to n. The recursive structure: for each choice of root i, all left subtrees come from BSTs of [1..i-1], all right subtrees from BSTs of [i+1..n] - a Cartesian product. The "DP" here is a memoized recursive enumeration. It teaches enumeration via Cartesian product of sub-results and demonstrates that the same DP framework applies to constructive problems where the answer is a list of structures rather than a value.

Back to DSA Mastery - Interview Prep, End to End