968 · Binary Tree Cameras

Three states — covered-with-camera, covered-without, uncovered — and a greedy postorder placement. The hardest state design in this pattern; if you can derive its transition table you can derive any of them.

1 — The problem

A camera at a node monitors itself, its parent, and its immediate children. Place the minimum number of cameras so every node is monitored.

Two decisions have to be made before any code, and the second is the one people skip.

1.1 The greedy rule

Never put a camera on a leaf. A camera on a leaf covers the leaf and its parent. Moving it to the parent covers the parent, the leaf, the parent's other child, and the grandparent — strictly more, for the same cost. So an optimal solution exists in which cameras sit only on nodes with at least one child, and the rule becomes: place a camera as late as possible — at the parent of an uncovered node.

Working bottom-up is what makes "as late as possible" implementable: by the time you reach a node, its children have already declared whether they still need covering.

1.2 Why three states and not two

The parent needs to distinguish three genuinely different situations in a child, and no pair of them can be merged:

Merging 1 and 2 into "covered" loses the fact that only a camera radiates upward. Merging 0 and 2 loses the distinction between "needs help" and "fine". Three is the minimum.

The transition table follows mechanically, and the order of the tests is the algorithm:

Test 1 must come first: an uncovered child is an obligation, and it outranks the convenience of already being covered by the other child.

2 — One camera, placed as late as possible

Both leaves report 0. Their parent is forced to take a camera, and that single camera then covers the leaves, itself, and the root.

2.1 Two details that decide correctness

• null returns 2, not 0. An absent child does not need covering, so it must not force a camera. Returning 0 puts a camera above every leaf — the exact placement the greedy argument rejected — and roughly doubles the answer. This is the single most common bug in the problem.
• The root needs a final check. If go(root) returns 0, the root is uncovered and there is no parent to fix it, so one more camera is needed. The recursion cannot know it is at the root, so the wrapper handles it.

public int minCameraCover(TreeNode root) {
    cameras = 0;
    if (go(root) == 0) cameras++;   // root left uncovered — no parent to save it
    return cameras;
}

2.2 Greedy, and why it is safe here

Greedy algorithms on trees are usually suspect — LC 337 is the cautionary example, where taking the locally better option fails and you must carry both cases upward. So why is greedy sound here?

Because the exchange argument above is airtight: any solution with a camera on a leaf can be transformed into one with the camera on its parent, no worse and covering a superset. Repeatedly applying that transformation reaches a solution the algorithm produces, without ever increasing the count. There is no such exchange for House Robber — moving a robbery upward is not always neutral — which is precisely why that problem needs the paired state and this one does not.

A DP formulation with three per-node costs also works and is easier to justify; it is longer to write. Know that it exists in case an interviewer challenges the greedy.

3 — Complexity and edge cases

• Time O(n), space O(h). One postorder pass, O(1) per node.
• Single node: both children are null → 2, 2 → falls to line 7 and returns 0. The wrapper adds the one camera. Answer 1.
• Two nodes: the leaf returns 0, the root places a camera. Answer 1 — and this is the smallest case that distinguishes "camera on the leaf" from "camera on the parent".
• A perfect tree of 7 nodes: answer 2 — cameras on the two middle nodes, with the root covered by both.
• A long chain: cameras land every third node, which is the recognisable signature of a correct implementation.
• Common bug: null returning 0.
• Common bug: omitting the root check. Off by exactly one, and only on inputs where the root ends uncovered.
• Common bug: testing for state 1 before state 0. A node with one camera-holding child and one uncovered child would return 2 and abandon the uncovered child forever.

4 — Reference implementation

// 0 = uncovered, 1 = has a camera, 2 = covered without one
private int cameras;

public int minCameraCover(TreeNode root) {
    cameras = 0;
    if (go(root) == 0) cameras++;
    return cameras;
}

private int go(TreeNode nd) {
    if (nd == null) return 2;                    // absent ⇒ needs nothing
    int L = go(nd.left), R = go(nd.right);
    if (L == 0 || R == 0) { cameras++; return 1; }  // obligation — test this FIRST
    if (L == 1 || R == 1) return 2;             // a child's camera reaches me
    return 0;                                  // both children merely covered
}