Problem 32.7 · Advanced DPHard

Binary Tree Cameras

What it teaches: Three states per node; the bottom-up rule places cameras on the parents of leaves.

Practise it on judges as “Binary Tree Cameras”.

The problem

A camera on a node watches its parent, itself and its children. Return the minimum number of cameras to watch every node.

Example 1

Input: root = [0, 0, null, 0, 0]
Output: 1

Constraints

1 ≤ nodes ≤ 1000

Pattern clues in the wording

→ Cover every node with minimum items
→ Tree

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int minCameraCover(TreeNode root) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	root = [0,0,null,0,0]	1
2	root = [0,0,null,0,null,0,null,null,0]	2
3	root = [0]	1

From slow to fast

Approaches

1. Post-order states · O(n)

Post-order states

Time O(n) Space O(h)

null → 2. If any child is 0 → camera here (1). Else if any child is 1 → 2. Else → 0. At the root, a 0 needs one more camera.

Approach 1

class Solution {
    private int cameras = 0;

    public int minCameraCover(TreeNode root) {
        return state(root) == 0 ? cameras + 1 : cameras;
    }

    private int state(TreeNode n) {
        if (n == null) return 2;
        int l = state(n.left), r = state(n.right);
        if (l == 0 || r == 0) { cameras++; return 1; }
        if (l == 1 || r == 1) return 2;
        return 0;
    }
}

Verdict: Greedy, justified by the tree structure.

Before you submit

Edge cases and common mistakes

Test these inputs

Single node (1)
A path

Mistakes people make

Putting cameras on leaves (a leaf's camera covers fewer nodes than its parent's).

Interview

Follow-up questions

Why is a camera at a leaf's parent always safe?

Command Palette

The problem

Approaches

Post-order states

Edge cases and common mistakes

Follow-up questions