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.
This approach uses recursion along with memoization to store the maximum robbery amount for each node of the tree. The idea is to leverage a helper function that returns two values for each node: maximum money if the current node is included and maximum money if the current node is not included. At each node, we have two choices: either rob this node or not rob it, and for each choice, there are further choices for child nodes and so on.
The helper function returns two values for each node. It uses recursion to visit each node in the tree, calculating the maximum robbery amount when the current node is included or not. For each node, if it's robbed, the children cannot be robbed; else, we take the maximum of robbing or not robbing the children. The final result is the maximum of the helper(root) values.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree. |
| Default Approach | — |
| 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 |
House Robber III - Tree - Leetcode 337 • NeetCode • 59,450 views views
Watch 9 more video solutions →Practice House Robber III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor