Problem Statement

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.

Example 1:

Input:[0,0,null,0,0]
Output:1
Explanation:One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input:[0,0,null,0,null,0,null,null,0]
Output:2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

1. The number of nodes in the given tree will be in the range [1, 1000].
2. Every node has value 0.

Problem Link

Binary Tree Cameras - LeetCode

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // A node can be in three states
    // 1. It is not covered by a camera (returns 0)
    // 2. It is has a camera (returns 1)
    // 3. It is covered by a camera (returns 2)
    // The idea here is to place the camera on the node which is the parent of a leaf node 
    //  because in this way we can cover max nodes (node's parent,node and node's children)
    int cameras = 0,notCovered = 0, hasCamera = 1, cameraCovered = 2;
    int minCameraCover(TreeNode* root) {
        
        // if the root is notcovered by a camera then it needs one extra camera on it 
        return (dfs(root)==notCovered ? 1 : 0) + cameras;
        
    }
    int dfs(TreeNode* root)
    {
        if(!root)
            return cameraCovered;
        
        // if the node is a leaf node
        if(!root->left&&!root->right)
            return notCovered;
        
        int left = dfs(root->left);
        int right = dfs(root->right);
        
        // if the node is a parent of a leaf node so we place our camera here
        if(left==notCovered || right==notCovered)
        {
            cameras++;
            return hasCamera;
        }
        
        // if either left node has camera or right node has camera then their parent 
        // is cameraCovered otherwise not covered by camera 
        return left==hasCamera || right==hasCamera ? cameraCovered : notCovered;
    }
};
// Time Complexity : O(n)
// Space Complexity : O(h) where h = height of tree