Skip to main content

337. House Robber III

medium

Houses now form a binary tree — robbing two directly-linked nodes triggers the alarm. Compute the max loot via a tree DP returning two states per node.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • 0 <= Node.val <= 10^4

Examples

Example 1

Input
root = [3,2,3,null,3,null,1]
Output
7

Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2

Input
root = [3,4,5,1,3,null,1]
Output
9

Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Each node has two states: robbed or not robbed. The choice propagates a constraint to children.

Hint 2

Return a pair (rob, skip) from each subtree. rob = node.val + left.skip + right.skip; skip = max(left.rob, left.skip) + max(right.rob, right.skip).

Hint 3

Post-order traversal: compute children first, then combine. Answer is max(root.rob, root.skip).

Solution approach

Reveal approach

Post-order tree DP returning a tuple (rob, skip) for each subtree. For a null node return (0, 0). For an internal node, recurse on left and right to get (lrob, lskip) and (rrob, rskip). If we rob this node, we cannot rob its children, so rob = node.val + lskip + rskip. If we skip this node, each child can independently choose its better option, so skip = max(lrob, lskip) + max(rrob, rskip). Bubble (rob, skip) up. At the root return max(rob, skip). O(n) time visiting each node once; O(h) recursion stack.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dynamic-programming
  • tree-dp
  • post-order

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Uber

Practice these live with InterviewChamp.AI

Drill House Robber III and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →