House Robber III

Medium

Google

3 views

Topics:

TreesRecursionDynamic Programming

You are a thief planning to rob houses along a street. However, these houses are arranged in a binary tree structure, where each node represents a house, and the value of the node is the amount of money in that house. There's a catch: you cannot rob two directly linked houses because the alarm system will be triggered. Your goal is to maximize the total amount of money you can rob without setting off the alarm.

Details:

You are given the root node of a binary tree where each node has a non-negative value representing the amount of money in that house.
You can only access the tree through the root node.
If you rob a house (node), you cannot rob its immediate children (left and right children).
Your task is to determine the maximum amount of money you can rob without triggering the alarm.

Example 1:

Consider the following binary tree:

The maximum amount you can rob is 3 (root) + 3 (right-child's right-child) + 1 (right-child's right-child) = 7.

Example 2:

Consider the following binary tree:

The maximum amount you can rob is 4 (left-child) + 5 (right-child) = 9.

Write a function that takes the root of the binary tree as input and returns the maximum amount of money the thief can rob without alerting the police.

House Robber III

Medium

Google

3 views

Topics:

TreesRecursionDynamic Programming

You are a thief planning to rob houses along a street. However, these houses are arranged in a binary tree structure, where each node represents a house, and the value of the node is the amount of money in that house. There's a catch: you cannot rob two directly linked houses because the alarm system will be triggered. Your goal is to maximize the total amount of money you can rob without setting off the alarm.

Details:

You are given the root node of a binary tree where each node has a non-negative value representing the amount of money in that house.
You can only access the tree through the root node.
If you rob a house (node), you cannot rob its immediate children (left and right children).
Your task is to determine the maximum amount of money you can rob without triggering the alarm.

Example 1:

Consider the following binary tree:

The maximum amount you can rob is 3 (root) + 3 (right-child's right-child) + 1 (right-child's right-child) = 7.

Example 2:

Consider the following binary tree:

The maximum amount you can rob is 4 (left-child) + 5 (right-child) = 9.

Write a function that takes the root of the binary tree as input and returns the maximum amount of money the thief can rob without alerting the police.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values of the nodes be negative, zero, or only positive?
What is the structure of the tree? Is it guaranteed to be a binary tree, or could it be a more general tree structure?
Could the root node be null, representing an empty tree? If so, what should the function return?
If a node is robbed, can we still rob its descendants, as long as its immediate children are not robbed?
What is the maximum number of nodes that the tree could contain?

Brute Force Solution

Approach

We are trying to find the most money you can steal from houses arranged in a tree structure, where you can't rob adjacent houses. The brute force way involves checking every single possible combination of houses you could rob.

Here's how the algorithm would work step-by-step:

Consider robbing the root house.
If you rob the root house, then you cannot rob its immediate children (the houses directly connected to it).
For the houses below the children, try all possible combinations of robbing or not robbing them.
Now, consider NOT robbing the root house.
If you don't rob the root house, then you CAN rob its immediate children.
For each child, decide whether to rob it or not.
If you rob a child, you cannot rob its children.
If you don't rob a child, you can consider robbing its children.
Keep exploring all possible combinations of robbing and not robbing houses further down the tree.
For each combination of robbed houses, calculate the total amount of money you would get.
After exploring every single possible combination, pick the one that gives you the most money.

Code Implementation

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

