Tree: Depth-First Search - House Robber III (On Tree)
Given the following tree and the optimal House Robber III code, what is the maximum amount that can be robbed?
3
/ \
2 3
\ \
3 1
Given the following tree and the optimal House Robber III code, what is the maximum amount that can be robbed? 3 / \ 2 3 \ \ 3 1
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace dfs on leaf nodes
Leaf 3 returns (3,0), leaf 1 returns (1,0).Step 2: Compute values for internal nodes
Node 2: rob=2+0+0=2, not_rob=max(3,0)+0=3; Node 3 (right): rob=3+0+0=3, not_rob=max(0,1)=1.Step 3: Compute root
Root 3: rob=3+3(not_rob left)+1(not_rob right)=7, not_rob=max(2,3)+max(3,1)=3+3=6.Final Answer:
Option D -> Option DQuick Check:
Maximum is robbing root plus grandchildren = 7 [OK]
Quick Trick: Robbing root plus grandchildren yields max sum [OK]
Common Mistakes:
MISTAKES- Forgetting to add grandchildren when robbing current node
Trap Explanation:
PITFALL- Candidates often sum children values directly, missing grandchildren sums when robbing current node.
Interviewer Note:
CONTEXT- Tests ability to mentally execute DP on tree
Master "House Robber III (On Tree)" in Tree: Depth-First Search
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Tree: Depth-First Search Quizzes