Binary Tree Cameras

February 7, 2024

Problem Statement #

Given a binary tree, your goal is to install cameras on the tree nodes in such a way that every node in the tree is monitored. A 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 given binary tree.

Note:

• Every node has at most one parent.
• Tree nodes are numbered uniquely.

Solution Approach #

This problem can be solved using a greedy algorithm and depth-first search (DFS). The idea is to place cameras at all leaf nodes’ parents. We traverse the tree from bottom to top, deciding whether to place a camera at each node based on the status of its children.

We can mark each node with three states:

• 0 if the node needs to be covered,
• 1 if the node has a camera,
• 2 if the node is covered but doesn’t have a camera.

Algorithm Steps #

1. Start by defining a recursive DFS function that operates on the current node. The function should return the state of the node.
2. If the current node is null, we return 2 (covered).
3. Recursively call DFS for the left and right children of the current node.
4. Decide the state of the current node based on its children’s states:
   • If any child needs to be covered (0), place a camera here (1) and increase the camera count.
   • If any child has a camera (1), the current node is covered (2).
   • Otherwise, the current node needs to be covered (0).
5. After the DFS traversal, check the root node’s state. If it needs coverage, add one more camera.
6. Return the total number of cameras needed.

Code (Python) #

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

def minCameraCover(root):
    def dfs(node):
        if not node: return 2
        left, right = dfs(node.left), dfs(node.right)
        
        if left == 0 or right == 0:
            nonlocal cameras
            cameras += 1
            return 1
        return 2 if left == 1 or right == 1 else 0

    cameras = 0
    if dfs(root) == 0: cameras += 1
    return cameras

# Example usage
root = TreeNode(0, TreeNode(0, TreeNode(0), TreeNode(0)))
print(minCameraCover(root))  # Output: 2

Time Complexity #

• O(N), where N is the number of nodes in the binary tree. Each node is visited exactly once.

Space Complexity #

• O(H), where H is the height of the binary tree. This space is used by the call stack during the DFS.