Fewest Cameras to Watch Every Node
HardTrees
Problem
A security company places cameras on the nodes of a binary tree. A camera on a node watches that node, its parent and its direct children.
Return the minimum number of cameras needed so that every node is watched. Node values are irrelevant (all 0).
Example 1
- Input:
- root = [0, 0, null, 0, 0]
- Output:
- 1
One camera on the root's left child watches it, the root and both of its children.
Example 2
- Input:
- root = [0, 0, null, 0, null, 0, null, null, 0]
- Output:
- 2
A chain of five nodes needs two cameras, for example on the 2nd and 4th nodes.
Constraints
- 1 ≤ number of nodes ≤ 10^4
- node.val == 0
Hint
Show the first hint
Leaves are the hardest nodes to cover efficiently. Is a camera on a leaf ever better than one on its parent?
Walkthrough
How to approach it
01Clarify before coding
- Does a camera watch grandchildren? No, only itself, its parent and its children.
- Can the tree be a single node? Yes: it needs one camera.
- Do values matter? No, every value is 0.
02Brute force
Try every subset of nodes as camera positions and keep the smallest subset that watches everything.
Cost: O(2^n · n): impossible beyond about 25 nodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.