#968

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Cameras

Determine the minimum number of cameras required to monitor every node in a binary tree using efficient DFS and state tracking.

dynamic programming tree depth first search binary tree

Problem Statement

You are given the root of a binary tree. Each camera placed at a node can monitor its parent, itself, and immediate children. Determine the minimum number of cameras required to cover all nodes in the tree.

For example, given root = [0,0,null,0,0], one camera placement can cover all nodes. For root = [0,0,null,0,null,0,null,null,0], at least two cameras are necessary. Return the smallest number of cameras needed.

Examples

Example 1

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

Output: 1

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

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

Solution Approach

Use DFS with Node State Tracking

Traverse the tree using depth-first search. Assign each node a state: 0 for not covered, 1 for covered, 2 for has a camera. Evaluate children first to decide whether the current node needs a camera.

Bottom-Up Recursion

Process leaf nodes first and propagate coverage information upwards. Place cameras on nodes whose children are not covered to ensure minimal placement while all nodes are eventually monitored.

Dynamic Programming Optimization

Cache the results for subtrees to avoid recalculating coverage states. This reduces redundant computation and guarantees that each node's camera placement decision contributes to a global minimum.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(H)

Time complexity is O(N) because each node is visited once. Space complexity is O(H) due to recursion stack, where H is the height of the tree.

What Interviewers Usually Probe

Wants an optimal solution using DFS with minimal cameras
Interested in how you track node states during traversal
Checks if you handle edge cases like skewed or leaf-heavy trees

Common Pitfalls or Variants

Common pitfalls

Placing cameras on every node instead of minimal set
Failing to correctly propagate covered states from children
Ignoring the coverage of parent nodes leading to overcounting cameras

Follow-up variants

Find minimum cameras in n-ary trees instead of binary trees
Compute camera placement when some nodes cannot hold cameras
Determine camera placement for dynamic trees that can change structure

FAQ

What is the core pattern in Binary Tree Cameras problem?

The main pattern is binary-tree traversal combined with state tracking for covered nodes, which guides minimal camera placement.

How do I determine if a node needs a camera?

Check the states of its children: if any child is not covered, the current node requires a camera to cover them.

Can I solve this without recursion?

Yes, but iterative DFS or BFS with explicit stacks is more complex and requires careful state management for each node.

What are common mistakes when placing cameras?

Placing too many cameras, failing to propagate coverage, or not handling leaf nodes correctly are frequent errors.

How does dynamic programming help in this problem?

It avoids recalculating coverage for subtrees, ensuring optimal camera count while keeping the algorithm efficient.

terminal

Solution

Solution 1: Dynamic Programming (Tree DP)

For each node, we define three states:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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)

Continue Practicing

#1372 longest zigzag path in a binary tree #1373 maximum sum bst in binary tree #337 house robber iii