Community Problem

House Robber III

Difficulty: Medium

Maximize money robbed from a binary-tree neighborhood where no two directly-connected houses can both be robbed.

House Robber III

Maximize money robbed from a binary-tree neighborhood where no two directly-connected houses can both be robbed.

MEDIUM

Free

trees

binary-tree

dfs

recursion

By @milozhang

May 16, 2026

Updated May 20, 2026

869 views

4.3 (12)

I love this one as a follow-up after candidates solve the original House Robber on a line, because it forces them to translate "max independent set on a path" into "max independent set on a tree". The tree version is the cleanest example of post-order DP I know: every recursive call returns a tuple of two values (rob this node, skip this node), and the parent combines them. The catalog has linear House Robber but skipped this generalization.

House Robber III

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 robbed 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.

Examples

Example 1:

Input: root = [3, 2, 3, null, 3, null, 1]
Output: 7
Explanation: Rob the root (3) plus the two leaf grandchildren (3 and 1). Total 3 + 3 + 1 = 7. Robbing any direct child would forbid robbing the root and cap the total below 7.

Example 2:

Input: root = [3, 4, 5, 1, 3, null, 1]
Output: 9
Explanation: Rob the two children of the root (4 + 5 = 9). Robbing the root would forbid robbing either child, capping the total at 3 + 1 + 3 + 1 = 8.

Example 3:

Input: root = [1]
Output: 1
Explanation: Single house, no neighbors to worry about.

Example 4:

Input: root = [10, 1, 1, null, null, 1, 1]
Output: 12
Explanation: Rob the root (10) plus the two grandchildren (1 + 1). Total 12.

Constraints

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

Follow-up

The naive recursion that calls rob(grandchildren) and rob(child) is exponential. The post-order tuple version is O(n). Can you explain why each subtree is visited exactly once in the tuple version?

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach: Post-Order DP Returning a (rob, skip) Tuple (O(n) time, O(h) space)

The naive thought is: at each node, choose between node.val + rob(grandchildren) and rob(children). That recursion is correct but exponential, because the same subtree is visited from multiple ancestors. The fix is to compute both options at every node in a single post-order pass and return them as a pair.

For every subtree rooted at node, define:

rob(node) = maximum money if we DO rob node = node.val + skip(left) + skip(right).
skip(node) = maximum money if we do NOT rob node = max(rob(left), skip(left)) + max(rob(right), skip(right)).

The recursion returns the pair, the parent combines them, and at the root we take max(rob(root), skip(root)).

Algorithm

Define helper(node) returning [rob, skip].
Base case: node == null returns [0, 0].
Recursive case: compute left = helper(node.left), right = helper(node.right). Build [node.val + left.skip + right.skip, max(left) + max(right)].
Top level: return max(helper(root)).

Why It Works

Each subtree contributes its two best options once to its parent, so every node is visited exactly once. The constraint "no two directly-linked houses" is enforced by the fact that the rob branch sums only the skip values of the children, which by definition do not rob those children. Conversely, the skip branch does not rob the current node, so children are free to be either robbed or skipped.

Complexity

Text

Sample tree with (rob, skip) values
        3
       / \
      4   5
     / \   \
    1   3   1

Leaf 1: (1, 0)
Leaf 3: (3, 0)
Leaf 1: (1, 0)
Node 4: (4 + 0 + 0, 1 + 3) = (4, 4)
Node 5: (5 + 0, 1) = (5, 1)
Root 3: (3 + skip(4) + skip(5), max(4,4) + max(5,1)) = (3 + 4 + 1, 4 + 5) = (8, 9)
Answer = max(8, 9) = 9

Text

Metric  Value
Time    O(n) - one post-order traversal
Space   O(h) recursion stack

Pitfalls

Naive recursion. The version that calls rob(grandchildren) and rob(children) recomputes the same subtree exponentially many times. The tuple version visits each node once.
Memoizing on node only. Memoizing rob(node) works but uses O(n) extra space for the cache. The tuple version uses O(h) recursion-stack space and no cache.
Confusing the two skip terms. Skipping a node means BOTH children can be either robbed or skipped, so you take max(rob(child), skip(child)) for each child independently. Forcing children to also be skipped is overcautious and wrong.

Solution Code

All Problems