Chapter 20: DP on Trees - House Robber III

We have mastered dynamic programming on linear and 2D data structures. Now, we will venture into a new domain: applying DP to trees. The principles remain the same—breaking a problem into optimal subproblems—but the "subproblems" are now defined by the subtrees of each node.

A recursive, top-down approach is often the most intuitive way to handle DP on trees. To illustrate this, we'll revisit a familiar foe with a new twist: "House Robber III" (Problem #337).

The Problem:

The houses in a neighborhood are arranged in a binary tree. A thief wants to rob them but faces one constraint: they cannot rob two directly-linked houses (i.e., a parent and its child).

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

For example:

• Tree: [3, 2, 3, null, 3, null, 1]

• Output: 7

• Explanation: The thief can rob the two houses with value 3 and the house with value 1, for a total of 3 + 3 + 1 = 7.

The Key Insight: Richer State Information

In the original "House Robber," the state at index i only depended on states at i-1 and i-2. Here, the decision at a parent node depends on the decisions at its children.

A simple function solve(node) that just returns one number (the max profit for that subtree) is not enough. Why? Because if we rob the parent, we cannot rob the children. But if we don't rob the parent, we are free to either rob or not rob the children. The parent needs more information from its children to make the best choice.

The solution is to have our recursive function return a tuple of two values for each node:

1. The maximum profit from this node's subtree if we rob this node.

2. The maximum profit from this node's subtree if we do not rob this node.

Let's call our function solve(node), which will return (rob_this_node, dont_rob_this_node).

Approach 1: The Recursive Solution

We can define the two return values based on the results from the node's children:

1. To calculate rob_this_node: If we rob the current node, we get its value, but we cannot rob its immediate children. Therefore, we must take the profit from the "don't rob" scenarios of its left and right children. rob_this_node = node.val + left_dont_rob + right_dont_rob

2. To calculate dont_rob_this_node: If we don't rob the current node, we are free to do whatever is optimal for its children. For each child, we can either rob it or not rob it, so we take the maximum of those two options. dont_rob_this_node = max(left_rob, left_dont_rob) + max(right_rob, right_dont_rob)

The base case is a None node, which contributes zero profit in either case, so it returns (0, 0).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def rob_recursive(root: Optional[TreeNode]) -> int:

    def solve(node):
        """Returns a tuple: (profit_if_robbing_this_node, profit_if_not_robbing_this_node)"""
        if not node:
            return (0, 0) # (rob, dont_rob)

        # Get results from children
        left_rob, left_dont_rob = solve(node.left)
        right_rob, right_dont_rob = solve(node.right)

        # 1. Calculate profit if we rob the current node
        profit_if_rob = node.val + left_dont_rob + right_dont_rob

        # 2. Calculate profit if we don't rob the current node
        profit_if_dont_rob = max(left_rob, left_dont_rob) + max(right_rob, right_dont_rob)

        return (profit_if_rob, profit_if_dont_rob)

    # The final answer is the max of robbing or not robbing the root
    return max(solve(root))

# This solution works, but it re-computes results for the same nodes multiple times
# if they are accessed through different paths in a more complex graph,
# though for a simple tree, it is just an inefficient traversal.
# The memoized version explicitly prevents re-computation.

Approach 2: Memoization (Top-Down DP)

The recursive solution is correct but can be inefficient because it might re-compute the results for the same node if the tree structure were more complex (like a graph with shared nodes). We can optimize this by storing the result for each node once we compute it. A dictionary is perfect for this, mapping a node object to its (rob, dont_rob) tuple.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        memo = {} # Use a dictionary for memoization

        def solve(node):
            if not node:
                return (0, 0)
            if node in memo:
                return memo[node]

            left_rob, left_dont_rob = solve(node.left)
            right_rob, right_dont_rob = solve(node.right)

            profit_if_rob = node.val + left_dont_rob + right_dont_rob
            profit_if_dont_rob = max(left_rob, left_dont_rob) + max(right_rob, right_dont_rob)

            memo[node] = (profit_if_rob, profit_if_dont_rob)
            return memo[node]

        return max(solve(root))

# Trying it out
# This is the standard and efficient way to solve DP on trees.

This memoized, top-down DP approach is the most common and intuitive way to solve this type of problem. Its time complexity is O(n), where n is the number of nodes, because solve is called exactly once for each node.

Conclusion

"House Robber III" is the perfect introduction to dynamic programming on trees. It forces a crucial shift in thinking: the state passed up from a subproblem (a child) must be rich enough to allow the parent to make an informed decision. By having our recursive function return a tuple of choices (rob, dont_rob), we provided exactly that. This pattern of using richer return values is a cornerstone of solving DP problems on tree and graph structures.