Introduction

House Robber III is the most popular Tree DP interview problem.

You are given:

Binary Tree

Goal:

Maximize money robbed.

Constraint:

Cannot rob parent and child together.

Example

        3       / \
      2   3
       \   \
        3   1

Output:

7

Explanation:

3 + 3 + 1 = 7

Key Observation

For every node:

Rob Current Node or Skip Current Node

DP State

rob = Maximum money if current node is robbednotRob = Maximum money if current node is not robbed

Transition

rob = node.val + left.notRob + right.notRobnotRob = max(left.rob, left.notRob) + max(right.rob, right.notRob)

Dry Run

Input:

        3       / \
      2   3
       \   \
        3   1

Rob:

3 + 3 + 1

Answer:

7

Approach : DFS + Tree DP

Explanation

For every node:

  1. Solve left subtree.
  2. Solve right subtree.
  3. Calculate rob state.
  4. Calculate notRob state.
  5. Return both states.

Practice

Complexity Analysis

DFS + Tree DP
Time Complexity: O(n)
Space Complexity: O(h)
where h = tree height

Why This Problem is Important

  • Tree DP
  • DFS + DP
  • Include Exclude Pattern
  • Binary Tree Traversal
  • State Compression

Common Beginner Mistakes

  • Robbing parent and child together
  • Using global variables
  • Missing notRob state
  • Incorrect DFS order
  • Not returning both states

Interview Tip

Always explain:

For every node:Rob or Not Rob

Maintain both states and return them from DFS.

Related Questions

  • Binary Tree Maximum Path Sum
  • Diameter of Binary Tree
  • Path Sum III
  • Tree DP Problems

Final Takeaway

House Robber III is the foundation of Tree DP.

It teaches:

  • Tree Dynamic Programming
  • DFS States
  • Include Exclude Pattern
  • State Compression

Mastering House Robber III makes advanced Tree DP interview questions significantly easier.