Minimum Cameras to Monitor Binary Tree

Problem

You are given the root of a binary tree. You need to place cameras on some nodes such that all nodes are monitored. Each camera at a node can monitor its parent, itself, and its immediate children. The goal is to return the minimum number of cameras needed to monitor all nodes of the tree.

Naive Approach

A brute-force approach would involve trying all possible combinations of camera placements and then selecting the configuration with the fewest cameras that covers all nodes. This approach is highly inefficient.

Algorithm:

1. For each node, we have two choices: place a camera or don't place a camera.
2. Generate all possible configurations of camera placements.
3. For each configuration, check if all nodes are monitored.
4. Return the minimum number of cameras among all valid configurations.

Complexity Analysis

• Time Complexity: O(2^N), where N is the number of nodes in the tree, due to the exponential number of possible camera placements.
• Space Complexity: O(N) in the worst case, for the recursion stack.

Optimal Approach

A more efficient approach can be achieved using a bottom-up recursion (or post-order traversal) combined with a greedy strategy. For each node, we can define three states:

• State 0: The node is covered, and its children have cameras.
• State 1: The node has a camera.
• State 2: The node is covered, and its children do not have cameras.

Algorithm

1. Define a recursive function that returns the state of a node based on the states of its children.
2. Use post-order traversal to process the tree from the leaves to the root.
3. The states are updated as follows:
   • If either child is not covered (State 2), place a camera at the current node (State 1).
   • If at least one child has a camera (State 1), the current node is covered (State 0).
   • If both children are covered but without a camera (State 0), the current node is not covered (State 2).
4. Handle the root node separately: If the root is not covered (State 2), place a camera there.

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once.
• Space Complexity: O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N, so it can be O(N).

Edge Cases

• Empty tree: Return 0.
• Single-node tree: Return 1.

Code Example (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def minCameraCover(root: TreeNode) -> int:
    camera_count = 0

    def dfs(node: TreeNode) -> int:
        nonlocal camera_count
        if not node:
            return 0  # Covered

        left = dfs(node.left)
        right = dfs(node.right)

        if left == 2 or right == 2:
            camera_count += 1
            return 1  # Has camera

        if left == 1 or right == 1:
            return 0  # Covered

        return 2  # Not covered

    if dfs(root) == 2:
        camera_count += 1

    return camera_count