337 · House Robber III

The int[]{withRoot, withoutRoot} return. The first genuinely two-dimensional state in this pattern, and the model for everything else in sub-variant K — when a single number cannot answer a parent's question, return the answer for every case the parent might be in.

1 — Why one number is not enough

Rob a tree of houses; no two directly-linked houses may both be robbed. Maximise the take.

The instinct is to return "the best take from this subtree". It does not work, and the reason is worth stating precisely: the parent cannot use that number, because it does not know whether the child itself was robbed. If the child was robbed, the parent must skip itself; if not, the parent is free. One number has thrown away the fact the parent needs.

Compare with LC 543, where the non-composable value was recorded on the side. Here the missing information is not a maximum to report — it is a case distinction, so the fix is different: return both cases.

The asymmetry between the two lines is the entire algorithm. rob may only add the children's skip; skip takes the better of each child's two options independently, because nothing links the two siblings.

2 — Two numbers coming up

Watch each node return a pair, and watch the root's answer — max(7, 6) — be decided only at the very end. Along the way, node 2 returns [2, 3]: its skip beats its rob, because its child is worth more than it is.

No node ever commits to a choice. Each one reports what would happen under both hypotheses and lets its parent decide — which is exactly what makes a greedy approach fail here and this one succeed.

2.1 The memoised alternative, and why it is worse

A single-value recursion can be rescued by looking two levels down:

private Map<TreeNode, Integer> memo = new HashMap<>();

public int rob(TreeNode nd) {
    if (nd == null) return 0;
    if (memo.containsKey(nd)) return memo.get(nd);
    int take = nd.val;
    if (nd.left  != null) take += rob(nd.left.left)  + rob(nd.left.right);
    if (nd.right != null) take += rob(nd.right.left) + rob(nd.right.right);
    int best = Math.max(take, rob(nd.left) + rob(nd.right));
    memo.put(nd, best);
    return best;
}

It is correct and it is what most people write first. Without the memo it is exponential, because every node is computed once as a child and again as a grandchild. The paired-return version needs no memo at all — it visits each node exactly once by construction — which is the general advantage of sub-variant K: carrying the case distinction upward removes the overlapping subproblems instead of caching them.

2.2 The rest of sub-variant K

Java has no tuples, so pick a carrier: int[] is fastest to type, record Pair(int rob, int skip) is what you want when the components are easy to swap by accident. In an interview the record is worth the extra line.

3 — Complexity and edge cases

• Time O(n), space O(h). One postorder pass, no memo, no map.
• Empty tree: 0, from max(0, 0).
• Single node: its value — rob = val, skip = 0.
• A straight chain: degenerates to the original House Robber on an array, which is the sanity check that the recurrence is right.
• Values are non-negative in this problem, so skip never needs clamping. If they could be negative, max(L.rob, L.skip) would still be correct — the max already declines a losing subtree, as in LC 124.
• Common bug: writing skip = L[0] + R[0] — forcing the children to be robbed rather than letting them choose.
• Common bug: returning max(rob, skip) from the helper. That is the answer for the caller at the top, not for a parent, and it destroys the case distinction — the exact mistake the pair exists to prevent.
• Common bug: swapping the two slots. Use a record if you have been bitten by this before.

4 — Reference implementation

public int rob(TreeNode root) {
    int[] r = go(root);
    return Math.max(r[0], r[1]);   // only the top-level caller collapses the pair
}

private int[] go(TreeNode nd) {
    if (nd == null) return new int[]{0, 0};
    int[] L = go(nd.left);
    int[] R = go(nd.right);
    int rob  = nd.val + L[1] + R[1];          // children forced to skip
    int skip = Math.max(L[0], L[1])
             + Math.max(R[0], R[1]);         // children choose freely
    return new int[]{rob, skip};
}