Binary Tree Cameras Problem

Problem

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.

Examples

Example 1:

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

Example 2: 

Input:
root = [0,0,null,0,null,0,null,null,0]
Output:
 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Node.val == 0

Solution

Method 1 - Post-order Traversal

We can cover the nodes with camera in these ways:

  1. A node in binary tree can be covered in 4 ways - by placing camera on - 1) itself, 2) parent, 3) left child, 4) right child.
  2. A root node can be covered in 3 ways - by placing camera on - 1) itself, 2) left child, 3) right child
  3. A leaf node can be covered in 2 ways - by placing camera on - 1) itself, 2) parent

Now, if we set a camera at the leaf (case 3), the camera can cover only leaf and its parent, but if we set a camera at its parent(case 1 or 2), the camera can cover the leaf, its parent and its sibling. In latter approach, we require less cameras to cover the nodes.

So, we can start placing cameras on the leaves parent and continue till all nodes are covered. As, we are taking decision based on children, we will do post-order traversal.

Algorithm

We can use enum MonitoringStatus - where we have 3 statuses:

  1. Not Monitored yet
  2. Monitored without camera on it
  3. Monitored with camera on it

We start the dfs which returns MonitoringStatus: 0. Initiate numCameras to 0

  1. For leaf nodes, we will return NotMonitored
  2. For parent node of leaf, we return MonitoredWithCam, and increment numCameras.
  3. For any other node, we return MonitoredWithoutCam

Code

Java
class Solution {
	// enum MonitoringStatus {
	// 	NotMonitored, MonitoredWithoutCam, MonitoredWithCam
	// } 
    private final int NotMonitored = 0;
    private final int MonitoredWithoutCam = 1;
    private final int MonitoredWithCam = 2;
	private int numCameras = 0;
    public int minCameraCover(TreeNode root) {
        var monitoringStatus = dfs(root);
        if (monitoringStatus == NotMonitored) {
	        numCameras++;
        }
        return numCameras;
    }
    private int dfs(TreeNode root) {
        if (root == null) {
	        return MonitoredWithoutCam;
	    }
        
        var left = dfs(root.left);
        var right = dfs(root.right);
        
        if (left == NotMonitored || right == NotMonitored) {
            numCameras++;
            return MonitoredWithCam; 
        }
        
        if (left == MonitoredWithCam || right == MonitoredWithCam) {
	        return MonitoredWithoutCam; 
        }
            
        
        return NotMonitored;
    }
}

Complexity

  • Time: O(n)
  • Space: O(h) => O(n) (assuming recursive stack)