Greedy Algorithm: Minimum Cameras to Monitor a Binary Tree

Given a binary tree, we need to place cameras on nodes such that every node in the tree is monitored. A camera placed on a node monitors itself, its parenet, and its immediate children. Determine the minimum number of cameras required.

Approach

We can solve this problem using a greedy algorithm with a post-order traversal. The key insight is that placing a camera on a leaf node is wasteful because it only covers itself and its parent. To maximize coverage, we should place cameras on the parents of leaf nodes.

Post-order traversal (left, right, root) allows us to process children before their parent, enabling a bottom-up decision process.

Node States

We define three states for each node:

• 0: Node is not covered (no camera, and not covered by any child or parenet camera yet).
• 1: Node has a camera installed.
• 2: Node is covered (either by a camera on itself, or by a child's camera, or by its parent's camera).

Handling Empty Nodes

For empty nodes (null or leaf children), we consider them as covered (state 2). This ensures that we do not force cameras onto leaf nodes unnecessarily.

Logic for Each Node

After receiving states from left and right children, we determine the state of the current node:

1. Both children are covered (state 2): The current node is not yet covered. Return state 0.
2. At least one child is uncovered (state 0): The current node must have a camera to cover it and its uncovered child. Increment the camera count and return state 1.
3. At least one child has a camera (state 1): The current node is covered by that child'ss camera. Return state 2.

After the traversal, check the root node. If it remains uncovered (state 0), we need to add one more camera.

Implementation

class Solution {
private:
    int cameraCount;
    
    // Post-order traversal
    // Returns: 0 = not covered, 1 = has camera, 2 = covered
    int traverse(TreeNode* node) {
        if (node == nullptr) return 2;  // Empty nodes are considered covered
        
        int leftState = traverse(node->left);
        int rightState = traverse(node->right);
        
        // Case 1: Both children are covered
        if (leftState == 2 && rightState == 2) {
            return 0;  // Current node is not covered
        }
        
        // Case 2: At least one child is uncovered
        if (leftState == 0 || rightState == 0) {
            cameraCount++;
            return 1;  // Place a camera here
        }
        
        // Case 3: At least one child has a camera
        // (leftState == 1 || rightState == 1)
        if (leftState == 1 || rightState == 1) {
            return 2;  // Current node is covered
        }
        
        // Should never reach here
        return -1;
    }
    
public:
    int minCameraCover(TreeNode* root) {
        cameraCount = 0;
        if (traverse(root) == 0) {  // Root is uncovered
            cameraCount++;
        }
        return cameraCount;
    }
};

Complexity Analysis

• Time Complexity: (O(n)), where (n) is the number of nodes. Each node is visited once.
• Space Complexity: (O(h)), where (h) is the height of the tree, due to recursion stack.

Key Points

• Placing cameras on leaf nodes is suboptimal; prefer placing them on parents of leaf nodes.
• Post-order traversal naturally supports bottom-up decision-making.
• The greedy choice (place camera whenever a child is uncovered) leads to optimal minimum number of cameras.