Binary Tree Cameras — LC 968 Greedy 3-State DFS

Problem Statement#

LeetCode 968 — Binary Tree Cameras | Difficulty: Hard

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.

Constraints:

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

Input:  root = [0,0,null,0,0]
Output: 1

Input:  root = [0,0,null,0,null,0,null,null,0]
Output: 2

Why This Problem Matters#

Binary Tree Cameras is a FAANG hard problem that combines greedy reasoning with tree DP. Amazon and Google include it in interviews because the solution requires you to: (a) recognize that placing cameras at leaves wastes coverage, (b) design a bottom-up greedy strategy, and (c) implement it cleanly with a 3-state DFS.

The problem is a classic example of delayed greedy decisions: instead of making a camera decision at a leaf, defer it to the parent. This greedy principle — "push decisions upward as far as possible" — appears in LC 1167 (Minimum Cost to Connect Sticks), LC 435 (Non-overlapping Intervals), and many scheduling problems.

The Core Insight#

Three states define the status of any node after DFS returns:

• State 0: Node is NOT covered (no camera monitors this node)
• State 1: Node HAS a camera
• State 2: Node IS covered by a child's camera (but has no camera itself)

Greedy rules (bottom-up, post-order):

1. If either child is uncovered (state 0), place a camera at the current node → return 1
2. If either child has a camera (state 1), current node is covered → return 2
3. If both children are covered but have no cameras (state 2), current node is uncovered → return 0

Null nodes are treated as "covered" (state 2) — they need no monitoring.

After the DFS, if the root itself is uncovered (state 0), place one more camera there.

Visual Dry Run#

Tree: [0, 0, null, 0, 0]

Post-order DFS:

Root state = 2 (covered). No extra camera needed. Answer = 1.

Solution (Optimal)#

class Solution:
    def minCameraCover(self, root) -> int:
        self.cameras = 0
 
        def dfs(node):
            # Null nodes are considered "covered" — need no camera
            if not node:
                return 2
 
            left = dfs(node.left)
            right = dfs(node.right)
 
            # If any child is uncovered, place camera here
            if left == 0 or right == 0:
                self.cameras += 1
                return 1  # this node has camera
 
            # If any child has camera, this node is covered
            if left == 1 or right == 1:
                return 2  # covered, no camera here
 
            # Both children are covered but have no cameras — this node is uncovered
            return 0
 
        # If root itself is uncovered, add one more camera
        if dfs(root) == 0:
            self.cameras += 1
 
        return self.cameras

var minCameraCover = function(root) {
    let cameras = 0;
 
    function dfs(node) {
        if (!node) return 2;  // null = covered
 
        const left = dfs(node.left);
        const right = dfs(node.right);
 
        // Any uncovered child forces camera here
        if (left === 0 || right === 0) {
            cameras++;
            return 1;
        }
 
        // Any child camera covers this node
        if (left === 1 || right === 1) return 2;
 
        // Both children covered, no camera adjacent — this node uncovered
        return 0;
    }
 
    if (dfs(root) === 0) cameras++;
    return cameras;
};

Time: O(n) — each node visited exactly once Space: O(h) — recursion stack depth

Common Mistakes#

• Placing cameras at leaves (state 0 → camera) instead of their parents — wastes coverage on nodes that could be monitored by a parent camera
• Forgetting the root check: if dfs(root) == 0, you must add one more camera
• Treating null nodes as uncovered (state 0) — they are "already covered" (state 2) and should not trigger camera placement
• Confusing state 0 (uncovered) and state 2 (covered without camera) — these have different parent responses

Interview Tips#

• Name the three states explicitly before coding: 0=uncovered, 1=has camera, 2=covered
• Explain the greedy insight: never place cameras at leaves — always push the decision to the parent
• The root edge case (if dfs(root) == 0) is a common interview gotcha — mention it proactively
• This is a hard problem — start with the greedy reasoning before jumping to code

Follow-up Questions#

• What if a camera can monitor all nodes at distance 2 (not just 1)? Extend the state machine to track coverage radius — the greedy structure remains but transitions become more complex.
• What if cameras have different costs? This becomes a weighted minimum dominating set problem — use full tree DP with 3 states tracking minimum cost.
• How does this relate to the minimum dominating set problem? Binary Tree Cameras is the tree version of the minimum dominating set problem, which is NP-hard on general graphs but solvable in O(n) on trees.
• What if the tree is an n-ary tree? The same 3-state DFS works — check all children instead of just left/right.

Key Takeaways#

• Three states: 0=uncovered, 1=has camera, 2=covered by child's camera
• Greedy: if any child is uncovered (state 0), place camera at current node — this is always optimal
• Null nodes return state 2 (covered) — they need no camera and should not trigger camera placement
• After DFS, if root is state 0, add one final camera
• Time O(n), space O(h) — visits each node exactly once
• The "push camera decisions upward" greedy insight is provably optimal: it minimizes cameras by maximizing each camera's coverage
• This is a hard problem — practicing the state-machine reasoning pattern is more important than memorizing the code