LeetCode 968: Binary Tree Cameras

Problem Restatement

We are given the root of a binary tree.

We may install cameras on tree nodes. A camera at a node can monitor:

1. Its parent
2. Itself
3. Its immediate children

Return the minimum number of cameras needed to monitor every node in the tree.

The official constraints say the tree has between 1 and 1000 nodes, and every node value is 0.

Input and Output

Example function shape:

def minCameraCover(root: Optional[TreeNode]) -> int:
    ...

Examples

Example 1:

root = [0, 0, None, 0, 0]

Output:

1

One camera can cover all nodes if placed on the internal child node.

Example 2:

root = [0, 0, None, 0, None, 0, None, None, 0]

Output:

2

At least two cameras are needed to cover every node.

First Thought: Try Every Camera Placement

A direct approach is to try every subset of nodes as camera positions.

For each subset, check whether all nodes are covered.

But a tree with n nodes has:

2 ** n

possible subsets.

With up to 1000 nodes, this is impossible.

We need a local greedy rule.

Key Insight

A camera placed at a leaf is usually inefficient.

A leaf camera covers:

1. The leaf
2. Its parent

But a camera placed at the parent covers:

1. The parent
2. The leaf
3. The parent’s other child, if present
4. The grandparent

So when a leaf needs coverage, it is better to place the camera at its parent.

This suggests a bottom-up traversal.

We decide what a node needs after seeing the states of its children.

Node States

Use postorder DFS.

Each node returns one of three states:

A None child is considered covered:

if node is None:
    return COVERED

A missing node does not need a camera.

Greedy Rules

After processing the left and right children:

Rule 1: If any child needs a camera, place a camera here

if left == NEEDS_CAMERA or right == NEEDS_CAMERA:
    cameras += 1
    return HAS_CAMERA

This covers the current node, both children, and the parent.

Rule 2: If any child has a camera, this node is covered

if left == HAS_CAMERA or right == HAS_CAMERA:
    return COVERED

The current node is monitored by that child camera.

Rule 3: Otherwise, this node needs a camera from its parent

return NEEDS_CAMERA

This happens when both children are covered but have no cameras.

Algorithm

1. Set cameras = 0.
2. Run postorder DFS.
3. For each node:
   • Get left child state.
   • Get right child state.
   • If any child needs a camera, place a camera here.
   • Else if any child has a camera, mark this node covered.
   • Else mark this node as needing a camera.
4. After DFS, if the root still needs a camera, add one more camera.
5. Return cameras.

Correctness

The algorithm makes decisions bottom-up.

A leaf has two None children. Since None children are covered and have no cameras, the leaf returns NEEDS_CAMERA.

When a parent sees that a child needs a camera, placing a camera at the parent is optimal. It covers that child, the parent itself, the sibling child, and possibly the grandparent. Placing the camera lower at the child would cover fewer useful nodes.

If a child already has a camera, the current node is covered. Adding another camera at the current node would be unnecessary at this moment, so the node returns COVERED.

If neither child has a camera and neither child needs one, then the children are covered without cameras. The current node is not covered by them, so it must ask its parent for coverage.

These cases cover all possible child-state combinations.

The only node without a parent is the root. If DFS finishes and the root still needs a camera, the algorithm adds one camera at the root. Therefore, every node is covered.

Because the algorithm places a camera only when a child cannot otherwise be covered from below, every placed camera is necessary. Therefore, the total number of cameras is minimum.

Complexity

Let n be the number of nodes.

Here, h is the height of the tree.

In the worst case, a skewed tree has h = n.

Implementation

from typing import Optional

# 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:
        NEEDS_CAMERA = 0
        HAS_CAMERA = 1
        COVERED = 2

        cameras = 0

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal cameras

            if node is None:
                return COVERED

            left = dfs(node.left)
            right = dfs(node.right)

            if left == NEEDS_CAMERA or right == NEEDS_CAMERA:
                cameras += 1
                return HAS_CAMERA

            if left == HAS_CAMERA or right == HAS_CAMERA:
                return COVERED

            return NEEDS_CAMERA

        if dfs(root) == NEEDS_CAMERA:
            cameras += 1

        return cameras

Code Explanation

We define three states:

NEEDS_CAMERA = 0
HAS_CAMERA = 1
COVERED = 2

A missing child returns COVERED:

if node is None:
    return COVERED

This prevents us from placing cameras for nonexistent nodes.

The DFS is postorder:

left = dfs(node.left)
right = dfs(node.right)

We need child states before deciding the current node state.

If either child needs a camera:

if left == NEEDS_CAMERA or right == NEEDS_CAMERA:
    cameras += 1
    return HAS_CAMERA

we place a camera at the current node.

If a child has a camera:

if left == HAS_CAMERA or right == HAS_CAMERA:
    return COVERED

then the current node is already monitored.

Otherwise:

return NEEDS_CAMERA

the current node is uncovered and asks its parent for a camera.

Finally, the root needs special handling:

if dfs(root) == NEEDS_CAMERA:
    cameras += 1

The root has no parent, so if it asks for a camera, we must place one at the root.

Testing

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root = build_tree([0, 0, None, 0, 0])
    assert s.minCameraCover(root) == 1

    root = build_tree([0, 0, None, 0, None, 0, None, None, 0])
    assert s.minCameraCover(root) == 2

    root = build_tree([0])
    assert s.minCameraCover(root) == 1

    root = build_tree([0, 0, 0])
    assert s.minCameraCover(root) == 1

    root = build_tree([0, 0, 0, 0, 0, 0, 0])
    assert s.minCameraCover(root) == 2

    print("all tests passed")

run_tests()

Test meaning: