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
The 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). By returning these two values up the recursion, the algorithm efficiently combines subproblems without redundant computations.
Optimal Approach
Implement 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. 'skip_this' is the max of robbing or skipping each child, allowing maximum flexibility. The final answer is the max of these two values at the root.
Time
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
| 17 | return max(dfs(root)) |
Objective
To select the overall maximum profit achievable by either robbing or skipping the root node.
Key Insight
The final answer is the maximum of robbing or skipping the root, as these two states represent all valid robbery scenarios for the entire tree. This simple max operation consolidates the dual-state results propagated up from all subtrees into a single optimal solution.
Interview Quick-Check
Core Logic
Taking the max of the two returned values from dfs(root) yields the global maximum profit.
State & Boundaries
This step finalizes the recursive exploration by choosing the best of the two mutually exclusive root states.
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.
return (rob_this, skip_this)Return the tuple of rob and skip profits for the current node.
Returning both states enables the parent node to make an informed decision, preserving the mutually exclusive choices throughout the recursion.
return max(dfs(root))Return the maximum profit achievable from the root node.
Taking the max of robbing or skipping the root consolidates all subtree computations into the final optimal solution.
return (0, 0)Return zero profit tuple for null nodes.
This base case ensures that leaf nodes' children contribute zero, enabling correct aggregation of profits.
left = dfs(node.left)Recursively compute rob and skip values for the left child.
This recursive call gathers the two-state results from the left subtree, essential for combining with the current node's decision.
right = dfs(node.right)Recursively compute rob and skip values for the right child.
Similarly, this call obtains the left child's results, enabling full subtree state aggregation.
def dfs(node):Define the DFS helper function to compute rob and skip values for a node.
Encapsulating the logic in a recursive function allows systematic exploration of the tree and state tracking per node.
Test Your Understanding
Why does the algorithm track two values (rob_this and skip_this) for each node instead of a single maximum value?
Because robbing a node excludes robbing its immediate children, and skipping a node allows robbing children, tracking both states separately enables combining subproblems without violating adjacency constraints and ensures the global maximum is found.
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