Binary Tree Cameras
The key idea
Process the tree bottom-up and label every node with one of three states: not-covered, covered-without-camera, or has-camera. A leaf can never afford a camera (it would waste coverage), so push the decision up: a parent installs a camera only when forced — i.e. when a child reports it is still not covered. This greedy 'install as late and as high as possible' rule is provably optimal.
Problem
You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
Constraints
- The number of nodes in the tree is in the range
[1, 1000]. Node.val == 0
Examples
Input: root = [0,0,null,0,0]
Output: 1
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM