# House Robber III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/house-robber-iii)
Canonical: https://scaleengineer.com/dsa/problems/house-robber-iii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe), [oyo](https://scaleengineer.com/companies/oyo)
---
## 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:**

![](https://assets.glich.co/dsa/house-robber-iii/image0.jpg) 

**Input:** root = [3,2,3,null,3,null,1]
**Output:** 7
**Explanation:** Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

**Example 2:**

![](https://assets.glich.co/dsa/house-robber-iii/image1.jpg) 

**Input:** root = [3,4,5,1,3,null,1]
**Output:** 9
**Explanation:** Maximum amount of money the thief can rob = 4 + 5 = 9.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `0 <= Node.val <= 104`

# Approaches
## Brute-Force Recursion
A straightforward recursive approach that directly translates the problem's logic. For each node, it calculates the maximum profit by considering two scenarios: robbing the current house or skipping it.
**Time:** O(2^N), where N is the number of nodes. The recursive calls branch out exponentially as many subproblems are recomputed. · **Space:** O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N). This space is used by the recursion stack.
**Pros:** Simple to understand and implement.; Directly follows the problem's constraints.
**Cons:** Extremely inefficient due to massive redundant computations.; Will likely result in a 'Time Limit Exceeded' error for larger trees.
### Explanation
The core idea is to define a recursive function, say `rob(node)`, which computes the maximum money that can be robbed from the subtree rooted at `node`.

At each `node`, we have two choices:
1.  **Rob the current node:** If we rob `node`, we gain `node.val` but cannot rob its immediate children (`node.left` and `node.right`). We can, however, rob its grandchildren. The total amount would be `node.val + rob(node.left.left) + rob(node.left.right) + rob(node.right.left) + rob(node.right.right)`.
2.  **Do not rob the current node:** If we skip `node`, we are free to rob its children. The total amount would be `rob(node.left) + rob(node.right)`.

The function `rob(node)` returns the maximum of these two options.
The base case for the recursion is when a node is `null`, in which case it returns 0.
This approach suffers from severe performance issues due to re-calculating the same subproblems multiple times. For instance, `rob(grandchild)` is computed independently by both `rob(parent)` and `rob(grandparent)`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // Option 1: Rob the root node
        int robRoot = root.val;
        if (root.left != null) {
            robRoot += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            robRoot += rob(root.right.left) + rob(root.right.right);
        }

        // Option 2: Don't rob the root node
        int skipRoot = rob(root.left) + rob(root.right);

        return Math.max(robRoot, skipRoot);
    }
}
```
### Algorithm
*   Define a function `rob(node)`.
*   Base Case: If `node` is `null`, return 0.
*   Calculate the profit if we rob the current node (`robCurrent`):
    *   Initialize `robCurrent = node.val`.
    *   If `node.left` is not null, add `rob(node.left.left) + rob(node.left.right)`.
    *   If `node.right` is not null, add `rob(node.right.left) + rob(node.right.right)`.
*   Calculate the profit if we skip the current node (`skipCurrent`):
    *   `skipCurrent = rob(node.left) + rob(node.right)`.
*   Return `max(robCurrent, skipCurrent)`.

## Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using a hash map to store the results of subproblems that have already been solved. This technique is known as memoization, a form of dynamic programming.
**Time:** O(N), where N is the number of nodes. Each subproblem (for each node) is computed only once thanks to memoization. · **Space:** O(N), where N is the number of nodes. The `memo` map can store up to N entries, and the recursion stack can go up to O(H) (O(N) in the worst case).
**Pros:** Significantly more efficient than brute-force.; Guarantees each subproblem is solved only once, leading to a polynomial time complexity.
**Cons:** Uses O(N) extra space for the memoization map, which can be significant for large trees.
### Explanation
The overlapping subproblems issue in the brute-force approach can be solved by caching the results. We use a hash map `memo` where the key is a `TreeNode` and the value is the maximum amount of money that can be robbed from the subtree rooted at that node.

The recursive function, `rob(node, memo)`, first checks if the result for the current `node` is already in the `memo` map.
If it is, the cached value is returned immediately, avoiding re-computation.
If not, it calculates the result just like in the brute-force approach: by comparing the profit from robbing the current node versus skipping it.
Before returning, the computed result is stored in the `memo` map for future use.
This ensures that the subproblem for each node is solved only once.

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int rob(TreeNode root) {
        return rob(root, new HashMap<>());
    }

    private int rob(TreeNode node, Map<TreeNode, Integer> memo) {
        if (node == null) {
            return 0;
        }
        if (memo.containsKey(node)) {
            return memo.get(node);
        }

        // Option 1: Rob the current node
        int robCurrent = node.val;
        if (node.left != null) {
            robCurrent += rob(node.left.left, memo) + rob(node.left.right, memo);
        }
        if (node.right != null) {
            robCurrent += rob(node.right.left, memo) + rob(node.right.right, memo);
        }

        // Option 2: Skip the current node
        int skipCurrent = rob(node.left, memo) + rob(node.right, memo);

        int result = Math.max(robCurrent, skipCurrent);
        memo.put(node, result);
        return result;
    }
}
```
### Algorithm
*   Create a `Map<TreeNode, Integer> memo` to store computed results.
*   Define a helper function `rob(node, memo)`.
*   Base Case: If `node` is `null`, return 0.
*   Memoization Check: If `memo` contains `node`, return `memo.get(node)`.
*   Calculate `robCurrent` and `skipCurrent` as in the brute-force approach, making recursive calls with the `memo` map.
*   `result = max(robCurrent, skipCurrent)`.
*   Store the result: `memo.put(node, result)`.
*   Return `result`.

