House Robber III
Problem
Given the root of a binary tree, return the maximum amount of money the thief can rob without robbing directly connected houses (parent and child nodes).
- The number of nodes in the tree is in the range [0, 10⁴]
- 0 ≤ Node.val ≤ 10⁴
Example
root = [3,2,3,null,3,null,1]7The thief can rob the root (3) plus the two grandchildren (3 and 1) for a total of 7. Robbing the root's children (2 and 3) would prevent robbing the root itself, resulting in less total money. The algorithm uses DFS to explore each node's two states: robbing it or skipping it, combining results from children to maximize total profit.
Approach
Straightforward Solution
A naive approach tries all subsets of nodes, checking for adjacency violations, which is exponential and infeasible for large trees.
Core Observation
At each node, the thief faces a binary choice: rob this house and skip its immediate children, or skip this house and consider robbing its children. This creates two states per node that must be tracked and combined to find the global optimum.
Path to Optimal
PreviewThe key insight is to use DFS to compute two values for each node: the maximum amount if robbing this node (which excludes its children) and the maximum amount if skipping this node (which allows robbing children)…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewImplement a DFS helper that returns a tuple (rob_this, skip_this) for each node. 'rob_this' is the node's value plus the 'skip_this' values of its children, ensuring no adjacent nodes are robbed…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited exactly once in the DFS traversal, and constant work is done per node to compute the two states.
Space
O(h)
The recursion stack depth is proportional to the height of the tree, which is O(h). No additional data structures proportional to n are used.
Pattern Spotlight
DFS (Stateful Exploration with Dual State Tracking)
When a problem requires making mutually exclusive choices at each node (e.g., rob or skip) that affect adjacent nodes, track multiple states per node during DFS to capture all possibilities and combine them optimally.
Solution
| 1 | class Solution: |
| 2 | def rob(self, root: Optional[TreeNode]) -> int: |
| 3 | |
| 4 | def dfs(node): |
| 5 | if not node: |
| 6 | return (0, 0) |
| 7 | |
| 8 | left = dfs(node.left) |
| 9 | right = dfs(node.right) |
| 10 | |
| 11 | rob_this = node.val + left[1] + right[1] |
| 12 | |
| 13 | skip_this = max(left) + max(right) |
| 14 | |
| 15 | return (rob_this, skip_this) |
| 16 | |
| 17 | return max(dfs(root)) |
Step-by-Step Solution
Recursively Compute Rob and Skip Values for Each Node
| 4 | def dfs(node): |
| 5 | if not node: |
| 6 | return (0, 0) |
| 8 | left = dfs(node.left) |
| 9 | right = dfs(node.right) |
| 11 | rob_this = node.val + left[1] + right[1] |
| 13 | skip_this = max(left) + max(right) |
| 15 | return (rob_this, skip_this) |
Objective
To calculate the maximum money obtainable by either robbing or skipping the current node, based on its children's states.
Key Insight
By returning a tuple of two values from each recursive call—one for robbing the current node and one for skipping it—the algorithm cleanly separates mutually exclusive choices. Robbing the current node adds its value plus the 'skip' values of its children, ensuring no adjacent nodes are robbed. Skipping the current node allows taking the maximum of robbing or skipping each child, maximizing profit without adjacency violations. This dual-state tracking is the core insight that transforms an exponential problem into a linear one.
Interview Quick-Check
Core Logic
The DFS returns two values per node: max profit if robbing this node (node.val + skip values of children) and max profit if skipping this node (max of rob or skip for each child).
State & Boundaries
The base case returns (0, 0) for null nodes, representing zero profit whether robbing or skipping.
Common Pitfalls & Bugs
Failing to separate rob and skip states leads to incorrect sums that violate the adjacency constraint.
Complexity
This approach visits each node once, resulting in O(n) time and O(h) space due to recursion.
Return the Maximum Profit from Root Node States
To select the overall maximum profit achievable by either robbing or skipping the root node.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
rob_this = node.val + left[1] + right[1]Calculate profit if robbing the current node.
Robbing this node requires skipping its children, so add node's value plus skip values from left and right children to avoid adjacency violations.
skip_this = max(left) + max(right)Calculate profit if skipping the current node.
Skipping this node allows robbing or skipping children independently, so take the maximum profit from each child's two states and sum them.
if not node:Check if the current node is null (base case).
Returning (0, 0) for null nodes correctly represents zero profit and terminates recursion safely.
Full line-by-line criticality + rationale for all 9 lines available on Pro.
Test Your Understanding
Why does the algorithm track two values (rob_this and skip_this) for each node instead of a single maximum value?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct House Robber III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the House Robber III drill