House Robber III

LeetCode 337: House Robber III Solution & Explanation

Problem Overview

TL;DR: The optimal LeetCode 337 solution utilizes a postorder depth-first search to propagate two values—the maximum loot including the current node and the maximum loot excluding it—up the tree.

In House Robber III, we are given a binary tree representing a neighborhood of houses. Each node contains a non-negative integer representing the amount of money in that house. The constraint is that if we rob a specific house (node), we cannot rob its direct parent or its direct children. We need to determine the maximum amount of money that can be stolen without triggering the alarm (i.e., without robbing two directly connected nodes).

This is a popular interview question that adapts the classic dynamic programming "House Robber" problem into a tree data structure context.

Brute Force Approach for House Robber III

The naive approach attempts to solve the problem using standard top-down recursion. For any given node, we have two primary choices:

1. Rob the current node: If we do this, we cannot rob its children (node.left and node.right). However, we are free to rob its grandchildren.
2. Skip the current node: If we do this, we are free to rob the children (though we don't have to; we take the maximum potential from the subtrees starting at the children).

The recurrence relation looks like this: rob(root) = max( root.val + rob(grandchildren), rob(children) )

Pseudo-code

function rob(node):
    if node is null: return 0
    
    val_with_node = node.val
    if node.left:
        val_with_node += rob(node.left.left) + rob(node.left.right)
    if node.right:
        val_with_node += rob(node.right.left) + rob(node.right.right)
        
    val_without_node = rob(node.left) + rob(node.right)
    
    return max(val_with_node, val_without_node)

Why this fails

This approach has an exponential time complexity. Specifically, rob(node) calls rob(node.left). Inside rob(node.left), it calculates values for its own children (the original node's grandchildren). However, the original call rob(node) also calls rob(grandchildren) directly. This results in massive re-calculation of the same subproblems. On a skewed tree or a full tree, this will result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

We implement a helper function dfs that performs a postorder traversal.

1. Base Case: If the current node is null, return [0, 0]. A null node contributes nothing whether robbed or not.
2. Recursive Step: Recursively call dfs on the left child and the right child. Let's denote the results as leftPair and rightPair.
3. Logic for "Robbing Current":
   • If we rob the current node, we strictly cannot rob the children.
   • Value = node.val + leftPair[1] + rightPair[1] (where index 1 represents the "without rob" value).
4. Logic for "Skipping Current":
   • If we skip the current node, we can choose to either rob or skip the children—whichever yields more money.
   • Value = max(leftPair[0], leftPair[1]) + max(rightPair[0], rightPair[1]).
5. Return: Return the new pair [rob_current, skip_current].

The final answer to the problem is the maximum of the two values returned by the dfs call on the root.

Execution Flow

Let's trace the algorithm with a simple tree: Root(3) -> Left(2), Right(3). Left(2) has no children. Right(3) has a child RightChild(1).

1. Call DFS(Root 3)
   • Call DFS(Left 2)
     • Left 2 is a leaf.
     • Rob 2: 2 + 0 + 0 = 2.
     • Skip 2: max(0,0) + max(0,0) = 0.
     • Returns [2, 0].
   • Call DFS(Right 3)
     • Call DFS(RightChild 1)
       • Leaf. Returns [1, 0].
     • Back at Right 3:
       • Rob 3: 3 + 0 (left null) + 0 (child skip) = 3.
       • Skip 3: 0 + max(1, 0) = 1.
       • Returns [3, 1].
   • Back at Root 3:
     • Rob 3: 3 + 0 (from Left[1]) + 1 (from Right[1]) = 4.
     • Skip 3: max(2, 0) + max(3, 1) = 2 + 3 = 5.
     • Returns [4, 5].
2. Final Result: max(4, 5) = 5.

Proof of Correctness

The correctness relies on the Optimal Substructure property.

• Base Case: For a null node, the return value [0, 0] is trivially correct.
• Inductive Step: Assume for any node u, the subtrees rooted at u.left and u.right correctly return the maximum values for the cases where the child is robbed or skipped.
  • To calculate the optimal value for u when robbed, we are forced to skip children. Since the children returned the optimal "skip" value, u.val + left.skip + right.skip is guaranteed to be optimal for this state.
  • To calculate the optimal value for u when skipped, we are free to choose the best outcome for each child. Since max(child.rob, child.skip) represents the global maximum for that subtree, summing these for left and right guarantees the optimal value for u in the "skip" state.
• Since the tree is finite and acyclic, this logic propagates to the root, ensuring the global maximum is found.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern used in LeetCode 337 is highly versatile. It is the standard approach for problems where a node's value depends on aggregating results from its subtrees.

• LeetCode 104: Maximum Depth of Binary Tree: Uses postorder traversal to pass depth d up to the parent, which computes max(left_d, right_d) + 1.
• LeetCode 110: Balanced Binary Tree: Returns height information bottom-up while simultaneously checking the balance condition.
• LeetCode 124: Binary Tree Maximum Path Sum: Calculates the maximum path extending downwards from children to compute the max path splitting at the current node.
• LeetCode 145: Binary Tree Postorder Traversal: The fundamental traversal mechanism used in all these solutions.

Reference Implementation

C++ Solution for LeetCode 337

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int rob(TreeNode* root) {
15        pair<int, int> result = dfs(root);
16        return max(result.first, result.second);
17    }
18
19private:
20    // Returns a pair: {max money if we rob root, max money if we DO NOT rob root}
21    pair<int, int> dfs(TreeNode* node) {
22        if (!node) {
23            return {0, 0};
24        }
25
26        pair<int, int> left = dfs(node->left);
27        pair<int, int> right = dfs(node->right);
28
29        // Option 1: Rob current node. Cannot rob children.
30        int robCurrent = node->val + left.second + right.second;
31
32        // Option 2: Do not rob current node. Can choose max of children.
33        int skipCurrent = max(left.first, left.second) + max(right.first, right.second);
34
35        return {robCurrent, skipCurrent};
36    }
37};

Java Solution for LeetCode 337

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public int rob(TreeNode root) {
18        int[] result = dfs(root);
19        return Math.max(result[0], result[1]);
20    }
21
22    // Returns int[2]: index 0 = rob current, index 1 = skip current
23    private int[] dfs(TreeNode node) {
24        if (node == null) {
25            return new int[]{0, 0};
26        }
27
28        int[] left = dfs(node.left);
29        int[] right = dfs(node.right);
30
31        // If we rob this node, we add its value to the "skip" values of children
32        int robCurrent = node.val + left[1] + right[1];
33
34        // If we skip this node, we take the max possible value from each child
35        int skipCurrent = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
36
37        return new int[]{robCurrent, skipCurrent};
38    }
39}

Python Solution for LeetCode 337

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def rob(self, root: Optional[TreeNode]) -> int:
9        # Returns tuple: (rob_root, skip_root)
10        def dfs(node):
11            if not node:
12                return (0, 0)
13            
14            left_rob, left_skip = dfs(node.left)
15            right_rob, right_skip = dfs(node.right)
16            
17            # If we rob current, we must skip children
18            rob_current = node.val + left_skip + right_skip
19            
20            # If we skip current, we take max of children's options
21            skip_current = max(left_rob, left_skip) + max(right_rob, right_skip)
22            
23            return (rob_current, skip_current)
24
25        result = dfs(root)
26        return max(result)