We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

House Robber III

Number: 337

Difficulty: Medium

Paid? No

Companies: Amazon, Google, TikTok, Meta, PhonePe, LinkedIn, Adobe, Microsoft, Uber

Problem Description

Given the root of a binary tree where each node represents a house with some amount of money, determine the maximum amount of money the thief can rob without alerting the police. The thief cannot rob two directly-linked houses (i.e., parent and child) on the same night.

Key Insights

  • The problem is modeled on a binary tree where each node represents a house.
  • If a node is robbed, its immediate children cannot be robbed.
  • Using DFS (Depth First Search) allows us to explore the tree and decide for each node whether to rob it or not.
  • At each node, compute two values: one when the node is robbed and one when it is not.
  • The optimal solution at each node is derived by considering the maximum money collected from its subtrees, taking the constraints into account.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, as each node is visited once. Space Complexity: O(n) due to the recursion call stack in the worst-case skewed tree.

Solution

We use a DFS-based recursive strategy to solve the problem. For each node, compute two scenarios:

  1. Robbing the current node: In this case, we cannot rob its children. So, the value is node.val plus the sum of values from not robbing its left and right children.
  2. Not robbing the current node: In this case, we can rob or not rob its children based on which option yields more money from each subtree. By returning these two values (rob, notRob) for each node and combining them from the bottom-up, the solution picks the optimal strategy at the root. Key data structures include recursion (function call stack) and tuples/pairs to maintain the two states per node.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # value of the node (money in the house)
        self.left = left     # left child
        self.right = right   # right child

def rob(root: TreeNode) -> int:
    # Returns a tuple (rob, notRob) representing:
    # rob -> maximum money when this node is robbed
    # notRob -> maximum money when this node is not robbed
    def dfs(node):
        if not node:
            return (0, 0)
        left = dfs(node.left)
        right = dfs(node.right)
        # If we rob this node, we cannot rob its children
        rob_current = node.val + left[1] + right[1]
        # If we do not rob this node, choose the max for each child independently
        not_rob_current = max(left) + max(right)
        return (rob_current, not_rob_current)
    
    return max(dfs(root))
    
# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output should be 7
← Back to All Questions