Binary Tree Cameras
Hard · Trees · Dynamic Programming · Tree · Depth-First Search · Binary Tree
Problem
You are given the root of a binary tree. You can install cameras on nodes, and a camera watches its own node, its parent and its immediate children.
Return the smallest number of cameras needed so that every node in the tree is watched.
Examples
Input: root = [0,0,null,0,0] Output: 1
One camera on the root’s left child watches the root and both of its children.
Input: root = [0,0,null,0,null,0,null,null,0] Output: 2
The tree is a chain of five nodes; cameras on the 2nd and 4th nodes watch it all.
Constraints
- The number of nodes is in the range [1, 1000]
- Node.val == 0
Approaches
- Baseline: three costs per node (dynamic programming) — time O(n), space O(h) for the recursion
Follow-up
What if each node has a price for its camera? The greedy no longer works, because a cheap leaf can beat an expensive parent; keep three costs per node instead (see the use case “Cheapest cameras when each node has a price”). The same post-order pattern solves the vertex cover of a tree, where a guard covers only the edges at its node.
Related problems
Start free on Cariara · Coding problems · System design studio
