House Robber III
Understanding the Problem
We have a binary tree where each node holds a non-negative integer (the money in that house). The thief wants to maximize the total money stolen, but there is a constraint: if you rob a node, you cannot rob its direct parent or its direct children. In other words, no two adjacent nodes in the tree can both be robbed.
This is the tree version of the classic House Robber problem. In the original, houses sit in a line, and you cannot rob adjacent houses. Here, "adjacent" means parent-child in a tree. The linear structure is gone, so simple left-to-right DP will not work. We need to think recursively.
At every node, we face a binary choice. Either we rob this node (and skip its children, collecting from grandchildren and beyond) or we skip this node (and are free to rob or skip each child independently). The optimal answer for the whole tree is the better of these two choices made at the root, where each subtree has already resolved its own rob-or-skip decisions optimally.
Key Constraints:
1 <= number of nodes <= 10^4--> With up to 10,000 nodes, an O(n) solution is the target. The naive recursion without memoization is exponential on skewed trees, so we need memoization or a bottom-up traversal.0 <= Node.val <= 10^4--> All values are non-negative. The maximum possible total is 10^4 nodes times 10^4 per node, which is 10^8, well within a signed 32-bit integer. No overflow handling is needed.
Approach 1: Naive Recursion
Intuition
At every node, we choose to rob it or not. If we rob the current node, we add its value and then solve the problem for its four grandchildren (skipping both children). If we skip the current node, we solve the problem for its two children and take whatever is best from each. We pick whichever choice gives more money.
This translates the problem statement directly into code, but it solves the same subtree many times. When computing the answer for the root, both the "rob root" path (which needs grandchildren) and the "skip root" path (which needs children, which in turn need grandchildren) recompute the same nodes.
Algorithm
- If the node is null, return 0.
- Calculate the "rob this node" option: take the node's value, plus the results from all four grandchildren.
- Calculate the "skip this node" option: take the results from the left child and the right child.
- Return the maximum of rob and skip.
Example Walkthrough
Code
- Time Complexity: O(2^n) in the worst case. Each node spawns recursive calls to its children and grandchildren. On a skewed tree, the same nodes are recomputed many times, causing exponential blowup.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack goes as deep as the tree height. For a balanced tree this is O(log n), for a skewed tree it is O(n).
The redundant work comes from the rob option needing grandchildren while the skip option needs children, which then also need grandchildren. The next approach caches each node's result so it is computed only once.
Approach 2: Recursion with Memoization
Intuition
The naive approach has the correct logic but repeats work. The fix is to store the result of rob(node) in a hash map after computing it the first time, and check the map before computing any node. If we have seen this node before, we return the cached result. Each node is then computed at most once, so the total work drops from exponential to linear.
The hash map keys on the node reference (its identity in memory), not its value. This matters because two different nodes can hold the same value, and they must map to separate cache entries. Keying on the value would collide them and return a wrong result. The Rust implementation cannot hash an Rc<RefCell<TreeNode>> directly, so it keys on the raw pointer obtained from Rc::as_ptr, which gives the same identity guarantee.
Algorithm
- Create a hash map to store computed results, keyed by node reference.
- If the node is null, return 0.
- If the node is already in the map, return the cached value.
- Compute the rob option (node value + grandchildren results) and the skip option (children results), same as before.
- Store the maximum in the map and return it.
Example Walkthrough
Code
- Time Complexity: O(n). Each of the n nodes is computed exactly once and cached. All subsequent lookups are O(1).
- Space Complexity: O(n). The hash map stores one entry per node. The recursion stack adds O(h) but is dominated by the O(n) map.
The memoization approach runs in O(n) time, but it allocates a hash map and stores one entry per node. The next approach removes the map entirely by returning enough information from each recursive call for the parent to decide on its own.
Approach 3: Tree DP (Optimal)
Intuition
Instead of returning a single "best you can get" value from each subtree, return two values: the best if you rob this node, and the best if you skip this node. When a parent receives these two values from each child, it has everything it needs to make its own decision in constant time.
If we rob the current node, both children must be skipped. So the rob value is: node.val + leftSkip + rightSkip.
If we skip the current node, each child can be robbed or skipped independently. So the skip value is: max(leftRob, leftSkip) + max(rightRob, rightSkip).
Each node computes its pair in O(1) given its children's pairs. Since we process each node exactly once in a post-order traversal, the total time is O(n) with no hash map needed.
The two returned values are the only facts a parent needs about a child's subtree: the best total when the child is robbed, and the best total when the child is skipped. The adjacency rule constrains a node only against its direct parent and direct children, so once a child reports both of those totals, nothing deeper in that subtree can affect the parent's choice. That is the optimal substructure here: the answer for a node is built from the two summary values of each child, and the recursion computes those values exactly once on the way back up.
Algorithm
- Define a helper function that returns a pair
[robThis, skipThis]for each node. - If the node is null, return
[0, 0]. - Recursively get
[leftRob, leftSkip]from the left child and[rightRob, rightSkip]from the right child. - Compute
robThis = node.val + leftSkip + rightSkip(rob current, must skip children). - Compute
skipThis = max(leftRob, leftSkip) + max(rightRob, rightSkip)(skip current, children choose freely). - Return
[robThis, skipThis]. - The answer is
max(robThis, skipThis)at the root.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once in a post-order traversal. At each node, we do O(1) work (a few additions and comparisons).
- Space Complexity: O(h) where h is the height of the tree. The only space used is the recursion stack. For a balanced tree, h = O(log n). For a skewed tree, h = O(n). No hash map or extra data structure is needed.