Minimum Cameras to Monitor Binary Tree

Problem

You are given the root of a binary tree. You need to install cameras on the tree nodes such that each camera at a node can monitor its parent, itself, and its immediate children. The goal is to find 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. For each node, we can either place a camera or not. We would then check if the current camera placement monitors all nodes. This is a highly inefficient solution.

1. Generate all possible camera placements: Iterate through all possible subsets of nodes where cameras can be placed.
2. Verify coverage: For each placement, check if every node is monitored (covered by at least one camera in its vicinity).
3. Minimize: Keep track of the minimum number of cameras needed for a valid coverage.

Big O Analysis

• Time Complexity: O(2^N), where N is the number of nodes in the tree. This is because there are 2^N possible subsets of nodes to consider.
• Space Complexity: O(N) in the worst case, where N is the height of the tree, for the recursion stack during the coverage check.

This solution is computationally infeasible for larger trees.

Optimal Approach: Greedy Algorithm

A more efficient approach involves a greedy algorithm combined with recursion. We can traverse the tree in a post-order manner. For each node, we can have three states:

• 0: The node is not covered, and no camera is installed at this node.
• 1: The node is covered, but no camera is installed at this node.
• 2: A camera is installed at this node.

We can implement the following logic during the post-order traversal:

1. If either of the children is not covered (state 0), then we must install a camera at the current node (state 2). This ensures that the uncovered child is monitored.
2. If at least one child has a camera (state 2), then the current node is covered (state 1).
3. If both children are covered but have no camera (state 1), then the current node is not covered (state 0).

For the root node, if it's not covered (state 0), we need to install a camera.

Big O 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 can be N.

Edge Cases

• Empty tree: If the tree is empty (root is None), return 0.
• Single node: If the tree contains only one node, one camera is needed.

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:
    count = 0

    def dfs(node):
        nonlocal count
        if not node:  # Null node is considered covered
            return 1

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

        if left == 0 or right == 0:
            count += 1
            return 2  # Install camera
        elif left == 2 or right == 2:
            return 1  # Node is covered
        else:
            return 0  # Node is not covered

    if dfs(root) == 0:
        count += 1  # Install camera at root if needed

    return count

Explanation of the Code

1. TreeNode Class: Definition of a TreeNode class for binary tree representation.
2. minCameraCover Function:
   • Initializes a count variable to track the number of cameras.
   • Defines a Depth-First Search (DFS) function dfs.
   • DFS Function:
     • Base Case: If the node is None, return 1 (covered).
     • Recursively call dfs on the left and right children.
     • If either child is not covered (0), increment count and return 2 (install camera).
     • If either child has a camera (2), return 1 (covered).
     • Otherwise, return 0 (not covered).
   • After the DFS, if the root is not covered (0), increment count.
   • Return the final count.