Rob Houses in a Binary Tree

Problem Description

You are a thief planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were robbed on the same night.

Given the root of a binary tree, where each node represents a house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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

Example 2:

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

Naive Solution (Brute Force with Recursion)

A straightforward approach is to consider each node and recursively explore two possibilities:

1. Rob the current node: If we rob the current node, we cannot rob its children.
2. Don't rob the current node: If we don't rob the current node, we can rob its children.

We recursively calculate the maximum amount we can rob in each case and return the maximum of the two.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob_naive(root: TreeNode) -> int:
    if not root:
        return 0

    # Rob the current node
    rob_current = root.val
    if root.left:
        rob_current += rob_naive(root.left.left) + rob_naive(root.left.right)
    if root.right:
        rob_current += rob_naive(root.right.left) + rob_naive(root.right.right)

    # Don't rob the current node
    skip_current = rob_naive(root.left) + rob_naive(root.right)

    return max(rob_current, skip_current)

Time Complexity: O(2^N), where N is the number of nodes in the tree. This is because, in the worst case, we explore all possible combinations of robbing/not robbing nodes.

Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), H = N, so the space complexity can be O(N).

Optimal Solution (Dynamic Programming with Recursion)

The naive solution has exponential time complexity due to overlapping subproblems. We can optimize it using dynamic programming (memoization).

Instead of recalculating the maximum robbery amount for each subtree multiple times, we can store the results in a dictionary (or a similar data structure) and reuse them when needed.

We can modify the recursive function to return two values: the maximum amount we can rob if we rob the current node and the maximum amount if we don't rob the current node.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root: TreeNode) -> int:
    def rob_helper(node):
        if not node:
            return (0, 0)  # (rob_node, skip_node)

        left_rob, left_skip = rob_helper(node.left)
        right_rob, right_skip = rob_helper(node.right)

        # If we rob the current node, we cannot rob its children
        rob_node = node.val + left_skip + right_skip

        # If we don't rob the current node, we can rob its children or not
        skip_node = max(left_rob, left_skip) + max(right_rob, right_skip)

        return (rob_node, skip_node)

    rob_result, skip_result = rob_helper(root)
    return max(rob_result, skip_result)

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.

Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), H = N, so the space complexity can be O(N).

Edge Cases

• Empty Tree: If the input tree is empty (root is None), the maximum amount we can rob is 0.
• Single Node: If the tree has only one node, the maximum amount we can rob is the value of that node.
• Skewed Tree: The height of the tree can be equal to the number of nodes in the case of a skewed tree, which affects the space complexity of the recursive solution.