Problem statement

The houses of a neighbourhood are arranged as a binary tree: every house except the root has exactly one parent house, and each node's value is the money inside that house.

A thief may rob any set of houses, except that two houses joined directly by an edge (a parent and its child) can never both be robbed — the alarm would go off. Return the most money the thief can take.

Example 1

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Rob the root 3 and the two grandchildren 3 and 1: 3 + 3 + 1 = 7.

Example 2

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Rob the root's two children 4 and 5: 4 + 5 = 9.

Example 3

Input: root = [4,1,null,2,null,3]
Output: 7
Explanation: A chain 4 - 1 - 2 - 3: robbing 4 and 3 gives 7; 4 and 2 would give only 6.

Constraints

• 1 <= number of nodes <= 10^4
• 0 <= Node.val <= 10^4

Hints for House Robber III

1. Hint 1

   Whether a house can be robbed depends only on whether its parent was robbed.

2. Hint 2

   For each subtree, compute two answers: the best total if its root is robbed, and the best total if its root is left alone.

3. Hint 3

   Robbing a node means skipping both children; skipping it leaves each child free to be robbed or not — take the better of its two answers. Compute both answers bottom-up in one post-order pass.

How to solve House Robber III

Dynamic programming on the tree: for every node keep the best loot of its subtree with the node robbed and with it skipped, both computed from the children's pairs.

Approach

1. Define best(node) returning a pair (take, skip); for a null node it is (0, 0).
2. Compute the pairs (lt, ls) and (rt, rs) of the two children.
3. take = node.val + ls + rs — robbing the node forces both children to be skipped.
4. skip = max(lt, ls) + max(rt, rs) — each child may go either way.
5. Return max(take, skip) for the root.

Why it works

The only constraint links a node to its children, so once a node's choice is fixed its two subtrees are independent problems, each needing only its own root's choice. The pair therefore captures everything a parent needs, and by induction each pair is optimal for its subtree.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Robbing alternate levels is not optimal: in the chain 4 - 1 - 2 - 3 the best picks 4 and 3, two levels apart.
• A plain recursion that recomputes grandchildren's answers for each choice is exponential; return both values from one call.

Reference solution

Python

from typing import Optional

def rob(root: Optional[TreeNode]) -> int:
    def best(node):
        if node is None:
            return 0, 0
        lt, ls = best(node.left)
        rt, rs = best(node.right)
        return node.val + ls + rs, max(lt, ls) + max(rt, rs)

    return max(best(root))

Java

public static int rob(TreeNode root) {
    int[] r = robPair(root);
    return Math.max(r[0], r[1]);
}

static int[] robPair(TreeNode node) {
    if (node == null) return new int[] {0, 0};
    int[] l = robPair(node.left), r = robPair(node.right);
    return new int[] {node.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])};
}

C++

pair<int, int> robPair(TreeNode* node);

int rob(TreeNode* root) {
    pair<int, int> r = robPair(root);
    return max(r.first, r.second);
}

pair<int, int> robPair(TreeNode* node) {
    if (!node) return {0, 0};
    pair<int, int> l = robPair(node->left), r = robPair(node->right);
    return {node->val + l.second + r.second, max(l.first, l.second) + max(r.first, r.second)};
}

JavaScript

var rob = function(root) {
    var r = robPair(root);
    return Math.max(r[0], r[1]);
};

var robPair = function(node) {
    if (node === null) return [0, 0];
    var l = robPair(node.left), r = robPair(node.right);
    return [node.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium