Binary Tree Cameras Interview Question for Google

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree. For example:

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

As another example:

Input: root = [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.

Consider a binary tree where each node represents a location. Your task is to determine the fewest number of cameras needed to ensure that every location is monitored. A camera placed at any node monitors that node, its parent, and its immediate children. The tree structure is represented by TreeNode objects, where each node has a value of 0. Given the root of the tree, design an efficient algorithm to return the minimum number of cameras required to monitor all nodes.

## Minimum Cameras to Monitor Binary Tree

This problem requires us to find the minimum number of cameras needed to cover all nodes in a binary tree, where a camera at a node can monitor its parent, itself, and its immediate children.

### Naive Approach

A simple, but not optimal, approach would be to place a camera at every node. This guarantees that every node is covered, but it will likely use far more cameras than necessary.

### Optimal Approach

A more efficient approach involves a recursive, bottom-up strategy. We can define three states for each node:

1.  **State 0: Not covered:** The node is not covered by any camera.
2.  **State 1: Covered but no camera:** The node is covered by one of its children.
3.  **State 2: Has camera:** The node itself has a camera.

The algorithm works as follows:

*   **Base Case:** For a null node, return `1` (covered but no camera needed).
*   **Recursive Step:**
    *   Calculate the states of the left and right children.
    *   If either child is not covered (state 0), we must place a camera at the current node (state 2).
    *   If the current node's children are covered but without cameras (state 1), the current node's state is 'not covered'.
    *   Otherwise, the current node is covered by its children.

Here's the Python code:

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


class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.count = 0

        def dfs(node):
            if not node:
                return 1  # Covered

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

            if left == 0 or right == 0:
                self.count += 1
                return 2  # Has camera

            if left == 2 or right == 2:
                return 1  # Covered by child

            return 0  # Not covered

        if dfs(root) == 0:
            self.count += 1

        return self.count

# Example Usage:
# Construct the tree: [0,0,null,0,0]
root = TreeNode(0)
root.left = TreeNode(0)
root.left.left = TreeNode(0)
root.left.right = TreeNode(0)


sol = Solution()
result = sol.minCameraCover(root)
print(result)

# Construct the tree: [0,0,null,0,null,0,null,null,0]
root = TreeNode(0)
root.left = TreeNode(0)
root.left.left = TreeNode(0)
root.left.left.left = TreeNode(0)
root.right = TreeNode(0)


sol = Solution()
result = sol.minCameraCover(root)
print(result)

Big(O) Run-time Analysis

The time complexity is O(N), where N is the number of nodes in the tree. This is because we visit each node once during the depth-first search (DFS).

Big(O) Space Usage Analysis

The space complexity is O(H), where H is the height of the tree. This is due to the recursive call stack during the DFS. In the worst case (skewed tree), H can be equal to N, making the space complexity O(N). In the best case (balanced tree), H is log(N), making the space complexity O(log N).

Edge Cases

Empty Tree: If the root is None, the function should return 0, as no cameras are needed.
Single Node: If the tree consists of only the root node, one camera is needed.
Skewed Tree: The algorithm should handle skewed trees efficiently without resulting in unnecessary camera placements.

Here are some diagrams that can help illustrate the process.

A single node tree:

Here, we need 1 camera at the root node.

A tree like this:

    0
   / \
  0   0

Here, we need 1 camera at the root.

A more complex tree:

In this case, we need two cameras at the two nodes where the last level of zeroes are connected to.