968 - Binary Tree Cameras

Difficulty: Hard | Pattern: Greedy + DFS | Company tags: Google, Amazon, Facebook

Problem Statement

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

Example 2:

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

Algorithm Flow

Approach: Greedy DFS (Bottom-Up) — O(n), O(h)

Key insight: Place cameras as high as possible (greedy from leaves up). A leaf never needs a camera — place the camera on its parent. State per node:

• 0 = not covered
• 1 = covered but no camera
• 2 = has camera

def minCameraCover(root) -> int:
    cameras = 0
    
    def dfs(node):
        nonlocal cameras
        if not node:
            return 1  # null nodes considered "covered"
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        if left == 0 or right == 0:
            # At least one child not covered → place camera here
            cameras += 1
            return 2
        
        if left == 2 or right == 2:
            # At least one child has camera → this node is covered
            return 1
        
        # Both children covered but no camera → this node not covered
        return 0
    
    if dfs(root) == 0:
        cameras += 1  # root itself not covered
    
    return cameras

Dry Run

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

    0
   /
  0
 / \
0   0

DFS (post-order):

• Leaves (bottom 0,0): dfs(None)=1, so no camera needed → return 0 (not covered)
• Node (middle 0): left=0 → place camera! cameras=1, return 2
• Node (root): left=2 → covered, return 1

Root returns 1 → no extra camera needed. Answer: 1 ✓

State Machine Summary

left	right	action	return
0 or right=0	—	place camera	2
2 or right=2	—	covered by child	1
both 1	both 1	not covered	0

Complexity

• Time: O(n)
• Space: O(h) for recursion stack

Key Terms

Term	Definition
Greedy bottom-up DFS	Deciding camera placement post-order, starting from leaves, to minimize total cameras
Tree DP with node states	Encoding each subtree's status (uncovered / covered / has-camera) as the DFS return value
Post-order traversal	Processing children before the parent, required so a node's placement decision can use both children's states
Root correction	Special-case check after DFS finishes, since the root has no parent to place a camera on its behalf

FAQ

Q1: Why place cameras at leaves' parents instead of at the leaves themselves? A camera at a leaf only covers itself and its parent, whereas a camera one level up covers the parent, that node, and all sibling leaves — strictly more coverage per camera, which is the greedy insight.

Q2: What if the tree is a single node? dfs(root) returns 0 (both children are None, treated as covered, but the node itself has no camera), so the if dfs(root) == 0: cameras += 1 correction fires, giving the correct answer of 1.

Q3: Why does dfs(None) return 1 (covered) instead of 0? Treating missing children as "covered" prevents leaf nodes from being forced to place unnecessary cameras — a leaf's children don't exist and impose no coverage obligation.

Q4: Can this greedy strategy fail on any tree shape? No — it's provably optimal because a bottom-up greedy that only places a camera when forced (a child is uncovered) never places redundant cameras, and post-order guarantees children are resolved before the decision is needed.

Q5: How does this relate to other tree "state DP" problems? It's structurally similar to House Robber III or Binary Tree Pruning: each node's DFS returns enough state for the parent to make an optimal local decision without re-scanning the subtree.

Quick Revision

• Each node's DFS return value is one of three states: 0 (uncovered), 1 (covered, no camera), 2 (has camera).
• dfs(None) returns 1 so leaves are never forced to hold a camera themselves.
• If either child returns 0 (uncovered), place a camera at the current node and return 2.
• Else if either child returns 2 (has camera), the current node is covered — return 1.
• Else (both children covered but no camera) — return 0, deferring the decision to the parent.
• After the full DFS, if the root itself returns 0, add one final camera for the root.
• Time is O(n), space is O(h) for the recursion stack.
• Greedy works because placing cameras as high as possible always covers at least as much as placing them lower.

Related Problems

• 814 - Binary Tree Pruning — same post-order DFS pattern returning subtree state to the parent
• 104 - Maximum Depth of Binary Tree — simpler example of the same bottom-up recursion structure
• Pattern match: tree DP / greedy-with-state problems like House Robber III (rob houses in a binary tree)