# Binary Tree Cameras

##### February 7, 2024

## Problem Statement #

Given a binary tree, your goal is to install cameras on the tree nodes in such a way that every node in the tree is monitored. A camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the given binary tree.

**Note:**

- Every node has at most one parent.
- Tree nodes are numbered uniquely.

## Solution Approach #

This problem can be solved using a greedy algorithm and depth-first search (DFS). The idea is to place cameras at all leaf nodes’ parents. We traverse the tree from bottom to top, deciding whether to place a camera at each node based on the status of its children.

We can mark each node with three states:

`0`

if the node needs to be covered,`1`

if the node has a camera,`2`

if the node is covered but doesn’t have a camera.

## Algorithm Steps #

- Start by defining a recursive DFS function that operates on the current node. The function should return the state of the node.
- If the current node is
`null`

, we return`2`

(covered). - Recursively call DFS for the left and right children of the current node.
- Decide the state of the current node based on its children’s states:
- If any child needs to be covered (
`0`

), place a camera here (`1`

) and increase the camera count. - If any child has a camera (
`1`

), the current node is covered (`2`

). - Otherwise, the current node needs to be covered (
`0`

).

- If any child needs to be covered (
- After the DFS traversal, check the root node’s state. If it needs coverage, add one more camera.
- Return the total number of cameras needed.

## Code (Python) #

```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def minCameraCover(root):
def dfs(node):
if not node: return 2
left, right = dfs(node.left), dfs(node.right)
if left == 0 or right == 0:
nonlocal cameras
cameras += 1
return 1
return 2 if left == 1 or right == 1 else 0
cameras = 0
if dfs(root) == 0: cameras += 1
return cameras
# Example usage
root = TreeNode(0, TreeNode(0, TreeNode(0), TreeNode(0)))
print(minCameraCover(root)) # Output: 2
```

## Time Complexity #

**O(N)**, where`N`

is the number of nodes in the binary tree. Each node is visited exactly once.

## Space Complexity #

**O(H)**, where`H`

is the height of the binary tree. This space is used by the call stack during the DFS.