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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Cameras

Number: 1008

Difficulty: Hard

Paid? No

Companies: DE Shaw, Amazon, Goldman Sachs, DP world, Microsoft, eBay, Adobe, Oracle, Meta, Google

Problem Description

Given the root of a binary tree, place cameras on some of the nodes so that every node is monitored. A camera at a node can monitor its parent, itself, and its immediate children. Determine the minimum number of cameras required to cover all nodes in the tree.

Key Insights

  • Use a DFS (depth-first search) to traverse the tree in postorder.
  • For each node, classify it with one of three states:
    • State 0: Node has a camera.
    • State 1: Node is covered by a camera (child or parent) but has no camera.
    • State 2: Node is not covered and needs a camera.
  • Place a camera at the current node if any child is in state 2.
  • If at least one child has a camera, mark the current node as covered.
  • For leaf nodes (or null nodes), consider them as covered for the sake of simplifying the DFS recurrence.

Space and Time Complexity

Time Complexity: O(N) where N is the number of nodes in the tree since each node is visited once. Space Complexity: O(H) due to the recursion stack, where H is the height of the tree.

Solution

We solve the problem using a DFS based on postorder traversal. At every node, inspect the state of its children. Based on that, decide if the current node should have a camera, be considered covered, or require a camera from its parent. The main challenge is to correctly propagate the state information upward to minimize the number of cameras while ensuring every node is covered. This strategy uses a greedy approach on the tree structure with three states.

Code Solutions

# 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:
        # Define states:
        # 0: Node has a camera.
        # 1: Node is covered, but has no camera.
        # 2: Node is not covered.
        
        self.camera_count = 0
        
        def dfs(node):
            if not node:
                # Null nodes are considered covered.
                return 1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # If any child is not covered, current node must have a camera.
            if left == 2 or right == 2:
                self.camera_count += 1
                return 0  # Place camera at current node.
            
            # If any child has a camera, current node is covered.
            if left == 0 or right == 0:
                return 1  # Covered but no camera.
            
            # Else, node is not covered.
            return 2
        
        if dfs(root) == 2:
            self.camera_count += 1
        return self.camera_count
← Back to All Questions