## Optimized Dynamic Programming
This is the most efficient approach. Instead of a recursive function that returns a single value, we design a function that returns a pair of values for each node: the maximum profit if the node is robbed, and the maximum profit if the node is not robbed. This avoids the need to make recursive calls to grandchildren.
**Time:** O(N), where N is the number of nodes. We visit each node exactly once. · **Space:** O(H), where H is the height of the tree, for the recursion stack. This is O(log N) for a balanced tree and O(N) for a skewed tree. This is better than the O(N) space required for the memoization map in the previous approach.
**Pros:** Most efficient in both time and space.; Clean logic based on post-order traversal.; Avoids the overhead of a hash map and complex recursive calls to grandchildren.
**Cons:** The state representation (returning a pair/array) might be slightly less intuitive at first glance compared to the direct recursive approach.
### Explanation
We can observe that to decide the maximum profit for a node, we only need information from its immediate children, not its grandchildren.
Let's define a helper function, `robSub(node)`, that performs a post-order traversal and returns an array of two integers for each `node`: `[max_if_robbed, max_if_skipped]`.
- `max_if_robbed`: The maximum profit from the subtree at `node`, assuming we rob `node`.
- `max_if_skipped`: The maximum profit from the subtree at `node`, assuming we skip `node`.

The logic is as follows:
1.  Recursively call `robSub` on the left and right children to get their respective profit pairs: `leftPair` and `rightPair`.
2.  To calculate `max_if_robbed` for the current `node`: We must rob `node`, so we cannot rob its children. The profit is `node.val + leftPair[1] + rightPair[1]` (where `leftPair[1]` and `rightPair[1]` are the profits from skipping the children).
3.  To calculate `max_if_skipped` for the current `node`: We skip `node`, so we are free to either rob or skip its children. We take the maximum possible from each child's subtree. The profit is `max(leftPair[0], leftPair[1]) + max(rightPair[0], rightPair[1])`.

The base case is a `null` node, for which we return `[0, 0]`.
The final answer for the root of the tree is the maximum of the two values returned by `robSub(root)`.

```java
class Solution {
    public int rob(TreeNode root) {
        int[] result = robSub(root);
        return Math.max(result[0], result[1]);
    }

    // Returns an array of size 2: [max_if_robbed, max_if_skipped]
    private int[] robSub(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        int[] left = robSub(node.left);
        int[] right = robSub(node.right);

        // If we rob the current node, we cannot rob its children.
        // Profit = current_node_value + profit_from_skipping_left_child + profit_from_skipping_right_child
        int robbed = node.val + left[1] + right[1];

        // If we skip the current node, we can either rob or skip its children.
        // We take the max profit from the left and right subtrees.
        // Profit = max(profit_from_robbing_left, profit_from_skipping_left) + max(profit_from_robbing_right, profit_from_skipping_right)
        int skipped = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{robbed, skipped};
    }
}
```
### Algorithm
*   Define a helper function `robSub(node)` that returns an array of two integers `[robbed, skipped]`.
*   Base Case: If `node` is `null`, return `[0, 0]`.
*   Recursively call on children:
    *   `left = robSub(node.left)`
    *   `right = robSub(node.right)`
