Binary Tree Cameras: Minimum Cameras with Greedy DFS

LeetCode Binary Tree Cameras (Problem 968) asks you to place the fewest cameras possible on a binary tree so that every node is monitored. A camera at a node monitors the node itself, its parent, and its immediate children. Given the root of a binary tree, return the minimum number of cameras needed to cover every node.

The problem

You are given the root of a binary tree. You need to install cameras on some of the tree nodes. Each camera monitors the node it sits on, the node's parent, and the node's direct children. Find the minimum number of cameras required so that every node is monitored by at least one camera.

For example, given this tree:

      0
     / \
    0   0
   / \
  0   0

The answer is 2. One camera at the left child of the root, and one camera at the root itself, cover all five nodes.

The brute force approach

You could try every possible subset of nodes, place cameras on each subset, check whether all nodes are covered, and track the smallest valid subset. That is an exponential search: for n nodes, there are 2^n subsets. Even for modest trees with 20 or 30 nodes, this is completely impractical.

A slightly better brute force uses recursion with memoization, treating each node as a small DP problem with states for "has camera," "covered by neighbor," and "not covered." But this still overcomplicates things. The structure of trees gives us a much cleaner approach.

The key insight

Think about where you should avoid placing cameras. Leaves are the worst spot for a camera. A camera on a leaf monitors at most two nodes (itself and its parent). A camera on the leaf's parent monitors at most four nodes (itself, its parent, and up to two children). So you always prefer to push cameras up from the leaves.

This gives you a greedy strategy: process the tree bottom-up, and let each node report its state to its parent. Every node is in one of three states:

• State 0: "I need a camera." The node is not covered and needs its parent to install one.
• State 1: "I have a camera." The node has a camera installed and covers its neighbors.
• State 2: "I am covered." The node is already monitored by a child's camera and does not need anything from its parent.

The rules for deciding a node's state are simple:

1. If any child returns 0 (needs a camera), install a camera at the current node. Return 1.
2. If any child returns 1 (has a camera), the current node is covered. Return 2.
3. If both children return 2 (covered), the current node is not yet covered. Return 0, asking its parent to handle it.

Step-by-step walkthrough

Let's trace through the example tree. The DFS processes nodes in post-order: left subtree first, then right subtree, then the current node.

Notice how the algorithm never places a camera on a leaf. Every leaf returns 0, which forces its parent to install a camera. This is exactly the greedy choice: cameras on interior nodes cover more of the tree than cameras on leaves.

The code

def minCameraCover(root):
    cameras = 0
    def dfs(node):
        nonlocal cameras
        if not node:
            return 2
        left = dfs(node.left)
        right = dfs(node.right)
        if left == 0 or right == 0:
            cameras += 1
            return 1
        if left == 1 or right == 1:
            return 2
        return 0
    if dfs(root) == 0:
        cameras += 1
    return cameras

Here is what each piece does:

• if not node: return 2 is the base case. Null nodes are treated as "covered" so that leaves correctly report state 0 (needs camera).
• left = dfs(node.left) and right = dfs(node.right) recurse into both subtrees first (post-order). The current node makes its decision after hearing from both children.
• if left == 0 or right == 0 checks whether any child needs a camera. If so, install one here (cameras += 1) and return 1.
• if left == 1 or right == 1 checks whether any child has a camera. If so, the current node is already covered. Return 2.
• return 0 is the fallback. Both children are covered (state 2), but nobody is covering the current node. It tells its parent "I need a camera."
• The final if dfs(root) == 0: cameras += 1 handles the root. The root has no parent to install a camera for it, so if it returns 0, you must add one more camera.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node you do O(1) work: two comparisons, possibly an increment, and a return.

Space is O(h) where h is the height of the tree. This is the recursion stack depth. For a balanced tree, h = log n. For a skewed tree (essentially a linked list), h = n. No extra data structures are needed beyond the call stack and the camera counter.

The building blocks

Bottom-up tree processing

The core pattern here is post-order DFS where each node collects information from its children before making its own decision. You see this in many tree problems: compute something for the children first, then combine the results at the current node.

The skeleton looks like this:

def dfs(node):
    if not node:
        return BASE_CASE
    left = dfs(node.left)
    right = dfs(node.right)
    # decide based on left and right
    return RESULT

This same skeleton powers Binary Tree Maximum Path Sum, Diameter of Binary Tree, and Balanced Binary Tree. The difference is what you compute and return at each node.

Greedy state machines

Instead of exploring all possibilities (DP over subsets), you assign each node a state and make a locally optimal choice. The three states (0 = needs camera, 1 = has camera, 2 = covered) form a tiny state machine. The transition rules are greedy: always prefer to push cameras away from leaves and toward interior nodes.

This greedy choice works because of the tree structure. In a tree, there are no cycles, so each node has exactly one parent. A camera on an interior node always covers at least as many nodes as a camera on a leaf. You never regret pushing cameras upward.

Edge cases

• Single node (just a root): The root is a leaf with no children. Both null children return 2, so the root returns 0. The final check catches this and adds one camera. Answer: 1.
• Two nodes (root with one child): The child is a leaf and returns 0. The root installs a camera and returns 1. Answer: 1.
• Straight line (skewed tree): A chain of n nodes. Cameras are placed at every third node from the bottom. The greedy naturally handles this because each leaf triggers a camera at its parent, covering three consecutive nodes.
• Perfect binary tree: Cameras go on every other level, starting from the parents of the leaves. The greedy post-order traversal produces this pattern automatically.

From understanding to recall

You just traced through the three-state greedy approach and watched it place cameras at interior nodes while skipping leaves. The logic is clean: leaves say "I need a camera," parents of needy nodes install one, and nodes with camera-equipped children report "I am covered."

But during an interview, will you remember to return 2 for null nodes instead of 0? Will you remember to check left == 0 or right == 0 before checking left == 1 or right == 1? Will you remember the final root check at the end?

Understanding a solution once is not the same as being able to reproduce it under pressure. Spaced repetition bridges that gap. You practice writing the solution from scratch at increasing intervals, and each time the three states and their priority order become more automatic.

The bottom-up greedy pattern and the post-order state machine are reusable building blocks. Once you can recall them reliably, you can apply them to new tree problems you have never seen before.

Related posts

• Binary Tree Maximum Path Sum - Another post-order DFS that returns one value to the parent while tracking a different global answer. Same skeleton, different problem.
• House Robber III - Tree DP where each node chooses between two states (rob or skip). Similar bottom-up decision making on a tree.
• Lowest Common Ancestor of a Binary Tree - Bottom-up recursion where each node reports information to its parent. A foundational tree pattern worth knowing.