# Binary Tree Cameras
**Difficulty:** HARD
[External](https://leetcode.com/problems/binary-tree-cameras)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-cameras
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [eBay](https://scaleengineer.com/companies/ebay), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [MathWorks](https://scaleengineer.com/companies/mathworks), [DP world](https://scaleengineer.com/companies/dp-world), [Graviton](https://scaleengineer.com/companies/graviton), [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/binary-tree-cameras/image0.png) 

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

**Example 2:**

![](https://assets.glich.co/dsa/binary-tree-cameras/image1.png) 

**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.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 1000]`.
* `Node.val == 0`

# Approaches
## Dynamic Programming on Trees
This approach uses dynamic programming on the tree structure. We define a recursive function that computes the minimum number of cameras for a subtree, considering different states for the root of that subtree. By solving for the children and combining the results, we can determine the optimal solution for the parent. This method systematically explores all valid configurations for each subtree to find the minimum, resulting in a linear time complexity.
**Time:** O(N), where N is the number of nodes. Each node's state is computed once. · **Space:** O(N), where N is the number of nodes. The recursion depth can go up to N in a skewed tree, and a memoization table would also require O(N) space.
**Pros:** It's a systematic way to solve the problem that guarantees optimality.; It breaks down the problem into smaller, manageable subproblems.
**Cons:** More complex to reason about and implement compared to the greedy approach.; The state transitions can be tricky to define correctly.; Higher constant factor overhead in both time and space due to the more complex state management.
### Explanation
We can define a function, say `solve(node)`, that returns an array of three values representing the minimum cameras needed for the subtree rooted at `node` under three different states of `node` itself.
Let `res = [state0, state1, state2]`:
- `res[0]`: The minimum cameras for the subtree at `node`, given that `node` is **uncovered**.
- `res[1]`: The minimum cameras for the subtree at `node`, given that `node` is **covered by a camera from its child**, but has no camera on it.
- `res[2]`: The minimum cameras for the subtree at `node`, given that `node` **has a camera on it**.

The recursion proceeds in a post-order manner. For a given `node`, we first recursively call `solve` for its left and right children.

**Base Case**: If `node` is `null`, it doesn't need a camera and can be considered covered. We return `[0, 0, 1001]` (using a large number for infinity, as placing a camera on null is impossible).

**Transitions**:
- To calculate `state2` (camera on `node`): We place one camera on `node`. Its children are now covered. For each child, we can choose any of its three states and pick the one with the minimum cameras.
  `state2 = 1 + min(left_res) + min(right_res)`
- To calculate `state0` (`node` is uncovered): `node` has no camera. Its children must be covered by their own subtrees (i.e., they cannot be in state 0). So, they must be in state 1 or 2. We choose the cheaper option for each.
  `state0 = left_res[1] + right_res[1]`
- To calculate `state1` (`node` is covered by a child): `node` has no camera. At least one of its children must have a camera.
  - Option A: Left child has a camera. Cost is `left_res[2] + min(right_res[1], right_res[2])`.
  - Option B: Right child has a camera. Cost is `min(left_res[1], left_res[2]) + right_res[2]`.
  - `state1 = min(Option A, Option B)`.

**Final Answer**: For the root of the tree, it cannot be left uncovered. So the final answer is `min(res[1], res[2])` from the result of `solve(root)`.

```java
class Solution {
    // res[0]: node is not covered
    // res[1]: node is covered by a child's camera
    // res[2]: node has a camera
    public int minCameraCover(TreeNode root) {
        int[] result = solve(root);
        return Math.min(result[1], result[2]);
    }

    private int[] solve(TreeNode node) {
        if (node == null) {
            // {not_covered, covered_by_child, has_camera}
            // A null node is technically covered and needs 0 cameras.
            // It cannot have a camera, so we use a large value for that state.
            return new int[]{0, 0, 1001}; 
        }

        int[] left = solve(node.left);
        int[] right = solve(node.right);

        // Case 1: Place a camera on the current node.
        // Children can be in any state, pick the minimum for each.
        int has_camera = 1 + Math.min(left[0], Math.min(left[1], left[2])) + Math.min(right[0], Math.min(right[1], right[2]));

        // Case 2: Node is covered by a child's camera.
        // One of the children must have a camera.
        int covered_by_child = Math.min(
            left[2] + Math.min(right[1], right[2]), // left child has camera
            right[2] + Math.min(left[1], left[2])  // right child has camera
        );

        // Case 3: Node is not covered.
        // Children must be covered, but not by this node.
        int not_covered = left[1] + right[1];

        return new int[]{not_covered, covered_by_child, has_camera};
    }
}
```
### Algorithm
1. Define a recursive function, `solve(node)`, that computes the minimum cameras for the subtree at `node`.
2. This function will return an array of three integers: `[state0, state1, state2]`.
   - `state0`: Min cameras for the subtree, assuming `node` is **uncovered**.
   - `state1`: Min cameras for the subtree, assuming `node` is **covered by a child's camera**.
   - `state2`: Min cameras for the subtree, assuming `node` **has a camera**.
3. **Base Case**: For a `null` node, return `{0, 0, infinity}` as it's covered, needs 0 cameras, and cannot have a camera.
4. **Recursive Step (Post-order)**: For a non-null `node`, first recursively call `solve` for its left and right children to get their results, `left_res` and `right_res`.
5. **Calculate States for `node`**:
   - `state2 = 1 + min(left_res) + min(right_res)`. (Place a camera on `node`, so children can be in any state).
   - `state0 = left_res[1] + right_res[1]`. (`node` is uncovered, so children must be covered by their own subtrees, i.e., state 1).
   - `state1 = min(left_res[2] + min(right_res[1], right_res[2]), right_res[2] + min(left_res[1], left_res[2]))`. (`node` is covered by a child, so one child must have a camera).
6. **Final Result**: The initial call is `solve(root)`. The root cannot be left uncovered, so the answer is `min(result[1], result[2])`.

## Greedy Approach with Post-Order Traversal (DFS)
This is a highly efficient and intuitive greedy approach. The core idea is to use a post-order traversal (DFS) to make decisions from the leaves up to the root. We place a camera on a node only when it's strictly necessary, which is when one of its children is uncovered. This greedy strategy of placing cameras as high up as possible is optimal because a higher camera can cover more nodes (itself, its parent, and its children).
**Time:** O(N), where N is the number of nodes in the tree. We visit each node exactly once. · **Space:** O(H), where H is the height of the tree. This is for the recursion call stack. In the worst case of a skewed tree, this can be O(N). For a balanced tree, it's O(log N).
**Pros:** Very efficient in terms of both time and space.; The logic is relatively simple and concise to implement once the states are understood.; Optimal space complexity (O(H) vs O(N) for the DP with a full memoization table).
**Cons:** The correctness of the greedy choice might not be immediately obvious and requires some reasoning to be convinced of its optimality.
### Explanation
We can define three states for each node that our traversal function will return:
- `0`: The node is **uncovered**. It needs its parent to place a camera.
- `1`: The node is **covered** but does not have a camera itself.
- `2`: The node **has a camera** installed on it.

We use a member variable, `cameras`, to count the number of cameras placed. The algorithm uses a helper function, `dfs(node)`, which performs a post-order traversal.

**Algorithm**:
1. Initialize `cameras = 0`.
2. Start a post-order traversal from the root using `dfs(root)`.
3. The `dfs(node)` function works as follows:
    - **Base Case**: If `node` is `null`, it doesn't need monitoring. We can consider it "covered", so we return state `1`. This simplifies the logic for leaf nodes.
    - **Recursive Step**: Recursively call `dfs` on the left and right children to get their states: `leftState = dfs(node.left)` and `rightState = dfs(node.right)`.
    - **Greedy Decision**:
        - If `leftState == 0` or `rightState == 0`, it means at least one child is uncovered. To cover it, we *must* place a camera on the current `node`. So, we increment `cameras`, and this node now has a camera. Return state `2`.
        - If `leftState == 2` or `rightState == 2`, it means at least one child has a camera, which covers the current `node`. So, this node is covered. Return state `1`.
        - If `leftState == 1` and `rightState == 1`, it means both children are covered, but neither has a camera. The current `node` is therefore not covered yet. It signals to its parent that it needs coverage. Return state `0`.
4. **Root Handling**: After the initial call `dfs(root)` completes, we check the state of the root itself. If the root is in state `0`, it means it's uncovered and has no parent to place a camera. We must place one more camera at the root. So, if `dfs(root) == 0`, we increment `cameras`.
5. Return the final `cameras` count.

```java
class Solution {
    private int cameras = 0;
    // 0: uncovered
    // 1: covered, no camera
    // 2: has camera
    public int minCameraCover(TreeNode root) {
        // If the root is left uncovered after the traversal, it needs a camera.
        if (dfs(root) == 0) {
            cameras++;
        }
        return cameras;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            // A null node is considered covered.
            return 1;
        }

        int leftState = dfs(node.left);
        int rightState = dfs(node.right);

        // If either child is uncovered, this node must have a camera.
        if (leftState == 0 || rightState == 0) {
            cameras++;
            return 2;
        }

        // If either child has a camera, this node is covered.
        if (leftState == 2 || rightState == 2) {
            return 1;
        }

        // Both children are covered, but don't have cameras.
        // This node is not covered and needs its parent to place a camera.
        return 0;
    }
}
```
### Algorithm
1. Use a helper function, `dfs(node)`, that performs a post-order traversal and returns the state of `node`.
2. Define three states:
   - `0`: The node is **uncovered**.
   - `1`: The node is **covered** but has no camera.
   - `2`: The node **has a camera**.
3. Use a counter variable, `cameras`, initialized to 0.
4. **`dfs(node)` Logic**:
   - **Base Case**: If `node` is `null`, it's considered covered. Return state `1`.
   - **Recursive Step**: Get states from children: `leftState = dfs(node.left)`, `rightState = dfs(node.right)`.
   - **Greedy Decision**:
     - If `leftState == 0` or `rightState == 0` (a child is uncovered), place a camera on `node`. Increment `cameras` and return state `2`.
     - If `leftState == 2` or `rightState == 2` (a child has a camera), `node` is now covered. Return state `1`.
     - Otherwise (`leftState == 1` and `rightState == 1`), `node` is not covered by its children. It needs its parent to cover it. Return state `0`.
5. **Main Function Logic**:
   - Call `dfs(root)`.
   - If the root itself returns state `0`, it's uncovered and has no parent. Place one more camera. Increment `cameras`.
   - Return the total `cameras` count.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int minCameraCover ( TreeNode root ) { int [] ans = dfs ( root ); return Math . min ( ans [ 0 ], ans [ 1 ]); } private int [] dfs ( TreeNode root ) { if ( root == null ) { return new int [] { 1 << 29 , 0 , 0 }; } var l = dfs ( root . left ); var r = dfs ( root . right ); int a = 1 + Math . min ( Math . min ( l [ 0 ], l [ 1 ]), l [ 2 ]) + Math . min ( Math . min ( r [ 0 ], r [ 1 ]), r [ 2 ]); int b = Math . min ( Math . min ( l [ 0 ] + r [ 1 ], l [ 1 ] + r [ 0 ]), l [ 0 ] + r [ 0 ]); int c = l [ 1 ] + r [ 1 ]; return new int [] { a , b , c }; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ struct Status { int a , b , c ; }; class Solution { public: int minCameraCover ( TreeNode * root ) { auto [ a , b , _ ] = dfs ( root ); return min ( a , b ); } Status dfs ( TreeNode * root ) { if ( ! root ) { return { 1 << 29 , 0 , 0 }; } auto [ la , lb , lc ] = dfs ( root -> left ); auto [ ra , rb , rc ] = dfs ( root -> right ); int a = 1 + min ({ la , lb , lc }) + min ({ ra , rb , rc }); int b = min ({ la + ra , la + rb , lb + ra }); int c = lb + rb ; return { a , b , c }; }; };
```

### Python

```python
# 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 : def dfs ( root ): if root is None : return inf , 0 , 0 la , lb , lc = dfs ( root . left ) ra , rb , rc = dfs ( root . right ) a = min ( la , lb , lc ) + min ( ra , rb , rc ) + 1 b = min ( la + rb , lb + ra , la + ra ) c = lb + rb return a , b , c a , b , _ = dfs ( root ) return min ( a , b )
```