Photo by Rishabh Varshney on Unsplash

Binary Tree Cameras — Amazon Interview Question

968. Binary Tree Cameras

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Understanding the problem:

Since we want to minimize the number of cameras, one thing is clear we don't place cameras at the leaf node. So we can trace from leaf to root. This makes DFS the most likely choice to address the problem. But as we retrace back up, we need to exchange information between nodes to see if the current node needs a camera or not. If the previous node already has a camera we don't need a camera. To summarize we have the following things to consider:

If the current node is a leaf node, then we don't need a camera.
If we don't have a camera on the current node then the parent needs it.
If the current node has a camera then its parent does not need a camera.

We can assign different values to indicate those states. -1 from children means to put a camera. 1 from any children means no camera.

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: TreeNode) -> int:
        def dfs(node):
            l=0
            r=0
            if (node.left is None and node.right is None):
                return -1
            if node.left:
                l = dfs(node.left)
            if node.right:
                r = dfs(node.right)
            if(l == -1 or r == -1):
                self.count += 1
                return 1
            if(l == 0 and r == 0):
                return -1
            if(l == 1 or r == 1):
                return 0
        self.count=0
        cams = dfs(root)
        if(cams == -1):
            self.count += 1
        return self.count

Complexity Analysis

• Time Complexity: O(N) where N is the number of nodes in the binary tree
• Space Complexity: space for recursive calls stacks which may be N.

Happy Coding !!!