Binary Tree Cameras

LeetCode 1008 | Difficulty: Hard

Hard

Problem Description

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:

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

Example 2:

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`

Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 137 ms)

Metric	Value
Runtime	137 ms
Memory	38.5 MB
Date	2022-02-03

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int Not_Monitored = 0;
    private int Monitored_NoCam = 1;
    private int Monitored_WithCam = 2;
    private int cameras = 0;
    public int MinCameraCover(TreeNode root)
    {
        if(root==null) return 0;
        int top = dfs(root);
        return cameras + (top == Not_Monitored ? 1 : 0);
    }
    private int dfs(TreeNode root)
    {
        if(root==null) return Monitored_NoCam;
        int left = dfs(root.left);
        int right = dfs(root.right);
        if(left == Monitored_NoCam && right == Monitored_NoCam)
        {
            return Not_Monitored;
        }
        else if(left==Not_Monitored || right == Not_Monitored)
        {
            cameras++;
            return Monitored_WithCam;
        }
        else
        {
            return Monitored_NoCam;
        }
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.