Binary Tree Cameras

Binary Tree Cameras is a classic greedy tree-DP problem. It looks like it needs heavy bookkeeping, but a single post-order DFS that returns one of three small states solves it optimally — and it teaches the powerful "decide bottom-up, let parents fix what children leave undone" pattern.

The slow way first

You could try every subset of nodes, place cameras on each subset, and check whether the whole tree is covered — then keep the smallest valid subset. With n nodes that is 2ⁿ subsets, which is hopeless for anything but a tiny tree.

The question to ask: can I decide each camera locally instead of globally? A camera is only useful relative to its neighbors, so maybe a single bottom-up pass — where each node tells its parent how much help it still needs — is enough.

The idea: three states, decided bottom-up

Run a post-order DFS (children before parent). Each call returns one of three states describing the node it just finished:

• needs-cover — this node has no camera and nothing is watching it.
• has-camera — a camera sits on this node.
• covered — this node is watched by a child camera but has none itself.

The greedy rule at each node: if any child is needs-cover, you are its only remaining chance to cover it, so place a camera here. Otherwise, if any child has a camera, you are already watched, so return covered. Otherwise return needs-cover and let your parent deal with it.

The trick that makes this optimal: we place cameras as high up as possible (on parents of uncovered nodes), because a higher camera also covers the parent and siblings — so it does the most work.

Walk through it

Step through the animation. We dive to the deepest leaf 4, which returns needs-cover. Its parent 2 sees a needs-cover child and places a camera. Back up at node 1, the other leaf 3 returns needs-cover, forcing a second camera on node 1 — which conveniently also covers the root 0. The root comes back covered, so no extra camera is needed. Final answer: 2 cameras.

Pseudocode

cameras = 0
define dfs(node):
    if node is None: return COVERED        # a missing child never needs cover
    left  = dfs(node.left)                 # post-order: children first
    right = dfs(node.right)
    if left or right is NEEDS-COVER:
        cameras += 1                        # we must cover that child
        return HAS-CAMERA
    if left or right is HAS-CAMERA:
        return COVERED                      # a child camera watches us
    return NEEDS-COVER                      # ask our parent to cover us
if dfs(root) is NEEDS-COVER:
    cameras += 1                            # root has no parent to help it
return cameras

The Python solution

def min_camera_cover(root):
    cameras = 0
    NEED, CAM, COVERED = 0, 1, 2
 
    def dfs(node):
        nonlocal cameras
        if node is None:
            return COVERED
        left = dfs(node.left)
        right = dfs(node.right)
        if left == NEED or right == NEED:
            cameras += 1
            return CAM
        if left == CAM or right == CAM:
            return COVERED
        return NEED
 
    if dfs(root) == NEED:
        cameras += 1
    return cameras

• NEED, CAM, COVERED are the three states a node can be in after its DFS call.
• A None child returns COVERED — it never demands a camera, which keeps leaves clean.
• We recurse into both children first (post-order), then decide based on their returns.
• The heart of the greedy: if either child is NEED, we place a camera here (cameras += 1) and return CAM.
• If we got here without placing a camera but a child has one, we are COVERED; otherwise we are NEED and push the decision up.
• After the DFS, the root has no parent, so if it came back NEED we add one last camera.

Complexity

Each node is visited exactly once, so time is O(n). The only extra space is the recursion stack, which is O(h) for tree height h (O(n) for a degenerate tree, O(log n) when balanced).

When this pattern shows up

Practice