Binary Tree Cameras - Leetcode Solution

Problem Description: 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.

Solution: The main idea of solving this problem is to assign different states to each node and solve it using a bottom-up approach. There are three states assigned to each node:

1. State 0 represents that the node is not covered, and it requires a camera to monitor it.
2. State 1 represents that the node is covered, and it doesn't require a camera.
3. State 2 represents that the node has a camera installed on it

Applying the above states to all the nodes of the tree, we can convert the given problem into a Dynamic Programming problem, where we keep track of the minimum number of cameras required to cover all nodes of the subtree rooted at any given node.

The following are the solutions:

Approach 1: Using Recursion

Step 1: We create a recursive function dfs that takes a node and returns the state of the node.

Step 2: We use the states of each node to calculate the minimum number of cameras required to cover all nodes of the subtree rooted at any given node using the following conditions:

• If the current node is null, we return the state 1, as it is already covered.
• We traverse through the left and right subtrees, and obtain their respective states.
• If any of the child nodes are not covered, we install a camera on the current node and return a state 2.
• If both the child nodes are covered and none of them have any camera, we return a state 0.
• If both the child nodes have cameras installed on them, we return a state 1.

Step 3: Finally, we call the dfs function on the root node, and we count the number of cameras that are installed using the result.

Approach 2: Using Iteration with stack

Step 1: We create a Stack stack and add the root node to it.

Step 2: We also create a Dictionary state to store the states of each node in the tree.

Step 3: We traverse through the tree using a while loop, until the stack is empty.

Step 4: For each node in the stack, we check if it is null, and if it is, we move to the next node.

Step 5: Otherwise, we check if the left and right subtrees have been covered or not. We obtain their respective states using the state dictionary.

Step 6: If any of the child nodes are not covered, we install a camera on the current node and set state[node] to 2.

Step 7: If the left and right subtrees are already covered and none of them have any camera installed, we set state[node] to 0.

Step 8: If both the child nodes have cameras installed on them, we set state[node] to 1.

Step 9: Finally, if the root node is not covered, we install a camera on it and increase the count of cameras.

Step 10: We continue this process until the stack is empty, and then we return the count of cameras.

Both the approaches have a time and space complexity of O(n), where n is the number of nodes in the tree.

Implementation in Python:

Approach 1: Using Recursion

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.ans = 0
        
        def dfs(node):
            if not node:
                return 1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            if left == 0 or right == 0:
                self.ans += 1
                return 2
            
            if left == 2 or right == 2:
                return 1
            
            return 0
        
        if dfs(root) == 0:
            self.ans += 1
        
        return self.ans

Approach 2: Using Iteration with stack

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        stack = [root]
        state = {None:1}
        ans = 0
        
        while stack:
            node = stack[-1]
            
            if node.left not in state or node.right not in state:
                stack.append(node.left)
                stack.append(node.right)
            else:
                stack.pop()
                left = state[node.left]
                right = state[node.right]
                
                if left == 0 or right == 0:
                    ans += 1
                    state[node] = 2
                elif left == 2 or right == 2:
                    state[node] = 1
                else:
                    state[node] = 0
        
        if root and state[root] == 0:
            ans += 1
        
        return ans

1