Bird
Raised Fist0

The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium🐞 Bug Identification Q14 of Q15
Tree: Depth-First Search - House Robber III (On Tree)
The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.
ALine 5: rob_current calculation uses left[0] and right[0]
BLine 7: Returning (rob_current, not_rob_current)
CLine 6: not_rob_current uses max(left) + max(right)
DLine 2: Base case returns (0, 0)
Step-by-Step Solution

  1. Step 1: Understand rob_current calculation

    rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

  2. Step 2: Identify the bug

    Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Using rob values of children overcounts and breaks correctness [OK]
Quick Trick: Rob current node + not_rob children, not rob children [OK]
Common Mistakes:
MISTAKES
  • Mixing rob and not_rob indices in tuple
  • Forgetting adjacency constraints
Trap Explanation:
PITFALL
  • Using rob values of children looks plausible but breaks the no-adjacent rule.
Interviewer Note:
CONTEXT
  • Tests if candidate can spot subtle DP state misuse causing incorrect aggregation.
Master "House Robber III (On Tree)" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes
Balanced Binary Tree - Balanced Binary Tree - Quiz 4medium Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 6medium Binary Tree Maximum Path Sum - Binary Tree Maximum Path Sum - Quiz 8hard Construct Tree from Inorder and Postorder - Construct Tree from Inorder and Postorder - Quiz 13medium Diameter of Binary Tree - Diameter of Binary Tree - Quiz 10hard Path Sum - Path Sum - Quiz 5medium Path Sum II (All Root-to-Leaf Paths) - Path Sum II (All Root-to-Leaf Paths) - Quiz 6medium Path Sum III (Any Path) - Path Sum III (Any Path) - Quiz 15hard Path Sum III (Any Path) - Path Sum III (Any Path) - Quiz 6medium Path Sum III (Any Path) - Path Sum III (Any Path) - Quiz 14medium