NUHMAN.com

Introduction

LeetCode 337: House Robber III is a problem in which you need to determine the maximum amount of money you can rob from a binary tree of houses. The houses are represented as nodes in a binary tree, and you cannot rob two directly linked houses. This means you cannot rob both a parent and its immediate child.

The goal is to maximize the sum of money you can rob without robbing two directly connected houses.

This problem can be solved using dynamic programming (DP) on trees by using recursion and memoization to store results of subproblems to avoid redundant calculations.

Problem Statement

In a binary tree, each node represents a house with a certain amount of money, and you need to find the maximum amount of money you can rob such that no two directly connected houses are robbed.

Note:

• A node represents a house with some amount of money.
• You cannot rob a parent and its child simultaneously.

Example

python

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Robbing the root node (3) and the right child (3) is the optimal solution, which yields 7.

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Robbing the root node (3), the left child (4), and the right child's right child (1) gives the maximum amount of 9.

Approach: Dynamic Programming on Trees

The idea is to use a bottom-up approach with recursion to solve this problem. For each node in the tree, we need to determine:

1. Maximum money if we rob this node.
2. Maximum money if we do not rob this node.

To calculate the maximum value we can rob from each node, we define two states for each node:

• Robbed: The maximum amount if we rob the current node.
• Not Robbed: The maximum amount if we do not rob the current node.

At each node, we have two choices:

• Rob the node: If we rob the current node, we cannot rob its children. Thus, the total amount will be the value of the node plus the sum of the "not robbed" values of its left and right children.
• Do not rob the node: If we skip the current node, the total amount will be the sum of the maximum values from the left and right children.

Key Idea:

• Use recursion to calculate these two states for each node.
• Use memoization to store results and avoid recalculating for the same nodes.

✅ Python Code

python

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return (0, 0)  # (robbed, not robbed)
            
            left_rob, left_not_rob = dfs(node.left)  # Recurse on left child
            right_rob, right_not_rob = dfs(node.right)  # Recurse on right child
            
            # If we rob this node, we cannot rob its children
            robbed = node.val + left_not_rob + right_not_rob
            
            # If we do not rob this node, we take the maximum from robbing or not robbing its children
            not_robbed = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)
            
            return (robbed, not_robbed)

        robbed, not_robbed = dfs(root)
        return max(robbed, not_robbed)

🧪 Dry Run Example

Input: root = [3,2,3,null,3,null,1]

1. Initial Setup: The binary tree is as follows:

markdown

     3
    / \
   2   3
    \   \
     3   1

1. DFS Traversal:

• For node 3 (root):
• Left child (2):
• Left child is null: Return (0, 0) (both robbed and not robbed are 0).
• Right child (3):
• Left and right children are null: Return (0, 0).
• Robbed value: 3 + 0 + 0 = 3.
• Not robbed value: max(0, 0) + max(0, 0) = 0.
• Return (3, 0).
• Robbed value: 2 + 0 + 3 = 5.
• Not robbed value: max(0, 0) + max(3, 0) = 3.
• Return (5, 3).
• Right child (3):
• Left child is null: Return (0, 0).
• Right child (1):
• Left and right children are null: Return (0, 0).
• Robbed value: 1 + 0 + 0 = 1.
• Not robbed value: max(0, 0) + max(0, 0) = 0.
• Return (1, 0).
• Robbed value: 3 + 0 + 0 = 3.
• Not robbed value: max(0, 0) + max(1, 0) = 1.
• Return (3, 1).

1. Final Calculation:

• Robbed value for root: 3 + 3 + 1 = 7.
• Not robbed value for root: max(5, 3) + max(3, 1) = 8.

1. The maximum value between robbed and not robbed at the root is max(7, 8) = 7.

Output: 7

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(n)

• n is the number of nodes in the binary tree.
• We traverse each node once using DFS, leading to O(n) time complexity.
• The space complexity is O(n) due to the recursion stack, and we also store results for subproblems.

🧠 Key Takeaways

• This problem demonstrates dynamic programming applied to trees, where you can store the results of subproblems (the maximum values for robbed and not robbed states) to avoid redundant calculations.
• DFS traversal is combined with memoization to solve the problem efficiently.
• The problem is a variation of the classic House Robber problem, but applied to a binary tree structure.

🧱 Edge Cases

• Empty tree: If the tree is empty (root = None), return 0.
• Single node: If there is only one node, the maximum sum is the value of that node.
• Unbalanced tree: The algorithm works for both balanced and unbalanced trees due to its recursive nature.

✅ Conclusion

LeetCode 337: House Robber III is a great problem for practicing dynamic programming on trees. By using DFS and memoization to track the maximum amount of money you can rob from each node, we can efficiently solve the problem in O(n) time and O(n) space. This solution avoids unnecessary recalculations and handles both balanced and unbalanced trees.