Binary Tree Cameras
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 the minimum dominating set problem restricted to binary trees: choose the smallest set of nodes such that every node is in the set or adjacent to a member. On general graphs that problem is NP-hard, but the tree structure makes it solvable in linear time. One observation drives every efficient solution: a camera on a leaf covers two nodes (the leaf and its parent), while a camera on the leaf's parent covers up to four (itself, both children, and its own parent). Whenever the tree has more than one node, some optimal placement puts every camera on an internal node.
Key Constraints:
1 <= number of nodes <= 1000- The tree is small, so the challenge is correctness rather than performance. Even an O(n^2) solution would finish in under a millisecond; only the exponential brute force is ruled out.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
Try every possible subset of nodes as camera positions, check whether each subset covers all nodes, and return the size of the smallest valid subset.
Each node either gets a camera or it does not, which gives 2^n subsets. For each subset, we verify that every node is either a camera node or adjacent to one.
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. The waste is that subsets are evaluated globally even though the problem decomposes: the best way to cover a subtree depends only on what happens at the subtree's root, not on the rest of the tree. Dynamic programming on the tree exploits that decomposition.
Approach 2: Tree DP (Three Costs per Node)
Intuition
The rest of the tree needs only one piece of information about a subtree: the status of its root. That status takes one of three forms, so we compute three costs for every node:
- camera: the minimum cameras to cover the whole subtree with a camera placed on this node.
- covered: the minimum cameras to cover the whole subtree with no camera here, meaning at least one child holds a camera.
- uncovered: the minimum cameras to cover everything below this node while the node itself stays unmonitored, waiting for its parent.
A post-order DFS fills in these triples bottom-up using three transitions:
- camera = 1 + the cheapest of the three states for each child. A camera here monitors both children from above, so each child may take any state, including uncovered.
- covered = the cheaper of "left child takes a camera" and "right child takes a camera." The child without the camera must pay for its own coverage (camera or covered), because nothing at this node monitors it.
- uncovered = left covered + right covered. No child may hold a camera (that would cover this node, contradicting the state) and no child may stay uncovered (nothing below or here will ever cover it).
A null child contributes (INF, 0, 0): it cannot hold a camera, and it costs nothing to leave alone. The answer is min(camera, covered) at the root. The root's uncovered cost is discarded because no parent exists to cover it.
Algorithm
- Run a post-order DFS that returns the triple (camera, covered, uncovered) for each node.
- For a null node, return (INF, 0, 0).
- Compute the node's three costs from the children's triples using the transitions above.
- Cap each cost at INF so the sentinel cannot grow without bound on deep trees.
- Return min(camera, covered) for the root.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited once, and the transition work per node is a constant number of additions and minimums.
- Space Complexity: O(h) where h is the height of the tree, for the recursion stack (O(n) worst case for a skewed tree). Each frame stores one constant-size triple.
This already runs in linear time, and the triple formulation generalizes: the same decomposition solves weighted variants where a camera costs a different amount at each node. In this problem every camera costs 1, and that uniformity supports a simpler rule that skips the cost comparisons entirely.
Approach 3: Greedy DFS (Three States)
Intuition
The DP carries three costs per node and compares sums of them at every step. Those comparisons turn out to be unnecessary. A camera is only ever needed when a child would otherwise stay unmonitored, so a single status per node, computed bottom-up, determines every decision. Each node reports to its parent 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.
Take any deepest uncovered leaf. The only nodes that can cover it are the leaf itself and its parent. A camera on the parent covers a superset of what a camera on the leaf covers: the parent's camera reaches the leaf, the parent, the parent's other child, and the grandparent, while the leaf's camera reaches only the leaf and the parent. So any optimal solution with a camera on that leaf can be rewritten, without adding cameras, to put the camera on the parent instead. Some optimal solution therefore places a camera on the parent of every deepest uncovered leaf. That is the choice the greedy makes whenever a child reports NOT_COVERED. Remove the covered nodes and repeat the argument on the remaining forest: by induction, the greedy uses exactly as many cameras as an optimal solution.
The same reasoning explains why a node with both children COVERED stays uncovered rather than taking a camera: its parent can always cover it later, and deferring can only save cameras, never cost extra.
The three states are also exhaustive. Every combination of left and right child states maps to exactly one parent state, and the post-order traversal guarantees both children are resolved before the parent decides. The root is the one special case: it has no parent to defer to, so if it ends the DFS as NOT_COVERED, it takes its own camera in a final check.
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).