def house_robber_brute_force(root):
    def rob_or_not_rob(current_node):
        # If the node is empty, return 0
        if not current_node:
            return 0

        # Case 1: Rob the current node
        money_if_robbed = current_node.val

        # If we rob the current node, we can't rob its children.
        if current_node.left:
            money_if_robbed += rob_or_not_rob_children(current_node.left, False) 

        if current_node.right:
            money_if_robbed += rob_or_not_rob_children(current_node.right, False)

        # Case 2: Don't rob the current node
        money_if_not_robbed = 0

        # If we don't rob the current node, we can rob its children.
        if current_node.left:
            money_if_not_robbed += rob_or_not_rob_children(current_node.left, True)

        if current_node.right:
            money_if_not_robbed += rob_or_not_rob_children(current_node.right, True)

        return max(money_if_robbed, money_if_not_robbed)

    def rob_or_not_rob_children(current_node, can_rob):
        if not current_node:
            return 0

        if can_rob:
            return rob_or_not_rob(current_node)
        else:
            # When we can't rob, we have to skip and recurse.
            money_if_not_robbed = 0

            if current_node.left:
                money_if_not_robbed += rob_or_not_rob_children(current_node.left, True)

            if current_node.right:
                money_if_not_robbed += rob_or_not_rob_children(current_node.right, True)
            return money_if_not_robbed

    return rob_or_not_rob(root)

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores every possible combination of robbing or not robbing each house in the tree. Since each house has two choices (rob or don't rob), and there are n houses in the tree, this results in 2^n possible combinations. The algorithm effectively enumerates each of these combinations. Therefore, the time complexity is O(2^n), where n is the number of nodes (houses) in the tree.

Space Complexity

O(N) – The algorithm's space complexity is primarily determined by the depth of the recursion stack. In the worst-case scenario, where the tree resembles a linked list, the recursive calls will stack up to a depth of N, where N is the number of nodes in the tree. Each recursive call requires a stack frame to store local variables and the return address. Therefore, the auxiliary space required scales linearly with the number of nodes in the tree, resulting in O(N) space complexity.

Optimal Solution

Approach

This problem asks us to find the maximum amount we can rob from houses arranged like a tree, where robbing adjacent houses sets off an alarm. The clever approach avoids redundant calculations by figuring out the best outcome for each house considering two options: robbing it, or skipping it.

Here's how the algorithm would work step-by-step:

Think about each house and consider two possibilities: either you rob it, or you don't.
If you rob a house, you can't rob its immediate children (houses directly connected below it). Instead, you have to take the best outcome from their children (grandchildren of the current house).
If you don't rob a house, you *can* rob its immediate children. In this case, you choose the best possible outcome by robbing or not robbing each of them.
For each house, remember these two best outcomes: the best if you rob it, and the best if you don't. Store this information so you don't have to recalculate it later.
Start from the bottom of the tree (the houses with no children) and work your way up. For each house, decide whether robbing it or not robbing it gives you the maximum amount, using the already calculated best outcomes from its children.
The final answer is at the very top of the tree (the root house). Pick the larger value between robbing the root and not robbing the root. This will be the maximum amount you can rob without setting off any alarms.

Code Implementation

def house_robber_iii(root):
    def rob_sub_tree(node):
        if not node:
            return (0, 0)

        # Recursively calculate for left and right subtrees
        money_from_left = rob_sub_tree(node.left)
        money_from_right = rob_sub_tree(node.right)

        # If we rob the current node, we cannot rob its children
        rob_current = node.val + money_from_left[1] + money_from_right[1]

        # If we don't rob the current node, we can rob its children or not
        skip_current = max(money_from_left) + max(money_from_right)

        return (rob_current, skip_current)

    # Return the maximum value between robbing the root and skipping it
    return max(rob_sub_tree(root))

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

# Example usage (for testing, not part of the core solution)
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(house_robber_iii(root))

# root = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(3)), TreeNode(5, None, TreeNode(1)))
# print(house_robber_iii(root))

# This dictionary stores the results of subproblems
# to avoid redundant calculations.

# For each node, we calculate two values: the max
# loot if we rob the node, and the max loot if we skip it.

# We start from the bottom and go up, making decisions
# at each node based on the values calculated for its children.

Big(O) Analysis

Time Complexity

O(n) – The provided solution uses a depth-first traversal (implicitly through recursion) to visit each node (house) in the tree exactly once. At each node, a constant amount of work is performed to calculate the maximum robbery amount, considering both robbing and not robbing the current house. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which is represented by n. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm stores the best outcomes (robbing and not robbing) for each house. This information is stored to avoid recalculations. Since there are N houses in the tree, we potentially store two values (rob, not rob) for each, leading to auxiliary space proportional to the number of nodes, N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 if the root is null, representing no houses to rob.
Single node tree	Return the value of the root node, as that's the only house to rob.
Tree with all zero values	The algorithm should correctly return 0, as there's no profit to be made.
Unbalanced tree (highly skewed to left or right)	Ensure the recursion depth doesn't exceed reasonable limits to prevent stack overflow.
Tree with negative values (hypothetically, a house that costs you to rob)	The algorithm should still function correctly by choosing the path that maximizes the sum, even if that means avoiding negative values.
Large tree with potential integer overflow (sum exceeds maximum integer value)	Consider using a larger data type (e.g., long) or modular arithmetic to prevent overflow if the house values can be large.
Tree with a deep and narrow structure that leads to high call stack usage	Memoization or dynamic programming is important to improve the time complexity and prevent stack overflow errors.
Tree where robbing the root provides no benefit because its children provide more value	The algorithm must correctly explore both robbing the root and not robbing the root to find the optimal solution.