AlgoInsight

DSA problem

House Robber III

MediumTree / Graph DPPattern: Tree / Graph DPtop150FreeAmazonGoogleMicrosoftMetaBloomberg

The thief has discovered a new place to rob — a binary tree of houses. Each node holds a non-negative integer amount of money. The root is the entrance, and every other house has exactly one parent house. The catch is the same alarm rule as in the array version: two directly-linked houses (a parent and its child) cannot both be robbed on the same night. Given the root of the binary tree, return the maximum amount of money the thief can steal without triggering the alarm.

A naive recursion considers two choices at every node: rob it (so neither child can be robbed) or skip it (each child is then free to make its own optimal choice). The recurrence rob(node) = max(node.val + skip(left) + skip(right), rob(left) + rob(right)) is correct, but if implemented as two separate recursive calls per subtree it explodes into exponential overlapping work — each call to rob triggers calls to skip on its children, and each call to skip recursively invokes rob and skip again on the same subtrees.

Memoization on the node reference fixes the blowup, but the cleanest fix is structural: collapse both pieces of information into a single post-order traversal. For every subtree rooted at node, compute a pair (rob, notRob), where rob is the best total assuming we DO rob node and notRob is the best total assuming we DO NOT. The pair from a single recursive call delivers everything its parent needs.

The recurrences are then trivial: rob = node.val + leftNotRob + rightNotRob (children must be skipped), and notRob = max(leftRob, leftNotRob) + max(rightRob, rightNotRob) (each child independently picks its best option). The final answer at the root is max(rob, notRob). This runs in O(n) time visiting each node once, and O(h) space for the recursion stack where h is the height of the tree.

Examples

Example 1
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Rob root (3), skip its children, then rob the right grandchild of the root (3) and the left grandchild (1)? Actually the optimal is rob root 3 + right.right? No: rob = 3 + 3 + 1 = 7. The non-adjacent set {root=3, left-child-of-left=3, right-child-of-right=1} sums to 7.
Example 2
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Skip the root (3) and rob both its children: 4 + 5 = 9. Their grandchildren would add 1 + 3 + 1 = 5 < 9, so the optimum is robbing the middle layer.
Example 3
Input: root = [2,1,3,null,4]
Output: 7
Explanation: Rob the root (2) + the right child (3) + the grandchild (4)? The set {root=2, left-grandchild? none, right-child=3} cannot include 4 because 4 is a child of 1 which is a child of root; skipping root yields 1 + 3 + 4 = something, so optimal works out to 7 via the pair recurrence at each node.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

treedynamic-programmingdfsbinary-tree

Browse all DSA problems