We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Cameras

Difficulty: Hard

Problem Description

You are given the root of a binary tree. We install cameras on the tree nodes where 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.

Key Insights

  • Each camera can monitor its parent, itself, and its immediate children.
  • The problem can be approached using Depth-First Search (DFS) to traverse the tree.
  • We can categorize the state of each node as monitored by a camera, monitored without a camera, or not monitored.
  • A post-order traversal is effective for determining the placement of cameras in a bottom-up manner.

Space and Time Complexity

Time Complexity: O(N) - Each node is visited once during the DFS traversal. Space Complexity: O(H) - The space complexity is determined by the height of the tree due to the recursion stack.

Solution

We will use a Depth-First Search (DFS) approach to traverse the binary tree and determine the placement of cameras. We will define three states for each node:

  1. Camera: The node has a camera installed.
  2. Monitored: The node is monitored by a camera from its children.
  3. Not Monitored: The node is not monitored by any camera.

The algorithm will recursively check the status of each node's children and decide if a camera should be installed at the current node based on their states.

Code Solutions

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        # Define states
        NOT_MONITORED = 0
        MONITORED = 1
        CAMERA = 2
        
        self.camera_count = 0
        
        def dfs(node):
            if not node:
                return MONITORED
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # If either child is not monitored, place a camera here
            if left == NOT_MONITORED or right == NOT_MONITORED:
                self.camera_count += 1
                return CAMERA
            
            # If either child has a camera, this node is monitored
            if left == CAMERA or right == CAMERA:
                return MONITORED
            
            # This node is not monitored
            return NOT_MONITORED
        
        # Start DFS from the root
        if dfs(root) == NOT_MONITORED:
            self.camera_count += 1
            
        return self.camera_count
← Back to All Questions