House Robber 3 - Houses in Binary Tree

Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

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

Examples

Example 1:

graph TD;
	C(3):::robbed --- B(2) & C1(3)

	B ~~~ N1:::hidden
	B --- C2(3):::robbed 
	
	C1(3) ~~~ N2:::hidden
	C1 --- A(1):::robbed 

classDef hidden display: none;
classDef robbed stroke:#f66,stroke-width:2px

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Solution

Method 1 - DFS

Since this is a binary tree, we can traverse it recursively using post-order traversal and calculate the maximum amount of money the thief can rob for each subtree - when. a root is robbed and when it is not selected.

Approach:

Use post-order traversal (left → right → root):
- Calculate the maximum loot for the left and right children recursively.
- For each node, two scenarios are possible:
  1. Node is robbed: In this case, the thief cannot rob the children of this node. The amount will be node.val + max(left child when not robbed) + max(right child when not robbed).
  2. Node is not robbed: The thief can rob its children. The amount will be max(left child when robbed, left child when not robbed) + max(right child when robbed, right child when not robbed).
Use a helper function that returns two values for each node:
- The first is the maximum loot when the current node is not robbed.
- The second is the maximum loot when the current node is robbed.
Finally, at the root, return the maximum of these two values.

Code

Java

class Solution {
    public int rob(TreeNode root) {
        int[] ans = dfs(root);
        return Math.max(ans[0], ans[1]);
    }
    
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[] {0, 0}; // {not_robbed, robbed}
        }
        
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        
        // If the current node is not robbed, take the max of its children
        int notRobbed = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        // If the current node is robbed, only add its value plus children not being robbed
        int robbed = node.val + left[0] + right[0];
        
        return new int[] {notRobbed, robbed};
    }
}

Python

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        
        def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
            if not node:
                return (0, 0)  # (not_robbed, robbed)
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # If the current node is not robbed, take the max of children
            not_robbed = max(left) + max(right)
            
            # If the current node is robbed, add its value to children not being robbed
            robbed = node.val + left[0] + right[0]
            
            return (not_robbed, robbed)
        
        # Get max of both cases for the root
        ans = dfs(root)
        return max(ans)

Complexity

⏰ Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once.
🧺 Space complexity: O(h), where h is the height of the tree. This is due to the recursion stack.