Code Implementation

# 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: TreeNode) -> int:
        def helper(node):
            if not node:
                return (0, 0)
            left = helper(node.left)
            right = helper(node.right)
            rob_this = node.val + left[1] + right[1]
            not_rob_this = max(left) + max(right)
            return (rob_this, not_rob_this)
        return max(helper(root))
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    pair helper(TreeNode* node) {
        if (!node) return {0, 0};
        auto left = helper(node->left);
        auto right = helper(node->right);
        int rob_this = node->val + left.second + right.second;
        int not_rob_this = max(left.first, left.second) + max(right.first, right.second);
        return {rob_this, not_rob_this};
    }
    int rob(TreeNode* root) {
        auto res = helper(root);
        return max(res.first, res.second);
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int rob(TreeNode root) {
        int[] res = helper(root);
        return Math.max(res[0], res[1]);
    }

    private int[] helper(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = helper(node.left);
        int[] right = helper(node.right);
        int rob_this = node.val + left[1] + right[1];
        int not_rob_this = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob_this, not_rob_this};
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var rob = function(root) {
    function helper(node) {
        if (!node) return [0, 0];
        const left = helper(node.left);
        const right = helper(node.right);
        const rob_this = node.val + left[1] + right[1];
        const not_rob_this = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [rob_this, not_rob_this];
    }
    const res = helper(root);
    return Math.max(res[0], res[1]);
};
      

Problem Description

You are given the root node of a binary tree, where each node contains a non-negative integer value representing the amount of money stored in that house. The constraint is that if you rob a house (i.e., a node), you cannot rob its immediate children (left or right child nodes), because the police will be alerted.

Your task is to determine the maximum amount of money you can rob from the binary tree of houses without ever robbing two directly-linked houses. You must return a single integer representing this maximum sum.

• You cannot rob both a parent and its child node.
• Each node can only be considered once.
• There is always at least one node in the tree.

Thought Process

At first glance, this problem seems similar to the classic House Robber problem, but with a twist: instead of a linear array of houses, the houses are organized in a binary tree. In the linear case, you can use dynamic programming by considering whether to rob or skip each house based on previous choices.

For the tree version, you must account for the fact that robbing a node prevents you from robbing its immediate children, but not its grandchildren. A brute-force approach would be to try all possible combinations of robbing or skipping each node, but this quickly becomes inefficient as the tree grows.

The key insight is to use recursion and, at each node, to keep track of two scenarios:

• The maximum amount if you rob this node (which means you cannot rob its children).
• The maximum amount if you do not rob this node (which means you can choose to rob or not rob its children).

Solution Approach

• Recursive Strategy:
  • For each node, calculate two values:
    • rob_this: The maximum money you can get if you rob this node. In this case, you cannot rob its immediate children, but you can consider robbing its grandchildren.
    • not_rob_this: The maximum money you can get if you do not rob this node. Here, you are free to rob or not rob its children (take the maximum for each child).
• Recursive Helper Function:
  • Write a helper function that returns a tuple or array for each node: [rob_this, not_rob_this].
  • For the base case, if the node is null, return [0, 0].
  • For each non-null node, recursively call the helper on its left and right children to get their rob/not_rob values.
  • Compute:
    • rob_this = node.val + left[1] + right[1]
    • not_rob_this = max(left) + max(right)
• Final Step:
  • For the root node, return the maximum of rob_this and not_rob_this.

This approach ensures that at each node, you make the optimal decision based on the results of its subtrees, and you never recompute the same subproblem.

Example Walkthrough

Consider the following binary tree:

        3
       / \
      2   3
       \   \
        3   1
  

Let's trace the solution step by step:

• Leaf Nodes:
  • The rightmost leaf node with value 3 (left child of left subtree) and node with value 1 (right child of right subtree) both have no children, so:
    • rob_this = 3 or 1 (just the node value)
    • not_rob_this = 0 (no children to rob)
• Node with value 2:
  • Left child is null, right child is 3 (from above).
  • rob_this = 2 + 0 (left child not_rob) + 0 (right child not_rob) = 2
  • not_rob_this = max(0, 0) + max(3, 0) = 3
• Node with value 3 (right child of root):
  • Left child is null, right child is 1 (from above).
  • rob_this = 3 + 0 + 0 = 3
  • not_rob_this = max(0, 0) + max(1, 0) = 1
• Root node (value 3):
  • rob_this = 3 + 3 (left not_rob) + 1 (right not_rob) = 7
  • not_rob_this = max(2, 3) + max(3, 1) = 3 + 3 = 6
• Final Answer: max(7, 6) = 7

So, the maximum amount of money that can be robbed is 7.

Time and Space Complexity

• Brute-force Approach:
  • If you tried every possible combination of robbing or not robbing each node, the time complexity would be exponential, specifically O(2^n) for n nodes, since each node has two choices.
• Optimized Approach (Dynamic Programming on Trees):
  • Each node is only visited once, and at each node, only a constant amount of work is done (calculating two values and combining results from children).
  • Time Complexity: O(n), where n is the number of nodes in the tree.
  • Space Complexity: O(h), where h is the height of the tree, due to the recursion stack. In the worst case (skewed tree), h = n.

Summary

The House Robber III problem extends the classic dynamic programming paradigm to binary trees. By breaking the problem down into two scenarios at each node (rob or not rob), and propagating optimal results up from the leaves, we avoid redundant computations and achieve an efficient O(n) solution. The elegance of this approach lies in its simplicity and its adaptation of dynamic programming to tree structures, making it both efficient and easy to understand.