Binary Tree Cameras

hard binary tree dfs greedy

Problem

You are given the root of a binary tree. Install the minimum number of cameras on the tree nodes. Each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree.

Inputroot = [0, 0, null, 0, 0]

Output1

One camera placed on the lone middle node covers itself, its parent (the root), and its two children — the whole tree with a single camera.

tree (level-order, comma-separated, use null for empty)

NEED, CAM, OK = 0, 1, 2

def min_camera_cover(root):
    cameras = 0
    def dfs(node):
        nonlocal cameras
        if not node:
            return OK
        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 OK
        return NEED
    if dfs(root) == NEED:
        cameras += 1
    return cameras

const NEED = 0, CAM = 1, OK = 2;

function minCameraCover(root) {
  let cameras = 0;
  function dfs(node) {
    if (!node) return OK;
    const left = dfs(node.left);
    const right = dfs(node.right);
    if (left === NEED || right === NEED) {
      cameras++;
      return CAM;
    }
    if (left === CAM || right === CAM) return OK;
    return NEED;
  }
  if (dfs(root) === NEED) cameras++;
  return cameras;
}

class Solution {
    static final int NEED = 0, CAM = 1, OK = 2;
    int cameras = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == NEED) cameras++;
        return cameras;
    }

    private int dfs(TreeNode node) {
        if (node == null) return OK;
        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == NEED || right == NEED) {
            cameras++;
            return CAM;
        }
        if (left == CAM || right == CAM) return OK;
        return NEED;
    }
}

class Solution {
    static const int NEED = 0, CAM = 1, OK = 2;
    int cameras = 0;

    int dfs(TreeNode* node) {
        if (!node) return OK;
        int left = dfs(node->left);
        int right = dfs(node->right);
        if (left == NEED || right == NEED) {
            cameras++;
            return CAM;
        }
        if (left == CAM || right == CAM) return OK;
        return NEED;
    }
public:
    int minCameraCover(TreeNode* root) {
        if (dfs(root) == NEED) cameras++;
        return cameras;
    }
};

Explanation

We want the fewest cameras that watch every node, where a camera covers itself, its parent, and its children. The winning strategy is a greedy bottom-up DFS: put cameras as low as possible, only where they are actually forced.

Each call reports one of three states back to its parent: NEED (this node is not covered and wants help), CAM (this node has a camera), or OK (covered, but no camera here). A missing child returns OK so leaves don't force anything by themselves.

The rules at a node: if either child says NEED, we must place a camera here (it covers that child) and return CAM. If a child has a CAM, this node is already covered, so return OK. Otherwise both children are OK but nothing covers this node yet, so return NEED and push the problem upward.

Placing cameras at the parents of leaves is efficient because one such camera covers up to three nodes at once.

One last detail: after the DFS, if the root itself returned NEED, there is no parent above to cover it, so we add one final camera. For [0,0,null,0,0] a single camera on the middle node covers the whole tree, giving answer 1.

Time: O(n) Space: O(h)