Binary Tree Cameras Interview Question for Meta

## Minimum Cameras to Monitor Binary Tree

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

### 1. Naive Approach (Brute Force)

A brute-force approach would involve trying all possible camera placements and selecting the configuration with the fewest cameras that covers all nodes.  This would involve generating all subsets of nodes, placing cameras at each subset, and checking if the resulting placement covers all nodes. This is highly inefficient.

### 2. Optimal Solution (Greedy with DFS)

A more efficient approach is a greedy algorithm combined with a Depth-First Search (DFS) traversal. We can define three states for each node:

*   **State 0:** The node is covered.
*   **State 1:** The node has a camera.
*   **State 2:** The node is not covered, and its parent needs to have a camera.

We can traverse the tree in a post-order manner.  The post-order traversal ensures that the children are processed before the parent, allowing us to make informed decisions about camera placement.

Here's the algorithm:

1.  **Base Case:** If the node is `null`, return 0 (covered).
2.  **Recursive Calls:** Recursively call the function for the left and right children.
3.  **Post-order Logic:**
    *   If either child is in state 2 (uncovered and needs parent to have camera), then place a camera at the current node (set state to 1) and increment the camera count.
    *   Else if the current node has a camera state of 1, then set state to 0 (covered)
    *   Otherwise set state to 2 (uncovered and needs parent to have camera)
4.  **Root Node:** After the DFS, if the root is in state 2, we need to place a camera at the root.

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


def minCameraCover(root):
    camera_count = 0

    def dfs(node):
        nonlocal camera_count
        if not node:
            return 0  # Covered

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

        if left_state == 2 or right_state == 2:
            camera_count += 1
            return 1  # Has camera

        if left_state == 1 or right_state == 1:
            return 0  # Covered

        return 2  # Need camera

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

    return camera_count


# Example usage:
root = TreeNode(0, TreeNode(0, None, TreeNode(0)), TreeNode(0, TreeNode(0)))
print(minCameraCover(root))
# Output: 1

root2 = TreeNode(0, TreeNode(0, None, TreeNode(0)), TreeNode(0, None, TreeNode(0, None, TreeNode(0))))
print(minCameraCover(root2))
# Output: 2

3. Big(O) Runtime Analysis

The DFS traversal visits each node exactly once. Therefore, the time complexity is O(N), where N is the number of nodes in the tree.

4. Big(O) Space Usage Analysis

The space complexity is determined by the recursive call stack. In the worst case (a skewed tree), the call stack can grow to a depth of N. Therefore, the space complexity is O(N). In a balanced tree, the space complexity would be O(log N).

5. Edge Cases and Handling

Empty Tree: If the root is None, return 0.
Single Node Tree: If the tree has only one node, place a camera at the root (handled by the post-order processing and root check).
Skewed Trees: The algorithm correctly handles skewed trees as each node is processed in the post-order traversal.
Null Children: The base case (if not node: return 0) handles null children gracefully.

This solution provides a correct and efficient way to determine the minimum number of cameras needed to monitor all nodes in a binary tree.