Binary Tree Cameras

Problem Place the minimum number of cameras on binary-tree nodes so every node is monitored; a camera monitors its parent, itself, and its immediate children.

Input / Output

• Input: tree root. Output: minimum camera count.

Constraints

• Up to 1000 nodes; O(n) greedy DFS expected — the DP formulation also accepted.

Example

• [0,0,null,0,0] → 1 (camera on the middle node); [0,0,null,0,null,0,null,null,0] → 2.

Expected approach

• Post-order greedy with three states per node: NOT_COVERED, COVERED (no camera), HAS_CAMERA. A node places a camera iff any child is NOT_COVERED; leaves return NOT_COVERED (never waste a camera on a leaf — its parent covers more). Root check: if root ends NOT_COVERED, add one. Greedy optimality comes from placing cameras as high as possible above leaves. O(n)/O(h). The state design and the "why not leaves" argument are the interview substance.