House Robber on a Tree
Filed under Amazon
Free read 2 of 3For each node, return a pair: (max sum including node, max sum excluding node).
The question
Given a binary tree where each node has a value, find the maximum sum of values such that no two selected nodes are directly connected (parent-child).
Constraints
- Tree structure
- Non-negative values
- Standard tree traversal
Examples
- Input
- 3(2(3), 3(1))
- Output
- 7
- Why
- Select root(3) and children of children(3, 1) = 7.
Approach
For each node, return a pair: (max sum including node, max sum excluding node).
If node is included, children must be excluded. If node is excluded, children can be either.
Null node returns (0, 0).
Solution
O(N) time, O(H) space
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob(root):
def dfs(node):
if not node: return (0, 0)
l = dfs(node.left)
r = dfs(node.right)
inc = node.val + l[1] + r[1]
exc = max(l) + max(r)
return (inc, exc)
return max(dfs(root))
Tips
- What they are testing: Tests recursive DP on trees.
- Common mistake: Calculating only one state per node instead of two (included vs excluded).
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.