class Solution {
  
  Set<TreeNode> covered;
  int numCameras = 0;
  public int minCameraCover(TreeNode root) {
    covered = new HashSet<>();
    numCameras = 0;
    
    // null node is always covered
    covered.add(null);
    
    getCover(root, null);
    
    // if root node is not covered, add a camera at root node
    if (!covered.contains(root)) {
      numCameras++;
    }
    
    return numCameras;
  }
  
  public void getCover(TreeNode node, TreeNode parent) {
    if (node != null) {
      getCover(node.left, node);
      getCover(node.right, node);
      
      if (parent == null && !covered.contains(node) || 
          !covered.contains(node.left) || 
          !covered.contains(node.right)) {
        // add a camera to current node
        numCameras++;
        
        // update covered nodes
        covered.add(node);
        covered.add(parent);
        covered.add(node.left);
        covered.add(node.right);
      }
    }
  }
}