DP on Trees — House Robber III

DP on Trees Pattern

Process the tree bottom-up via DFS. Each node computes its DP values from its children's results. Return a pair: [value if we include this node, value if we exclude it].

Key constraint: if you rob a node, you can't rob its children. If you skip a node, children are free to be robbed or not.

Recurrence

dfs(node) → [rob, skip]

[leftRob, leftSkip] = dfs(left)
[rightRob, rightSkip] = dfs(right)

rob = node.val + leftSkip + rightSkip
skip = max(leftRob,leftSkip) + max(rightRob,rightSkip)

answer = max(rob, skip) at root

If we ROB this node

Add node's value. Children MUST be skipped (can't rob adjacent). So we take leftSkip + rightSkip.

If we SKIP this node

Node contributes 0. Each child independently chooses the better option: max(childRob, childSkip).

Why post-order DFS?

We need children's results before computing the parent. Process leaves first, then work up to the root.

C++ — House Robber III

pair<int,int> dfs(TreeNode* node) {
    if (!node) return {0, 0};

    auto [leftRob, leftSkip] = dfs(node->left);
    auto [rightRob, rightSkip] = dfs(node->right);

    // Rob this node: can't rob children
    int rob = node->val + leftSkip + rightSkip;

    // Skip this node: children choose freely
    int skip = max(leftRob, leftSkip)
             + max(rightRob, rightSkip);

    return {rob, skip};
}

int rob(TreeNode* root) {
    auto [r, s] = dfs(root);
    return max(r, s);
}

Complexity

Time

O(N)

Visit each node once.

Space

O(H)

H = tree height (recursion stack).

Pattern

Post-order DFS

Process children first, then compute parent.

Other Examples

Diameter, LCA, Rerooting

Many tree problems use this bottom-up DP approach.

📝 Notes

▼