337. House Robber III

337

MediumTrees and Binary Search TreesPost-order DFS with pair-state DPTree DP returning (rob, skip) per node

House Robber III

Given the root of a binary tree of house values, a thief cannot rob two directly-connected (parent-child) houses. Return the maximum total value the thief can rob without alerting the police.

Open official problem prompt ↗

In plain English

Maximize the sum of chosen node values subject to never choosing a parent and its child together.

Picture it like this

Planning which offices to raid in a company org chart: raiding a manager forbids raiding their direct reports, so you weigh each subtree's best inclusive and exclusive plans.

Example

Input: root = [3,2,3,null,3,null,1]
Output: 7
Why: Robbing the root 3 plus the two lower 3s (skipping the middle layer) gives 3+3+1=7, the best legal choice.

Constraints

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

Pattern lesson

See the pattern, then code

Tree DP returning (rob, skip) per node

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. For each node return two numbers: the best total if you rob this node (then both children must be skipped) and the best if you skip it (each child free to be robbed or not); combine children bottom-up.

New words, made simpleKnow these before the algorithm

Tree DP: Dynamic programming where subproblem results flow up from children to parents.
State pair: Two answers per node: best when the node is taken, and best when it is not.
Post-order: Compute children before the parent so the parent can combine them.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Memoized rob/no-rob recursion

Correct but the map lookups and recomputation are heavier than needed.

Define rob(node) with a hash map cache keyed on node and a taken/not-taken flag.

Time O(n)Space O(n)

Best choiceSingle post-order returning a pair

One traversal, no memo table, constant work per node.

Each call returns (robThis, skipThis); parent combines in O(1).

Time O(n)Space O(h)

The rule we keep true

Invariant

For any node, the returned pair holds the optimal subtree total under the two mutually exclusive decisions about that node.

Why this is correct

Reasoning

If the node is robbed, its children must be skipped, so add each child's skip value. If skipped, each child independently takes its own best (max of its pair). These cover all legal combinations, so the pair is optimal by induction from leaves upward.

The algorithm in three movesSay these aloud before coding

1Recurse to get (rob, skip) pairs for both children

leaf 3 -> (3,0); leaf 1 -> (1,0)

2Compute rob = node.val + left.skip + right.skip

node 2 -> (2, 3); node 3(r) -> (1, 0)

3Compute skip = max(left) + max(right)

root -> rob=3+0+0=... skip=3+1=4 -> max=7

4Return the pair; the answer is max of the root's pair

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readleft 3 and right 1

2 · AskPairs?

3 · Update state(3,0) and (1,0)

4 · Resultrobbing a leaf beats skipping it

Key takeaway

Robbing root and both bottom leaves (3,3,1) beats taking the middle layer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-5Base case
A missing node contributes (0,0): nothing to rob and nothing to skip.
2
Lines 6-7Recurse
Get both children's optimal pairs before deciding at this node.
3
Lines 8-9Two decisions
rob forces children skipped; skip lets each child take its own best.
4
Lines 11Answer
The best overall is the larger of the root's two options.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single node returns its own value
A node value of 0 still fits the recurrence
Deeply skewed tree relies on O(h) stack depth

Common beginner mistakes

Greedily robbing alternate levels, which is not always optimal
When robbing a node, mistakenly adding max(child) instead of the child's skip value
Recomputing subtrees without returning a pair, causing exponential blowup

Check your understanding

Why does the rob branch use the child's skip value rather than max(child)?

House Robber III

House Robber III

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees