Binary Tree Cameras

Problem

Install minimum cameras on nodes so every node is monitored (a camera monitors itself, parent, and children).

Key insight (Greedy): Place cameras as high as possible. If a leaf is uncovered, install camera at its parent (greedy bottom-up).

Approach — Tree DP with 3 states

State 0: Node not covered
State 1: Node has camera
State 2: Node covered (no camera)

Solutions

// C++ — greedy 3-state
int cameras = 0;
int dfs(TreeNode* node) {
    if (!node) return 2; // null = covered
    int l = dfs(node->left), r = dfs(node->right);
    if (l == 0 || r == 0) { cameras++; return 1; } // child uncovered → place camera here
    if (l == 1 || r == 1) return 2; // child has camera → we're covered
    return 0; // both children covered but no camera near us → we're uncovered
}
int minCameraCover(TreeNode* root) {
    if (dfs(root) == 0) cameras++;
    return cameras;
}

// Java
int cameras = 0;
public int minCameraCover(TreeNode root) {
    if (dfs(root) == 0) cameras++;
    return cameras;
}
int dfs(TreeNode node) {
    if (node == null) return 2;
    int l = dfs(node.left), r = dfs(node.right);
    if (l == 0 || r == 0) { cameras++; return 1; }
    if (l == 1 || r == 1) return 2;
    return 0;
}

// JavaScript
function minCameraCover(root) {
    let cameras = 0;
    function dfs(node) {
        if (!node) return 2;
        const l = dfs(node.left), r = dfs(node.right);
        if (l === 0 || r === 0) { cameras++; return 1; }
        if (l === 1 || r === 1) return 2;
        return 0;
    }
    if (dfs(root) === 0) cameras++;
    return cameras;
}

# Python
def minCameraCover(root):
    cameras = [0]
    def dfs(node):
        if not node:
            return 2  # covered
        l, r = dfs(node.left), dfs(node.right)
        if l == 0 or r == 0:
            cameras[0] += 1
            return 1  # place camera here
        if l == 1 or r == 1:
            return 2  # covered by child camera
        return 0  # not yet covered
    if dfs(root) == 0:
        cameras[0] += 1
    return cameras[0]

Complexity

Time: O(n)
Space: O(h)

Key Insight

Greedy: always delay camera placement as long as possible (go up). If a leaf is uncovered, its parent MUST have a camera — that camera also covers grandparent.