Binary Tree Cameras
Last Updated: March 28, 2026
Understanding the Problem
We need to place the fewest cameras possible on a binary tree so that every node is "covered," meaning it either has a camera on it or is adjacent to a node with a camera. A camera covers the node it sits on, its parent, and its direct children.
This is a minimum vertex cover variant on trees, but with a twist: coverage extends to the parent and both children, not just neighbors in one direction. The challenge is figuring out which nodes benefit most from having a camera. Placing a camera on a leaf only covers two nodes (itself and its parent), but placing one on the leaf's parent covers up to four nodes (itself, both children, and its own parent). That observation is the key to the entire solution.
Key Constraints:
1 <= number of nodes <= 1000- The tree is small. Even O(n^2) would run in under a millisecond. But the real challenge here is correctness, not performance.Node.val == 0- The values do not matter. This is purely a structural problem about the tree's shape.
Approach 1: Brute Force (Try All Subsets)
Intuition
The most direct approach: try every possible subset of nodes to place cameras on, check if all nodes are covered, and return the size of the smallest valid subset.
For each node, we either place a camera or we do not. That gives us 2^n subsets. For each subset, we verify that every node is either a camera node or adjacent to one. This is conceptually simple but wildly inefficient.
Algorithm
- Enumerate all 2^n subsets of nodes.
- For each subset, mark the selected nodes as having cameras.
- Check if every node in the tree is covered (has a camera or is adjacent to a camera node).
- Track the minimum subset size among all valid configurations.
- Return that minimum.
Example Walkthrough
Code
- Time Complexity: O(2^n * n). We enumerate 2^n subsets and for each subset, we traverse all n nodes to verify coverage. This is completely impractical for n > 20.
- Space Complexity: O(n). We store all nodes in a list and use a hash set for the camera positions.
This approach is exponential and unusable for the given constraints. Can we make a local decision at each node using information from its children instead of trying all combinations?
Approach 2: Greedy DFS (Three States)
Intuition
Instead of trying all subsets, think about what each node needs to "report" to its parent. After processing both children, a node knows everything it needs to make a decision. Each node can be in exactly one of three states:
- State 0 (NOT_COVERED): This node has no camera and is not covered by any child's camera. It needs its parent to place a camera.
- State 1 (HAS_CAMERA): This node has a camera on it. It covers itself, its children, and its parent.
- State 2 (COVERED): This node does not have a camera but is already covered by at least one child's camera.
The greedy insight is that we should never place a camera on a leaf if we can avoid it. A leaf camera covers at most 2 nodes (itself and its parent), while a camera on the leaf's parent covers up to 4 nodes (itself, both children, and its own parent). By processing bottom-up and delaying camera placement as long as possible, we naturally push cameras toward internal nodes where they cover more ground.
The three-state system captures every possible situation a node can be in after its subtree is fully processed. The rules are complete: every combination of left and right child states maps to exactly one parent state. And the post-order traversal guarantees that by the time we decide a node's state, both children are already resolved.
The only special case is the root. It has no parent, so if it ends up NOT_COVERED, there is nobody above to rescue it. We handle this with a final check after the DFS.
Algorithm
- Define three states: NOT_COVERED = 0, HAS_CAMERA = 1, COVERED = 2.
- Run a post-order DFS on the tree.
- Treat null children as COVERED (they do not need monitoring and should not force a camera).
- At each node, apply the state transition rules based on children's states:
- If any child is NOT_COVERED, place a camera on this node.
- If any child HAS_CAMERA, this node is COVERED.
- If both children are COVERED, this node is NOT_COVERED.
- After the DFS, if the root is NOT_COVERED, add one more camera for the root.
- Return the total camera count.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during the post-order DFS. Each visit does O(1) work (two comparisons and a return).
- Space Complexity: O(h) where h is the height of the tree. The recursion stack holds at most h frames. In the worst case (skewed tree), h = n. For a balanced tree, h = log(n).