Tree DP: Subtree Return Values

Write the subtree contract first

Not every bottom-up state algorithm is numeric DP. Binary Tree Cameras uses a three-state greedy rule. The shared skill is defining a state contract that retains the distinctions the parent needs.

A single best value is insufficient for house selection: the parent might forbid selecting the child. Preserve both conditional results instead of guessing which one the parent will need.

Return both choices in one visit

For maximum independent weight on a tree, adjacent nodes cannot both be selected. take assumes this node is selected, forcing both children to skip. skip allows each child to choose its better state. Missing children return [0,0]. The empty selection is allowed in this general template.

function maximumIndependentWeight(root) {
  function visit(node) {
    if (!node) return [0, 0];
    const [leftTake, leftSkip] = visit(node.left);
    const [rightTake, rightSkip] = visit(node.right);

    const take = node.val + leftSkip + rightSkip;
    const skip = Math.max(leftTake, leftSkip) + Math.max(rightTake, rightSkip);
    return [take, skip];
  }

  const [take, skip] = visit(root);
  return Math.max(take, skip);
}

• Each child subtree is visited once. There is no repeated include/exclude recursion over grandchildren.
• For the nonnegative House Robber III constraints, the same recurrence applies directly.
• The two returned numbers are conditional optima, not the two best individual houses.

Trace the example's pairs

The proof follows the contract: after fixing whether the current node is selected, there is no edge joining its two child subtrees. Optimize those subtrees independently under the chosen restriction, then combine them.

1. Grandchildren 3 and 1 return [3,0] and [1,0].
2. The left child 2 returns [2,3]: selecting it gives 2; skipping it permits its child worth 3.
3. The right child 3 returns [3,1].
4. At root 3, take = 3 + 3 + 1 = 7. skip = max(2,3) + max(3,1) = 6.
5. Return max(7,6) = 7. Skipping the root does not mean taking every node on one depth level.

Why path gains and coverage need different states

• For Maximum Path Sum, a completed candidate may use both children. The value returned upward may use only one, otherwise the parent creates a branching structure rather than a simple path.
• Clamp a negative child gain to zero when excluding that branch is allowed. Keep the global path answer nonempty, so an all-negative tree returns its best node, not zero.
• For cameras, a covered node without a camera cannot cover its parent. Keep COVERED distinct from CAMERA.
• A child that needs coverage takes priority over a sibling camera. The sibling's camera does not cover that child.
• A root has no parent. Resolve any final parent-dependent state explicitly.

Linear work does not guarantee stack safety

• The two-state template does constant work per node: O(N) time and O(H) recursion-stack space.
• H is O(log N) on a balanced tree but O(N) on a chain. A long valid chain can exceed JavaScript call-stack capacity.
• An explicit bottom-up order plus a Map of child states uses O(N) auxiliary space and avoids recursive calls. It is the robust variant for unbounded depth.
• Do not generalize this tree recurrence to arbitrary graphs: cycles and cross-edges break child-subtree independence.
• If the task changes to reconstructing selected nodes or handling weighted cameras, revisit the state and decision rules rather than copying this template unchanged.

Mistakes and Counterexamples