*   Calculate profit for the current node:
    *   `robbed = node.val + left[1] + right[1]` (rob current, so must skip children).
    *   `skipped = max(left[0], left[1]) + max(right[0], right[1])` (skip current, so take max from children).
*   Return `[robbed, skipped]`.
*   The main function calls `robSub(root)` and returns `max(result[0], result[1])`.

# Solutions
### Java

```java
public class House_Robber_III { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution_singleRecursion { public int rob ( TreeNode root ) { return Math . max ( dfs ( root , true ), dfs ( root , false )); } private int dfs ( TreeNode root , boolean isCurrentRootRobbed ) { if ( root == null ) { return 0 ; } if ( isCurrentRootRobbed ) { return root . val + dfs ( root . left , false ) + dfs ( root . right , false ); } else { // child can be either rob or no-rob return Math . max ( dfs ( root . left , true ), dfs ( root . left , false )) + Math . max ( dfs ( root . right , true ), dfs ( root . right , false )); } } } class Solution { /* 1. node value can be negative? */ public int rob ( TreeNode root ) { if ( root == null ) { return 0 ; } return Math . max ( target ( root ), skip ( root )); } private int target ( TreeNode root ) { if ( root == null ) { return 0 ; } return root . val + skip ( root . left ) + skip ( root . right ); } private int skip ( TreeNode root ) { if ( root == null ) { return 0 ; } // @note: not target, but rob again => 因为理论上可以连续skip两层 // return target(root.left) + target(root.right); return rob ( root . left ) + rob ( root . right ); } } } ///////// /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < TreeNode , Integer > memo ; public int rob ( TreeNode root ) { memo = new HashMap <>(); return dfs ( root ); } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } if ( memo . containsKey ( root )) { return memo . get ( root ); } int a = dfs ( root . left ) + dfs ( root . right ); int b = root . val ; if ( root . left != null ) { b += dfs ( root . left . left ) + dfs ( root . left . right ); } if ( root . right != null ) { b += dfs ( root . right . left ) + dfs ( root . right . right ); } int res = Math . max ( a , b ); memo . put ( root , res ); return res ; } }
```

### Python

```python
class Solution : def rob ( self , root : TreeNode ) -> int : return max ( self . dfs ( root , True ), self . dfs ( root , False )) # if no cache, then running time over limit @ cache def dfs ( self , root : TreeNode , isCurrentRootRobbed : bool ) -> int : if not root : return 0 if isCurrentRootRobbed : return root . val + self . dfs ( root . left , False ) + self . dfs ( root . right , False ) else : return self . rob ( root . left ) + self . rob ( root . right ) # below else logic also passing OJ # return max(self.dfs(root.left, True), self.dfs(root.left, False)) + max(self.dfs(root.right, True), self.dfs(root.right, False)) ########### # better and concise class Solution : # post-order def rob ( self , root : TreeNode ) -> int : def dfs ( node ): if not node : return 0 , 0 left , right = dfs ( node . left ), dfs ( node . right ) rob = node . val + left [ 1 ] + right [ 1 ] # [1] meaming left/right children skippted skip = max ( left ) + max ( right ) return rob , skip return max ( dfs ( root )) ########### class Solution : # return in else is too lengthy... def rob ( self , root : TreeNode ) -> int : return max ( self . dfs ( root , True ), self . dfs ( root , False )) # if no cache, then running time over limit @ cache def dfs ( self , root : TreeNode , isCurrentRootRobbed : bool ) -> int : if not root : return 0 if isCurrentRootRobbed : return root . val + self . dfs ( root . left , False ) + self . dfs ( root . right , False ) else : return max ( self . dfs ( root . left , True ), self . dfs ( root . left , False )) + max ( self . dfs ( root . right , True ), self . dfs ( root . right , False ))
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/house-robber-iii/ // Time: O(N) // Space: O(H) class Solution { pair < int , int > dfs ( TreeNode * root ) { // rob, skip if ( ! root ) return { 0 , 0 }; auto [ lr , ls ] = dfs ( root -> left ); auto [ rr , rs ] = dfs ( root -> right ); return { root -> val + ls + rs , max ( lr , ls ) + max ( rr , rs ) }; } public: int rob ( TreeNode * root ) { auto [ r , s ] = dfs ( root ); return max ( r , s ); } };
```