# LeetCode 968: Binary Tree Cameras

## Problem Restatement

We are given the root of a binary tree.

We may install cameras on tree nodes. A camera at a node can monitor:

1. Its parent
2. Itself
3. Its immediate children

Return the minimum number of cameras needed to monitor every node in the tree.

The official constraints say the tree has between `1` and `1000` nodes, and every node value is `0`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root of a binary tree |
| Output | Minimum number of cameras needed |
| Camera coverage | Parent, self, and immediate children |

Example function shape:

```python
def minCameraCover(root: Optional[TreeNode]) -> int:
    ...
```

## Examples

Example 1:

```python
root = [0, 0, None, 0, 0]
```

Output:

```python
1
```

One camera can cover all nodes if placed on the internal child node.

Example 2:

```python
root = [0, 0, None, 0, None, 0, None, None, 0]
```

Output:

```python
2
```

At least two cameras are needed to cover every node.

## First Thought: Try Every Camera Placement

A direct approach is to try every subset of nodes as camera positions.

For each subset, check whether all nodes are covered.

But a tree with `n` nodes has:

```python
2 ** n
```

possible subsets.

With up to `1000` nodes, this is impossible.

We need a local greedy rule.

## Key Insight

A camera placed at a leaf is usually inefficient.

A leaf camera covers:

1. The leaf
2. Its parent

But a camera placed at the parent covers:

1. The parent
2. The leaf
3. The parent's other child, if present
4. The grandparent

So when a leaf needs coverage, it is better to place the camera at its parent.

This suggests a bottom-up traversal.

We decide what a node needs after seeing the states of its children.

## Node States

Use postorder DFS.

Each node returns one of three states:

| State | Meaning |
|---|---|
| `NEEDS_CAMERA` | This node is not covered and asks its parent for a camera |
| `HAS_CAMERA` | This node has a camera |
| `COVERED` | This node is covered, but has no camera |

A `None` child is considered covered:

```python
if node is None:
    return COVERED
```

A missing node does not need a camera.

## Greedy Rules

After processing the left and right children:

### Rule 1: If any child needs a camera, place a camera here

```python
if left == NEEDS_CAMERA or right == NEEDS_CAMERA:
    cameras += 1
    return HAS_CAMERA
```

This covers the current node, both children, and the parent.

### Rule 2: If any child has a camera, this node is covered

```python
if left == HAS_CAMERA or right == HAS_CAMERA:
    return COVERED
```

The current node is monitored by that child camera.

### Rule 3: Otherwise, this node needs a camera from its parent

```python
return NEEDS_CAMERA
```

This happens when both children are covered but have no cameras.

## Algorithm

1. Set `cameras = 0`.
2. Run postorder DFS.
3. For each node:
   - Get left child state.
   - Get right child state.
   - If any child needs a camera, place a camera here.
   - Else if any child has a camera, mark this node covered.
   - Else mark this node as needing a camera.
4. After DFS, if the root still needs a camera, add one more camera.
5. Return `cameras`.

## Correctness

The algorithm makes decisions bottom-up.

A leaf has two `None` children. Since `None` children are covered and have no cameras, the leaf returns `NEEDS_CAMERA`.

When a parent sees that a child needs a camera, placing a camera at the parent is optimal. It covers that child, the parent itself, the sibling child, and possibly the grandparent. Placing the camera lower at the child would cover fewer useful nodes.

If a child already has a camera, the current node is covered. Adding another camera at the current node would be unnecessary at this moment, so the node returns `COVERED`.

If neither child has a camera and neither child needs one, then the children are covered without cameras. The current node is not covered by them, so it must ask its parent for coverage.

These cases cover all possible child-state combinations.

The only node without a parent is the root. If DFS finishes and the root still needs a camera, the algorithm adds one camera at the root. Therefore, every node is covered.

Because the algorithm places a camera only when a child cannot otherwise be covered from below, every placed camera is necessary. Therefore, the total number of cameras is minimum.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | The recursion stack has one frame per tree level |

Here, `h` is the height of the tree.

In the worst case, a skewed tree has `h = n`.

## Implementation

```python
from typing import Optional

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        NEEDS_CAMERA = 0
        HAS_CAMERA = 1
        COVERED = 2

        cameras = 0

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal cameras

            if node is None:
                return COVERED

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

            if left == NEEDS_CAMERA or right == NEEDS_CAMERA:
                cameras += 1
                return HAS_CAMERA

            if left == HAS_CAMERA or right == HAS_CAMERA:
                return COVERED

            return NEEDS_CAMERA

        if dfs(root) == NEEDS_CAMERA:
            cameras += 1

        return cameras
```

## Code Explanation

We define three states:

```python
NEEDS_CAMERA = 0
HAS_CAMERA = 1
COVERED = 2
```

A missing child returns `COVERED`:

```python
if node is None:
    return COVERED
```

This prevents us from placing cameras for nonexistent nodes.

The DFS is postorder:

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

We need child states before deciding the current node state.

If either child needs a camera:

```python
if left == NEEDS_CAMERA or right == NEEDS_CAMERA:
    cameras += 1
    return HAS_CAMERA
```

we place a camera at the current node.

If a child has a camera:

```python
if left == HAS_CAMERA or right == HAS_CAMERA:
    return COVERED
```

then the current node is already monitored.

Otherwise:

```python
return NEEDS_CAMERA
```

the current node is uncovered and asks its parent for a camera.

Finally, the root needs special handling:

```python
if dfs(root) == NEEDS_CAMERA:
    cameras += 1
```

The root has no parent, so if it asks for a camera, we must place one at the root.

## Testing

```python
from collections import deque

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

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root = build_tree([0, 0, None, 0, 0])
    assert s.minCameraCover(root) == 1

    root = build_tree([0, 0, None, 0, None, 0, None, None, 0])
    assert s.minCameraCover(root) == 2

    root = build_tree([0])
    assert s.minCameraCover(root) == 1

    root = build_tree([0, 0, 0])
    assert s.minCameraCover(root) == 1

    root = build_tree([0, 0, 0, 0, 0, 0, 0])
    assert s.minCameraCover(root) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[0,0,None,0,0]` | One camera covers all nodes |
| Long left chain | Requires multiple cameras |
| Single node | Root needs one camera |
| Root with two children | One root camera covers all |
| Perfect tree with 7 nodes | Two child cameras cover the tree |