Watch 10 video solutions for House Robber III, a medium level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by NeetCode has 377,825 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Constraints:
[1, 104].0 <= Node.val <= 104Problem Overview: Each node in a binary tree represents a house containing money. If you rob a house, you cannot rob its direct children. The goal is to compute the maximum amount of money you can steal without triggering the alarm.
This is a tree variant of the classic House Robber problem. Instead of a linear array, houses form a binary tree. The restriction applies between a node and its children, which naturally leads to a recursive decision at every node: rob it or skip it.
Approach 1: Brute Force DFS (Exponential Time)
Traverse the tree using Depth-First Search. For each node, compute two choices: rob the current node (which means skipping its children and exploring grandchildren) or skip the node (which allows exploring both children). The algorithm recursively evaluates both scenarios and returns the larger value. This approach repeatedly recomputes the same subtrees, causing exponential growth in work. Time complexity is O(2^n) in the worst case, and recursion depth requires O(h) space where h is the tree height.
Approach 2: Recursive DFS with Memoization (O(n))
The key observation: the maximum loot for a subtree rooted at a node is always the same regardless of how many times it is reached. Store the computed result for each node in a hash map (memo table). When DFS visits a node again, return the cached value instead of recomputing it.
For each node, compute:
rob = node.val + value(grandchildren)
skip = value(left child) + value(right child)
The result for that node is max(rob, skip). Memoization ensures each node's value is calculated once. This transforms the algorithm into a classic Dynamic Programming on trees problem. The DFS visits every node once, giving O(n) time complexity. The memo table stores results for up to n nodes, so space complexity is O(n) with recursion stack up to O(h).
This pattern is often called tree DP: compute optimal values for subtrees and reuse them while exploring the tree. Memoization prevents recomputation of overlapping subproblems, which is the main bottleneck in the brute force solution.
Recommended for interviews: The DFS with memoization approach is the expected solution. Interviewers want to see that you first recognize the rob/skip decision pattern from House Robber I, then adapt it to a tree structure using recursion. Explaining the brute force approach briefly shows understanding of the decision space, while introducing memoization demonstrates strong dynamic programming intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS | O(2^n) | O(h) | Conceptual starting point to understand rob vs skip decisions |
| DFS with Memoization (Tree DP) | O(n) | O(n) | Optimal solution for interviews and production code |