DSA problem
Binary Tree Cameras
You are given the root of a binary tree. We install cameras on some nodes of the tree, where each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor every node in the tree.
A correct solution must guarantee that every single node — including leaves and internal nodes — is covered by at least one camera. The natural greedy intuition is "do not waste cameras on leaves." A leaf can be covered cheaply by placing a camera on its parent, which also covers the parent and the parent's parent. So the optimal strategy installs cameras as high in the tree as possible while still ensuring leaves get covered.
To turn that intuition into an algorithm, do a post-order DFS that returns one of three states for each subtree: 0 (this node NEEDS a camera in its parent to be covered), 1 (this node is already COVERED by a child's camera), or 2 (this node HAS a camera, so it covers itself, its children, and contributes to covering its parent). Children's states drive the parent's decision via three rules.
Rule 1: if either child returns 0 (needs covering), the parent must install a camera here and return 2 — otherwise the needy child would go uncovered. Rule 2: if either child returns 2 (has a camera), this node is covered for free, so return 1. Rule 3: if both children return 1 (covered but no camera), this node has no camera above or below and itself needs covering, so return 0. After processing the root, if the root's own state is 0 we must install one final camera there. The traversal is O(n) time and O(h) space.
Examples
root = [0,0,null,0,0]1root = [0,0,null,0,null,0,null,null,0]2root = [0]1Constraints
- The number of nodes in the tree is in the range [1, 1000].
- Node.val == 0
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.