Binary Tree Cameras
Problem
root, return the fewest
cameras needed so that every node is watched.[0,0,null,0,0]Output1[0,0,null,0,null,0,null,null,0]Output21 ≤ n ≤ 1000 · Node.val == 0
Try it yourself
class Solution {
public int minCameraCover(TreeNode root) {
}
}
Instinct A node's best answer depends only on its children's answers - post-order DFS that returns a tiny tuple of states per node.
Memory hack Kids report up, parent decides - every subtree hands its parent a small report card, and the parent never re-reads the kids' homework.
Open the Tree & Graph DP guide →Approaches
Brute ForceTry Every Camera Subset
O(2n·n)Space O(n)Index the nodes and remember each one's parent. For every bitmask of camera positions, check in O(n) that each node has a camera on itself, its parent or a child, and keep the smallest valid popcount.
private final List<Integer> parent = new ArrayList<>(); public int minCameraCover(TreeNode root) { collect(root, -1); int n = parent.size(), best = n; for (int mask = 0; mask < (1 << n); mask++) if (Integer.bitCount(mask) < best && allWatched(mask)) best = Integer.bitCount(mask); return best; } private void collect(TreeNode node, int par) { // pre-order ids, record parents if (node == null) return; int id = parent.size(); parent.add(par); collect(node.left, id); collect(node.right, id); } private boolean allWatched(int mask) { boolean[] ok = new boolean[parent.size()]; for (int i = 0; i < ok.length; i++) { int p = parent.get(i); boolean camI = (mask >> i & 1) == 1, camP = p >= 0 && (mask >> p & 1) == 1; if (camI || camP) ok[i] = true; // own or parent's camera if (camI && p >= 0) ok[p] = true; // a child's camera watches its parent } for (boolean b : ok) if (!b) return false; return true; }
A useful oracle for tiny trees; hopeless beyond ~20 nodes.
BetterTree DP with 3 States
O(n)Space O(h)Each node returns the min cameras for its subtree in 3 states:
0 = node unwatched (everything below watched), 1 = watched by a child
camera, 2 = camera on node. Combine children:
s0 = L1+R1, s1 = min(L2+min(R1,R2), R2+min(L1,L2)),
s2 = 1 + min(L) + min(R).
private static final int INF = 1_000_000; public int minCameraCover(TreeNode root) { int[] r = solve(root); return Math.min(r[1], r[2]); } private int[] solve(TreeNode node) { // {unwatched, watched by child, has camera} if (node == null) return new int[]{0, 0, INF}; int[] l = solve(node.left), r = solve(node.right); int minL = Math.min(l[1], l[2]), minR = Math.min(r[1], r[2]); int s0 = l[1] + r[1]; int s1 = Math.min(l[2] + minR, r[2] + minL); int s2 = 1 + Math.min(l[0], minL) + Math.min(r[0], minR); return new int[]{s0, s1, s2}; }
Provably optimal and extends to weighted cameras, but more bookkeeping.
OptimalGreedy Post-Order (Leaves Up)
O(n)Space O(h)Return a status to the parent: 0 = needs cover,
1 = covered, 2 = has camera (null counts as covered). If a
child needs cover, the node must take a camera; if a child has one, the node is
covered; else ask the parent. Cameras sit as high as possible, so each covers the
most nodes.
private int cameras = 0; public int minCameraCover(TreeNode root) { if (dfs(root) == 0) cameras++; // root still uncovered return cameras; } private int dfs(TreeNode node) { // 0 = needs cover, 1 = covered, 2 = camera if (node == null) return 1; int left = dfs(node.left), right = dfs(node.right); if (left == 0 || right == 0) { cameras++; return 2; } return (left == 2 || right == 2) ? 1 : 0; }
Same O(n) as the DP with one int per node and no min() algebra.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Try Every Camera Subset | O(2n·n) | O(n) |
| Better | Tree DP with 3 States | O(n) | O(h) |
| Optimal | Greedy Post-Order (Leaves Up) | O(n) | O(h) |
- Treating
nullas “needs cover” — leaves get cameras. - Skipping the final root check — an uncovered root needs a camera.
- Testing “child has camera” before “child needs cover”.
- Justify greedy by exchange: moving a leaf camera up never hurts.
- Name the three states explicitly before coding.
- Offer the DP version if cameras get different costs.