Cameras on a bin tree: color-based explanation of greedy solution

cameras_on_tree.md

Problem: Given a binary tree, we install cameras on the nodes of the tree. Each camera at a node can monitor its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Solution: The basis of the induction is that leafs (if it is not trivial case) has no camera. This is the key in this greedy approach. The elegant way to express this, introduced by lee215, is by coloring not existing nodes by COVERED.

The step of induction has 3 variants:

1. one of the child of current node is NOTCOVERED. Hence, we must place a camera in this node.
2. one of the child of current node is HASCAMERA. Hence, we shall mark current as COVERED.
3. otherwise, mark this node as NOTCOVERED and we will covered it one level up.

class Solution {
public:
    enum Color {
        NOTCOVERED,
        HASCAMERA,
        COVERED_NOCAMERA
    };
    
    int res = 0;
    Color dfs(TreeNode* cur) {
        if (cur == nullptr) return COVERED_NOCAMERA;
        Color cLeft = dfs(cur->left);
        Color cRight = dfs(cur->right);
        // if one of the child is not covered - we must place a camera
        if (cLeft == NOTCOVERED || cRight == NOTCOVERED) {
            ++res;
            return HASCAMERA;
        }
        // if one of the child has cameras, we are covered
        if (cLeft == HASCAMERA || cRight == HASCAMERA)
            return COVERED_NOCAMERA;
        // otherwise, we are not covered from bottom so the parent will cover us
        return NOTCOVERED;
    }
    
    
    int minCameraCover(TreeNode* root) {
        // if the root was not covered, we need to add a camera
        if (dfs(root) == NOTCOVERED) 
            ++res;
        return res;
    }
}