LeetCode 337 - House Robber III
This problem is a variation of the classic House Robber dynamic programming problem, but instead of houses being arranged in a straight line, the houses form a binary tree.
Difficulty: 🟡 Medium
Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree
Solution
Problem Understanding
This problem is a variation of the classic House Robber dynamic programming problem, but instead of houses being arranged in a straight line, the houses form a binary tree.
Each node in the binary tree represents a house, and the value stored in the node represents the amount of money available in that house. The thief wants to maximize the total amount of money stolen, but there is an important restriction: two directly connected houses cannot both be robbed on the same night. In tree terminology, that means a parent and its child cannot both be selected.
The input is the root node of a binary tree. Every node may have a left child, a right child, both, or neither. The output should be a single integer representing the maximum amount of money that can be stolen while respecting the adjacency restriction.
The constraints tell us several important things:
- The tree can contain up to
10^4nodes. - Node values can be as large as
10^4. - The tree is not guaranteed to be balanced.
Because the tree can be large, an exponential brute-force solution will not finish in time. We need an algorithm close to linear time.
Several edge cases are important:
- A tree with only one node. In this case, the answer is simply that node's value.
- A skewed tree that behaves like a linked list. Recursive depth and repeated computations become important considerations.
- Nodes with value
0. Sometimes skipping a node is better even when it exists. - Trees where robbing grandchildren is better than robbing children.
- Trees where robbing the root blocks access to large-valued children.
The core challenge is deciding, for every node, whether robbing it produces a better total than skipping it.
Approaches
Brute Force Approach
A straightforward recursive approach is to consider two choices at every node:
- Rob the current node.
- Skip the current node.
If we rob the current node, we cannot rob its direct children, so we recursively compute the best values from the grandchildren.
If we skip the current node, we are free to rob or skip each child independently, so we recursively compute the best values from the children.
The recurrence looks like this conceptually:
rob(node) = node.val + rob(grandchildren)skip(node) = rob(children)- Answer is
max(rob(node), skip(node))
This approach is correct because it exhaustively explores all valid combinations.
However, it is extremely inefficient because the same subtrees are recomputed many times. For example, a subtree may be evaluated once as part of a "rob parent" scenario and again as part of a "skip parent" scenario. This overlapping work causes exponential time complexity.
Optimal Dynamic Programming Approach
The key insight is that every node only needs two pieces of information:
- The maximum money obtainable if this node is robbed.
- The maximum money obtainable if this node is skipped.
Instead of recomputing subproblems repeatedly, we compute these two values once per node using postorder traversal.
For a node:
- If we rob it, we cannot rob its children.
- If we skip it, each child can independently be robbed or skipped, whichever gives a larger value.
This naturally leads to tree dynamic programming.
For every node, we return a pair:
rob_currentskip_current
Using the results from the left and right children, we compute the current node's optimal states in constant time.
Because every node is processed once, the solution becomes linear.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(h) | Recomputes the same subtrees repeatedly |
| Optimal | O(n) | O(h) | Tree DP using postorder traversal |
Here, n is the number of nodes and h is the height of the tree.
Algorithm Walkthrough
- Define a recursive DFS function that processes one node at a time.
The function should return two values:
- Maximum money if the current node is robbed.
- Maximum money if the current node is skipped.
Returning both values together avoids recomputation. 2. Handle the base case.
If the node is None, return (0, 0) because an empty subtree contributes no money whether we rob or skip it.
3. Recursively process the left subtree.
The recursive call returns:
left_robleft_skip
- Recursively process the right subtree.
The recursive call returns:
right_robright_skip
- Compute the value when robbing the current node.
If we rob the current node, we cannot rob either child.
Therefore:
rob_current = node.val + left_skip + right_skip
- Compute the value when skipping the current node.
If we skip the current node, each child independently chooses its better option.
Therefore:
skip_current = max(left_rob, left_skip) + max(right_rob, right_skip)
- Return both values upward.
The parent node will use these results to compute its own states. 8. After processing the root, take the maximum of the two returned values.
The root itself may or may not be robbed, depending on which produces the larger result.
Why it works
The algorithm works because every subtree is solved optimally and independently. For each node, the only relevant information is whether the node itself is robbed or skipped. Once those two states are computed for the children, the parent can determine its own optimal states without needing any additional information.
This satisfies the optimal substructure property required for dynamic programming. Since every node is processed exactly once, the algorithm avoids repeated work and guarantees the optimal result.
Python Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional, Tuple
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
if not node:
return (0, 0)
left_rob, left_skip = dfs(node.left)
right_rob, right_skip = dfs(node.right)
rob_current = node.val + left_skip + right_skip
skip_current = (
max(left_rob, left_skip) +
max(right_rob, right_skip)
)
return (rob_current, skip_current)
rob_root, skip_root = dfs(root)
return max(rob_root, skip_root)
The implementation follows the dynamic programming strategy directly.
The nested dfs function performs a postorder traversal. It processes the children first because the current node depends on the results from both subtrees.
The base case returns (0, 0) for a null node. This simplifies the recursive logic because parent nodes can safely use these values in arithmetic operations.
For each node, the algorithm calculates two states:
rob_current, meaning the current node is robbed.skip_current, meaning the current node is skipped.
If the node is robbed, both children must be skipped. If the node is skipped, each child independently contributes its best possible result.
Finally, after processing the root, the algorithm returns whichever state gives the larger value.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
var dfs func(node *TreeNode) (int, int)
dfs = func(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
leftRob, leftSkip := dfs(node.Left)
rightRob, rightSkip := dfs(node.Right)
robCurrent := node.Val + leftSkip + rightSkip
skipCurrent := max(leftRob, leftSkip) +
max(rightRob, rightSkip)
return robCurrent, skipCurrent
}
robRoot, skipRoot := dfs(root)
return max(robRoot, skipRoot)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
The Go implementation mirrors the Python solution closely.
Go does not support tuple literals directly like Python, but multiple return values provide the same functionality cleanly.
The base case checks for nil nodes instead of None.
A helper max function is required because Go does not provide a built-in integer maximum function for primitive integers.
Since node values are bounded by 10^4 and the tree contains at most 10^4 nodes, standard Go int values are completely safe from overflow in this problem.
Worked Examples
Example 1
Input:
3
/ \
2 3
\ \
3 1
We process nodes bottom-up.
Step-by-step states
| Node | rob_current | skip_current |
|---|---|---|
| 3 (leaf) | 3 | 0 |
| 1 (leaf) | 1 | 0 |
| 2 | 2 + 0 = 2 | max(0,0) + max(3,0) = 3 |
| 3 (right parent) | 3 + 0 = 3 | max(0,0) + max(1,0) = 1 |
| Root 3 | 3 + 3 + 1 = 7 | max(2,3) + max(3,1) = 6 |
Final answer:
max(7, 6) = 7
The optimal strategy is robbing:
- Root
3 - Left grandchild
3 - Right grandchild
1
Total:
3 + 3 + 1 = 7
Example 2
Input:
3
/ \
4 5
/ \ \
1 3 1
Step-by-step states
| Node | rob_current | skip_current |
|---|---|---|
| 1 (leaf) | 1 | 0 |
| 3 (leaf) | 3 | 0 |
| 1 (right leaf) | 1 | 0 |
| 4 | 4 + 0 + 0 = 4 | 1 + 3 = 4 |
| 5 | 5 + 0 = 5 | 1 |
| Root 3 | 3 + 4 + 1 = 8 | 4 + 5 = 9 |
Final answer:
max(8, 9) = 9
The optimal strategy is robbing nodes 4 and 5.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every node is processed exactly once |
| Space | O(h) | Recursive call stack depends on tree height |
The DFS traversal visits each node one time and performs only constant work at each visit. Therefore, the total running time is linear in the number of nodes.
The space complexity comes from recursion depth. In a balanced tree, the height is O(log n). In the worst case, such as a completely skewed tree, the height becomes O(n).
Test Cases
# Definition for testing
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rob(self, root):
def dfs(node):
if not node:
return (0, 0)
left_rob, left_skip = dfs(node.left)
right_rob, right_skip = dfs(node.right)
rob_current = node.val + left_skip + right_skip
skip_current = (
max(left_rob, left_skip) +
max(right_rob, right_skip)
)
return (rob_current, skip_current)
return max(dfs(root))
sol = Solution()
# Example 1
root1 = TreeNode(3)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.right = TreeNode(3)
root1.right.right = TreeNode(1)
assert sol.rob(root1) == 7 # provided example 1
# Example 2
root2 = TreeNode(3)
root2.left = TreeNode(4)
root2.right = TreeNode(5)
root2.left.left = TreeNode(1)
root2.left.right = TreeNode(3)
root2.right.right = TreeNode(1)
assert sol.rob(root2) == 9 # provided example 2
# Single node
root3 = TreeNode(10)
assert sol.rob(root3) == 10 # single house
# Root better than children
root4 = TreeNode(10)
root4.left = TreeNode(1)
root4.right = TreeNode(1)
assert sol.rob(root4) == 10 # rob root only
# Children better than root
root5 = TreeNode(1)
root5.left = TreeNode(10)
root5.right = TreeNode(20)
assert sol.rob(root5) == 30 # skip root
# Skewed tree
root6 = TreeNode(3)
root6.right = TreeNode(2)
root6.right.right = TreeNode(3)
root6.right.right.right = TreeNode(1)
assert sol.rob(root6) == 6 # linked-list style tree
# All zeros
root7 = TreeNode(0)
root7.left = TreeNode(0)
root7.right = TreeNode(0)
assert sol.rob(root7) == 0 # zero-valued nodes
# Grandchildren better choice
root8 = TreeNode(4)
root8.left = TreeNode(1)
root8.right = TreeNode(1)
root8.left.left = TreeNode(5)
root8.right.right = TreeNode(5)
assert sol.rob(root8) == 14 # rob root and grandchildren
| Test | Why |
|---|---|
[3,2,3,null,3,null,1] |
Validates the first provided example |
[3,4,5,1,3,null,1] |
Validates the second provided example |
| Single node tree | Tests minimal input size |
| Large root with small children | Ensures robbing root is chosen |
| Small root with large children | Ensures skipping root is chosen |
| Skewed tree | Tests recursion on unbalanced trees |
| All zero values | Ensures zero handling is correct |
| Grandchildren larger than children | Verifies non-adjacent optimization |
Edge Cases
One important edge case is a tree containing only a single node. A naive implementation might incorrectly assume the existence of children or perform unnecessary recursion. In this implementation, the DFS handles leaf nodes naturally because their children return (0, 0), making the node's robbed value equal to its own value.
Another important case is a highly unbalanced tree, where every node has only one child. Such a tree behaves similarly to a linked list. Some implementations may accidentally introduce excessive recomputation or incorrect parent-child handling in this scenario. Since this solution processes each node exactly once and uses only recursive state passing, it remains efficient even for skewed trees.
A third important edge case occurs when skipping a node is better than robbing it. For example, a small-valued parent with very large-valued children should not be robbed. Greedy approaches often fail here because taking the current node may block access to more valuable descendants. This implementation explicitly computes both possibilities at every node and chooses the optimal result, ensuring correctness.
Another subtle edge case involves zero-valued nodes. A node with value 0 may still influence the structure of valid robberies because robbing it prevents robbing its children. The algorithm correctly evaluates both states independently, so it never assumes robbing a node is beneficial simply because it exists.