House Robber III

House Robber III

What is this problem about?

The House Robber III coding problem moves the heist from a street to a binary tree. Each node in the tree represents a house with a certain amount of money. The constraint remains: you cannot rob two houses that are directly connected (parent and child). You need to find the maximum amount of money you can collect.

Why is this asked in interviews?

This is a high-signal problem asked by Salesforce, Google, and Microsoft because it combines Binary Tree traversal with Dynamic Programming. It evaluates whether you can manage state across recursive calls. Unlike linear DP, tree-based DP requires you to return multiple pieces of information from each sub-problem (e.g., "the result if I rob this node" vs. "the result if I don't").

Algorithmic pattern used

The problem is solved using DFS (Post-order Traversal) with a Dynamic Programming state. Each recursive call returns a pair of values: [rob_current, skip_current].

1. rob_current: The value of the current node plus the skip_current values from both children.
2. skip_current: The maximum of (rob or skip) from the left child plus the maximum of (rob or skip) from the right child. By processing the tree from the bottom up, you build the optimal solution for the root.

Example explanation

Tree:

    3
   / 
  2   3
   \   
    3   1

1. Leaves (3 and 1) return [3, 0] and [1, 0].
2. Node 2 (left) receives [3, 0] from its child.
   • rob_2 = 2 + 0 = 2.
   • skip_2 = max(3, 0) = 3.
   • Returns [2, 3].
3. Node 3 (right) receives [1, 0] from its child.
   • rob_3 = 3 + 0 = 3.
   • skip_3 = max(1, 0) = 1.
   • Returns [3, 1].
4. Root 3 receives [2, 3] and [3, 1].
   • rob_root = 3 + 3 (skip_left) + 1 (skip_right) = 7.
   • skip_root = max(2, 3) + max(3, 1) = 3 + 3 = 6. Result: 7.

Common mistakes candidates make

• Redundant Recursion: Writing a naive solution that calls the function multiple times for the same node, leading to exponential $O(2^n)$ time.
• Failing to use memoization: Not realizing that returning a pair of values effectively implements DP in a single pass.
• State Confusion: Only returning the max value, which makes it impossible for the parent to know if it can safely rob itself.

Interview preparation tip

Practice returning arrays or custom objects from recursive functions in trees. This "Bottom-Up state passing" is the standard way to solve complex tree optimizations.