Binary Tree Cameras
Three States Per Node
The previous lessons in this chapter had two states: take or skip, in cover or not. Cameras introduce a third state, and that changes the dynamics of the postorder DP.
Problem: Binary Tree Cameras (LC 968)
Problem: You have a binary tree. You can place a camera on any node. A camera at a node monitors the node itself, its parent, and its immediate children. Return the minimum number of cameras needed to monitor every node.
Answer: 2. Place cameras at the second and third nodes from the top (the inner nodes). Every node is either a camera or adjacent to one.
The Three States
Every node, after the postorder pass, is in one of three states:
- State 0 — Uncovered. This node has no camera and no child has a camera pointing at it. It needs its parent to cover it.
- State 1 — Covered. This node is monitored (either by a child's camera or its parent's camera) but does not have a camera itself.
- State 2 — Has camera. This node has a camera, which also covers its parent and children.
The rules for combining child states:
- If any child is uncovered (state 0): This node MUST place a camera to cover that child. This node becomes state 2.
- If any child has a camera (state 2): This node is covered by that child. This node becomes state 1 (as long as the other child isn't uncovered — but rule 1 catches that first).
- If both children are covered (state 1): Neither child has a camera pointing at this node. This node is uncovered — it needs its parent to help. This node becomes state 0.
The greedy insight from the leaves up: Never place a camera at a leaf. A leaf camera covers only 2 nodes (itself + parent). A camera one level up covers up to 4 nodes (itself + parent + two children). So the optimal strategy pushes cameras away from leaves.
Full Trace
Process postorder: E, C, D, B, A.
| Step | Node | Left state | Right state | Decision | Node state | Cameras placed |
|---|---|---|---|---|---|---|
| 1 | E | null \(\to\) 1 | null \(\to\) 1 | Both covered \(\to\) uncovered | 0 | 0 |
| 2 | C | E returns 0 | null \(\to\) 1 | Child uncovered \(\to\) place camera | 2 | 1 |
| 3 | D | null \(\to\) 1 | null \(\to\) 1 | Both covered \(\to\) uncovered | 0 | 1 |
| 4 | B | C returns 2 | D returns 0 | Child uncovered \(\to\) place camera | 2 | 2 |
| 5 | A | B returns 2 | null \(\to\) 1 | Child has camera \(\to\) covered | 1 | 2 |
Null nodes return state 1 (covered) — they don't exist, so they don't need monitoring. This convention prevents placing unnecessary cameras at leaves.
Final answer: 2 cameras.
Manual verification: Camera at C covers {E, C, B}. Camera at B covers {C, B, A, D}. Every node is covered. Could we do it with 1 camera? Place it at B: covers {C, B, A, D} but NOT E. Node E is two edges away from B. So 1 camera is impossible. 2 is optimal.
Why Null Returns "Covered" (State 1)
This is the subtlest part. If null returned state 0 (uncovered), every leaf would see an uncovered child and place a camera. That wastes cameras at every leaf — the opposite of optimal.
If null returned state 2 (has camera), every leaf would think it's already covered and return state 1, then its parent would see two covered children and return state 0. The cameras shift up one level. That actually works for some trees but fails for others because the root might end up uncovered.
State 1 (covered) is the correct choice. It says: "null doesn't need monitoring, and it doesn't provide a camera." This forces leaves to be state 0 (uncovered), which forces cameras at their parents — exactly the greedy strategy we want.
Handling the Root
After the postorder finishes, check the root's state. If the root is state 0 (uncovered), nobody covered it — it has no parent. You need one more camera at the root.
This is the one edge case. The three-state logic assumes every uncovered node will be handled by its parent. The root has no parent, so you handle it explicitly.
The Code
int dfs(TreeNode* node, int& cameraCount) {
if (!node) return 1;
int leftState = dfs(node->left, cameraCount);
int rightState = dfs(node->right, cameraCount);
if (leftState == 0 || rightState == 0) {
cameraCount++;
return 2;
}
if (leftState == 2 || rightState == 2) {
return 1;
}
return 0;
}
int minCameraCover(TreeNode* root) {
int cameraCount = 0;
int rootState = dfs(root, cameraCount);
if (rootState == 0) {
cameraCount++;
}
return cameraCount;
}
Complexity: \(O(n)\) time, \(O(h)\) space where \(h\) is the tree height.
Connection to Minimum Vertex Cover
This problem is a variant of minimum dominating set on trees (every node must be dominated by a neighbor or itself). The approach in Lesson 2 (minimum vertex cover) had two states — include or exclude. Here you have three states because "covered by child" and "covered by parent" have different implications for what the parent must do.
The three-state pattern appears whenever a node's decision depends not just on whether it's selected, but on WHO selected it. In vertex cover, being covered by a child vs. a parent doesn't matter — you're covered either way. In cameras, it matters because a camera covers the parent too, creating upward information flow.
Try It
Predict before running: A straight chain of 3 nodes. Leaf = state 0, middle = places camera (state 2), root = covered by child (state 1). Answer: 1. Now add a 4th node at the bottom. The new leaf = state 0, its parent (old leaf) = places camera (state 2), middle = covered (state 1), root = uncovered (state 0). Root has no parent, so add 1 camera. Answer: 2.
Challenge: Can you solve this with the explicit DP approach instead? Define three cost values per node: \(cost_{camera}\), \(cost_{coveredByChild}\), \(cost_{coveredByParent}\). The recurrence is more complex but generalizes to \(k\)-ary trees without modification.
Edge Cases to Watch For
- Root is uncovered after postorder: The root has no parent to cover it. This is the one case where you must add an extra camera after the DFS completes. Always check
if (rootState == 0) cameraCount++. Forgetting this post-DFS check is the most common bug in this problem.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 968 --- Binary Tree Cameras | leetcode.com/problems/binary-tree-cameras | Hard |
| LC 337 --- House Robber III | leetcode.com/problems/house-robber-iii | Medium |
| LC 979 --- Distribute Coins in Binary Tree | leetcode.com/problems/distribute-coins-in-binary-tree | Medium |
| LC 1372 — Longest ZigZag Path | leetcode.com/problems/longest-zigzag-path-in-a-binary-tree | Medium |
What's Next?
You've learned the include/exclude framework. Chapter 9 connects this to formal dynamic programming and shows where the DP Course picks up.