Domain 2MediumCORE

House Robber III

We are given the root of a binary tree where each node represents a house containing a certain amount of money (Node.val). We need to determine the maximum total value we can steal without triggering an alarm. An alarm triggers if two directly linked houses (parent and child) are both robbed on the same night.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Tree#Depth-first Search

337. House Robber III

Model: qwen3.5:9b
Topics: Dynamic Programming,Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 52.0%


Problem Breakdown

We are given the root of a binary tree where each node represents a house containing a certain amount of money (Node.val). We need to determine the maximum total value we can steal without triggering an alarm. An alarm triggers if two directly linked houses (parent and child) are both robbed on the same night.

Inputs:

  • root: The root node of a binary tree where each node has a non-negative integer value representing money.

Outputs:

  • A single integer: The maximum amount of money that can be robbed without alerting the police.

Constraints & Edge Cases:

  • Number of nodes is between 1 and 10410^4.
  • Node values are ≥0\ge 0 (no negative numbers).
  • Implicit Constraint: We cannot select a node if its parent or child was selected in the same path decision chain. This creates dependencies that propagate up from leaves to root.

Intuition

A brute-force approach would try every possible subset of houses and check validity, which is exponential (O(2N)O(2^N)). Given 10410^4 nodes, this will time out immediately. We need a more efficient way to make decisions at each node based on its children’s status.

This problem exhibits overlapping subproblems typical of Dynamic Programming (DP), but applied to trees rather than arrays or DAGs.

  • If we rob the current house (u), we cannot rob its immediate children, but we can take whatever is optimal from their subtrees given that constraint.
  • If we do not rob u, there are no restrictions on its children; they can be robbed freely based on their own subtree logic.

Therefore, for any node in the tree, our recursive function needs to return two values:

  1. The max money if this specific node is robbed.
  2. The max money if this specific node is not robbed (skipped).

By returning both states up the call stack, we allow the parent to make an informed decision without needing a global cache for every possible state combination across different branches of the tree structure. Since it’s a standard binary tree with no cycles and each subtree is processed exactly once in post-order traversal, explicit memoization isn’t strictly necessary beyond returning these values; simple DFS suffices.

Approach

We will use Depth-First Search (DFS) traversing the tree bottom-up (post-order). For every node u, we calculate two scenarios:

  1. Rob Current Node: We add node.val to the max money obtained from skipping both children (left_skip + right_skip). Note that if we rob a child, its parent cannot be robbed; conversely, if we skip the current node’s value, we are free to take whatever is optimal in the subtrees.
  2. Skip Current Node: We do not add node.val. In this case, both children can contribute their maximum possible values regardless of whether they were robbed or skipped (since there is no adjacency restriction between a grandparent and grandchildren). So we sum max(left_robbed, left_skipped) + max(right_robbed, right_skipped).

The base case for recursion is when the node is null; in this scenario, both values are 0. The final answer will be the maximum of these two scenarios at the root.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes. We visit each node exactly once during the DFS traversal to compute its state and return it up the stack.
  • Space Complexity: O(H)O(H), where HH is the height of the tree (recursion call stack). In a balanced tree this is O(log⁡N)O(\log N); in a skewed line-like tree it degrades to O(N)O(N).

Solution

# Standard LeetCode TreeNode structure assumed available. 
# If running locally, ensure class definition matches:
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def rob(self, root: 'TreeNode') -> int:
        # Helper function returns a tuple (robbed_val, not_robbed_val) for the subtree rooted at node.
        def dfs(node):
            if not node:
                return 0, 0
            
            left = dfs(node.left)   # Tuple from left child
            right = dfs(node.right) # Tuple from right child
            
            l_rob, l_skip = left     # Unpack results for clarity in logic
            r_rob, r_skip = right
            
            # Scenario A: Rob current node. 
            # Cannot rob children directly (must take their 'skip' values).
            val_if_robbed = node.val + l_skip + r_skip
            
            # Scenario B: Skip current node.
            # Children are free to be robbed or skipped optimally within their own subtrees.
            val_if_skipped = max(l_rob, l_skip) + max(r_rob, r_skip)
            
            return (val_if_robbed, val_if_skipped)

        if not root:
            return 0
        
        # Get results for the root node and take the maximum of both scenarios.
        robbed_val, skipped_val = dfs(root)
        
        return max(robbed_val, skipped_val)

Edge Cases Handled

  • Empty Tree: The code checks if not root at entry (though constraints say N≥1N \ge 1, defensive coding is good). If null, returns 0.
  • Single Node: DFS recurses to children which return (0,0). Root calculates val + 0 + 0 vs max(0,0)+max(0,0) -> Returns val, correct max.
  • Deep Trees (Skewed): The recursion depth matches tree height. While Python has a default limit (~1000), LeetCode environments typically handle this or allow setting limits; the logic remains O(N)O(N) regardless of shape.