Dynamic Programming • Trees

House Robber III

Rob houses arranged in a binary tree where you cannot rob two directly linked houses.

Overview

This combines Tree DFS with the House Robber state machine logic. A classic "DP on Trees" problem.

Instead of returning a single integer, the recursive DFS function returns an array of two values: `[maxIfRobbed, maxIfSkipped]`.

If you rob the current node, you CANNOT rob its children. So `robThis = node.val + leftSkipped + rightSkipped`.

If you skip the current node, you have the CHOICE to rob or skip the children (whichever is better). `skipThis = max(left) + max(right)`.

$3

$2

$3

$1

Robbed 🔴Skipped 🟢

Code Tracker

:::

1function rob(node) {

2 if (!node) return [0, 0]; // [robbed, skipped]

3

4 let left = rob(node.left);

5 let right = rob(node.right);

6

7 let robNode = node.val + left[1] + right[1];

8 let skipNode = Math.max(...left) + Math.max(...right);

9

10 return [robNode, skipNode];

11}