968. Binary Tree Cameras - Leetcode Solution

Code Implementation

# 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):
        NOT_COVERED = 0
        HAS_CAMERA = 1
        COVERED = 2
        
        self.cameras = 0
        
        def dfs(node):
            if not node:
                return COVERED
            left = dfs(node.left)
            right = dfs(node.right)
            if left == NOT_COVERED or right == NOT_COVERED:
                self.cameras += 1
                return HAS_CAMERA
            if left == HAS_CAMERA or right == HAS_CAMERA:
                return COVERED
            return NOT_COVERED
        
        if dfs(root) == NOT_COVERED:
            self.cameras += 1
        return self.cameras

// /**
//  * Definition for a binary tree node.
//  * struct TreeNode {
//  *     int val;
//  *     TreeNode *left;
//  *     TreeNode *right;
//  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
//  * };
//  */
class Solution {
public:
    int cameras = 0;
    enum State { NOT_COVERED, HAS_CAMERA, COVERED };
    int dfs(TreeNode* node) {
        if (!node) return COVERED;
        int left = dfs(node->left);
        int right = dfs(node->right);
        if (left == NOT_COVERED || right == NOT_COVERED) {
            cameras++;
            return HAS_CAMERA;
        }
        if (left == HAS_CAMERA || right == HAS_CAMERA) {
            return COVERED;
        }
        return NOT_COVERED;
    }
    int minCameraCover(TreeNode* root) {
        if (dfs(root) == NOT_COVERED) cameras++;
        return cameras;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int cameras = 0;
    private static final int NOT_COVERED = 0;
    private static final int HAS_CAMERA = 1;
    private static final int COVERED = 2;
    
    public int minCameraCover(TreeNode root) {
        if (dfs(root) == NOT_COVERED) cameras++;
        return cameras;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) return COVERED;
        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == NOT_COVERED || right == NOT_COVERED) {
            cameras++;
            return HAS_CAMERA;
        }
        if (left == HAS_CAMERA || right == HAS_CAMERA) {
            return COVERED;
        }
        return NOT_COVERED;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minCameraCover = function(root) {
    const NOT_COVERED = 0, HAS_CAMERA = 1, COVERED = 2;
    let cameras = 0;
    function dfs(node) {
        if (!node) return COVERED;
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left === NOT_COVERED || right === NOT_COVERED) {
            cameras++;
            return HAS_CAMERA;
        }
        if (left === HAS_CAMERA || right === HAS_CAMERA) {
            return COVERED;
        }
        return NOT_COVERED;
    }
    if (dfs(root) === NOT_COVERED) cameras++;
    return cameras;
};

Problem Description

The Binary Tree Cameras problem asks you to determine the minimum number of cameras needed to monitor every node of a binary tree. Each camera can be placed on any node, and a camera at a node can monitor its parent, itself, and its immediate children.

You are given the root of a binary tree.
Each camera can cover its parent, itself, and its direct children.
Your goal: Find the smallest number of cameras needed so that every node is monitored.
All nodes must be covered, and cameras can only be placed on nodes (not between nodes).
Each node can only be covered once; cameras cannot be reused for multiple positions.

Thought Process

At first glance, it might seem reasonable to simply place cameras on every other node, or to try all possible combinations of camera placements to see which combination covers the tree with the fewest cameras. However, this brute-force method would be extremely inefficient, especially as the tree grows larger.

To optimize, we need to think about the tree structure and how a camera's coverage works. Since a camera covers its parent, itself, and its children, placing cameras at certain strategic nodes (typically the parents of leaves) can maximize coverage. The challenge is to ensure every node is covered while minimizing the number of cameras.

We can use a greedy, bottom-up approach, similar to how you might guard a museum: you start by protecting the most vulnerable spots (the leaves), and work your way up, only adding cameras where absolutely necessary.

Solution Approach

The optimal strategy is to traverse the tree from the bottom up (using post-order traversal) and decide at each node whether to place a camera, based on the state of its children.

Define States:
- NOT_COVERED: This node is not covered by any camera.
- HAS_CAMERA: This node has a camera installed on it.
- COVERED: This node is covered by a camera from its child or parent, but does not have a camera itself.
Recursive Traversal:
- Use a recursive function to traverse the tree in post-order (left, right, node).
- At each node, check the state of its children.
Decision Logic:
- If any child is NOT_COVERED, this node must have a camera (to cover that child).
- If any child has a camera, this node is COVERED.
- If both children are COVERED (but neither has a camera), this node is NOT_COVERED and may need to be covered by its parent.
Edge Case:
- After traversing, if the root is NOT_COVERED, add a camera at the root.
Efficiency:
- This approach ensures that cameras are only placed when absolutely necessary, always trying to push the responsibility up the tree.

Example Walkthrough

Consider the following binary tree:

Start at the leaves. The leftmost leaf (left child of root) is NOT_COVERED (no children).
The rightmost leaf (left child of the right child of root) is also NOT_COVERED.
Move up to their parents:
- The right child of root has a left child that is NOT_COVERED, so it must have a camera.
- The left child of root is a leaf, so it is NOT_COVERED.
Now, the root sees that its left child is NOT_COVERED and its right child has a camera. Since at least one child is NOT_COVERED, the root must have a camera.
In total, two cameras are used: one at the root, one at the right child of the root.

This covers all nodes with the minimum number of cameras.

Time and Space Complexity

Brute-force approach:
- Would involve trying all possible camera placements, leading to exponential time complexity: O(2^N), where N is the number of nodes.
Optimized approach (current solution):
- The algorithm visits each node exactly once, and does constant work at each step.
- Time Complexity: O(N), where N is the number of nodes in the tree.
- Space Complexity: O(H), where H is the height of the tree (due to recursion stack). In the worst case (skewed tree), H = N.

Summary

The Binary Tree Cameras problem is elegantly solved by a bottom-up, greedy approach that uses post-order traversal to minimize the number of cameras. By categorizing nodes into three states—NOT_COVERED, HAS_CAMERA, and COVERED—the algorithm ensures every node is monitored with the fewest cameras possible. This method is efficient, intuitive, and leverages the unique coverage property of the cameras in the tree structure.

AlgoMap.io

Want Help Cracking FAANG?