Binary Tree Cameras

def minCameraCover(root):
    cams = 0
    def dfs(node):              # post-order
        nonlocal cams
        if not node:
            return 2            # missing: watched
        left, right = dfs(node.left), dfs(node.right)
        if left == 0 or right == 0:
            cams += 1
            return 1            # camera here
        if left == 1 or right == 1:
            return 2            # watched by a child
        return 0                # parent covers it
    if dfs(root) == 0:
        cams += 1               # fix the root
    return cams

Binary Tree Cameras. Put cameras on a binary tree's nodes. A camera watches its node, its parent and its children. Return the fewest cameras that watch every node. Here, each node is a museum room.

A root, one child, two grandchildren: one camera on the child sees all four. Five rooms in a single chain need two cameras.

The naive way tries every set of camera rooms and checks that every room is watched. That's two to the n sets, each checked in n steps. Thirty rooms means over a billion sets.

The key idea: never put a camera on a leaf. Its parent sees the leaf, and more. So work bottom up. Each room reports a state: zero, not watched. One, has a camera. Two, watched without one. A missing child counts as two, so a leaf reports zero. If any child is zero, put a camera here. Else, if any child has a camera, report two. Otherwise, report zero and let the parent cover it.

In code, a post-order helper returns the state and counts cameras. If the root ends at zero, add one more.

Let's try eight rooms. The three leaves report zero, so their parents get cameras. One level up, both rooms see a camera and report two. The root sees only twos, so it reports zero. Nothing is above it, so it takes the third camera.

Each room is visited once: order n time. The recursion goes as deep as the tree: order h space.

Never on a leaf, three states, fix the root. That's Binary Tree Cameras.