House Robber III

MediumDynamic Programmingtree dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

The houses in a neighborhood are arranged as a binary tree, with root as the entrance. Each node's value is the amount of money in that house. You may choose any set of houses to rob, but you may never rob two houses that are **directly connected**, meaning a parent and its child. Return the largest total amount of money you can collect. An empty set of houses is allowed, so the answer is never negative. Aim for O(n) time: for each node, compute the best total with it robbed and the best total with it skipped.

Examples

Input: root = [3,2,3,null,3,null,1]
Output: 7
Rob the root (3) and the two grandchildren (3 and 1): 3 + 3 + 1 = 7.
Input: root = [3,4,5,1,3,null,1]
Output: 9
Rob the two children 4 and 5.

Constraints

  • 1 <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^4
  • The answer fits in a signed 32-bit integer

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More tree dp problems