โ† Amazon questions

House Robber on a Tree

Filed under Amazon

Free read 2 of 3

For 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

  1. For each node, return a pair: (max sum including node, max sum excluding node).

Solution

O(N) time, O(H) space

Python
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.