337. House Robber III
Asked at Amazon
Difficulty
Medium
Time
O(n)
Space
O(h)
Pattern
Dynamic Programming
Companies
1
Problem
A thief wants to rob houses that are arranged as a binary tree. The root node is the only entrance. Each house holds some money, given by its node value.
The police are called if the thief robs two houses that are directly connected by an edge (a parent and its child). So the thief must pick a set of nodes where no two chosen nodes are adjacent.
Given the root of the tree, return the maximum total money the thief can take without triggering the alarm.
Pick nodes with no parent-child pair
Constraints
- ●
The number of nodes in the tree is in the range [1, 10^4]. - ●
0 <= Node.val <= 10^4
Examples
root = [3,2,3,null,3,null,1]7root = [3,4,5,1,3,null,1]9Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
How to Think About It
Think recursively — for each node, you either rob it or skip it.
A naive recursive solution explores both choices at every node, leading to exponential time.
Use memoization to cache results of subtrees and avoid recomputation.
At each node, return two values: the max money if you rob this node, and the max if you skip it.
The optimal solution uses a single DFS pass returning a pair (rob, skip) for each subtree, achieving O(n) time.
Optimal Approach
Perform a depth-first search on the tree. For each node, return a pair (rob, skip) where rob is the max money obtainable if the node is robbed, and skip is the max if the node is skipped. If you rob the current node, you must skip its children: rob = node.val + left.skip + right.skip. If you skip the current node, you can take the best from children: skip = max(left) + max(right). The answer is max(root.rob, root.skip).
Each node returns (rob, skip)
What Trips People Up in Real Interviews
Clarify the constraint — adjacent means connected by an edge in the tree, not just neighboring levels.
Start by explaining the brute force recursive approach with two choices per node.
Transition to the optimized DFS that returns a tuple of (rob_this_node, skip_this_node).
Explain why this is O(n) time — each node is visited exactly once.
Edge cases: null tree (0), single node (value of that node), skewed tree vs balanced tree.
Solution Code
O(n) timedef rob(root):
def dfs(node):
if not node:
return (0, 0)
left = dfs(node.left)
right = dfs(node.right)
rob = node.val + left[1] + right[1]
skip = max(left) + max(right)
return (rob, skip)
return max(dfs(root))Frequently Asked Questions
What is the House Robber III problem?
A thief robs houses arranged in a binary tree where each node represents the amount of money in that house. No two adjacent houses (connected by an edge) can be robbed on the same night. Find the maximum amount that can be robbed.
How do you solve House Robber III?
The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask House Robber III?
House Robber III is asked at Amazon. It is a medium difficulty problem.
What are common mistakes on House Robber III?
- Clarify the constraint — adjacent means connected by an edge in the tree, not just neighboring levels.
- Start by explaining the brute force recursive approach with two choices per node.
- Transition to the optimized DFS that returns a tuple of (rob_this_node, skip_this_node).
- Explain why this is O(n) time — each node is visited exactly once.
- Edge cases: null tree (0), single node (value of that node), skewed tree vs balanced tree.