Problem statement

You are given the root of a binary tree. A camera can be installed on any node, and a camera watches the node it sits on, that node's parent, and that node's immediate children.

Return the minimum number of cameras needed so that every node of the tree is watched.

Every node's value is 0 — only the shape of the tree matters.

Example 1

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera on the root's left child watches it, the root and both of its children.

Example 2

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: The tree is a chain of five nodes; cameras on the second and fourth nodes from the top watch all five.

Example 3

Input: root = [0]
Output: 1
Explanation: A lone node must hold the camera itself.

Constraints

• The number of nodes is in the range [1, 1000]
• Node.val == 0

Hints for Binary Tree Cameras

1. Hint 1

   A leaf should never hold a camera: moving it to the leaf's parent watches everything it did and more.

2. Hint 2

   Work bottom-up. Each node can report one of three states to its parent: it needs watching, it holds a camera, or it is watched without a camera.

3. Hint 3

   Put a camera on a node exactly when some child needs watching. A missing child counts as watched. At the end, the root may still need a camera of its own.

How to solve Binary Tree Cameras

Decide cameras from the leaves upward. A leaf's parent is always a better camera spot than the leaf, and in general a node only needs a camera when one of its children would otherwise go unwatched — so a post-order pass with three states places cameras greedily and optimally.

Approach

1. Let visit(node) return 0 = needs watching, 1 = holds a camera, 2 = watched without a camera; a missing child returns 2.
2. Visit both children first.
3. If either child returns 0, install a camera here (count it) and return 1.
4. Otherwise, if either child returns 1, this node is watched: return 2.
5. Otherwise both children are watched without cameras, so this node is not: return 0 and let the parent handle it.
6. After visiting the root, add one more camera if it returned 0.

Why it works

Consider the deepest unwatched node. Any camera that watches it sits on it, its parent or a child; its children are already watched (they are deeper), so a camera on the parent watches a superset of what the other choices would newly watch. The greedy makes exactly that choice each time, so an exchange argument turns any optimal placement into the greedy one without adding cameras.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• A missing child must count as watched, or every leaf would force a camera on itself.
• The root has no parent to rescue it — check its state after the pass.
• Check 'a child needs watching' before 'a child holds a camera': a node with one of each still needs its own camera.

Reference solution

Python

from typing import Optional

def minCameraCover(root: Optional[TreeNode]) -> int:
    cameras = [0]

    # 0 = needs watching, 1 = holds a camera, 2 = watched without one
    def visit(node):
        if node is None:
            return 2
        left, right = visit(node.left), visit(node.right)
        if left == 0 or right == 0:
            cameras[0] += 1
            return 1
        if left == 1 or right == 1:
            return 2
        return 0

    if visit(root) == 0:
        cameras[0] += 1
    return cameras[0]

Java

public static int minCameraCover(TreeNode root) {
    int[] cameras = { 0 };
    if (cameraVisit(root, cameras) == 0) cameras[0]++;
    return cameras[0];
}

// 0 = needs watching, 1 = holds a camera, 2 = watched without one
static int cameraVisit(TreeNode node, int[] cameras) {
    if (node == null) return 2;
    int left = cameraVisit(node.left, cameras), right = cameraVisit(node.right, cameras);
    if (left == 0 || right == 0) { cameras[0]++; return 1; }
    if (left == 1 || right == 1) return 2;
    return 0;
}

C++

int minCameraCover(TreeNode* root) {
    int cameras = 0;
    // 0 = needs watching, 1 = holds a camera, 2 = watched without one
    function<int(TreeNode*)> visit = [&](TreeNode* node) -> int {
        if (!node) return 2;
        int left = visit(node->left), right = visit(node->right);
        if (left == 0 || right == 0) { cameras++; return 1; }
        if (left == 1 || right == 1) return 2;
        return 0;
    };
    if (visit(root) == 0) cameras++;
    return cameras;
}

JavaScript

var minCameraCover = function(root) {
    var cameras = 0;
    // 0 = needs watching, 1 = holds a camera, 2 = watched without one
    var visit = function(node) {
        if (node === null) return 2;
        var left = visit(node.left), right = visit(node.right);
        if (left === 0 || right === 0) { cameras++; return 1; }
        if (left === 1 || right === 1) return 2;
        return 0;
    };
    if (visit(root) === 0) cameras++;
    return cameras;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Maximum Path Sum Between Two Leaves Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Sum BST in Binary Tree Hard
• Recover a Tree From Preorder Traversal Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Maximum Path Sum Hard