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 1:**

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

**Example 2:**

**Input:**[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.

## Greedy approach

private static int CoverLogic(TreeNode node, Stack<TreeNode> stack, HashSet<TreeNode> covered, int minCamera) { //if node has any uncovered child, then cover it and it's parent(if any) if ((node.left != null && !covered.Contains(node.left)) || (node.right != null && !covered.Contains(node.right))) { minCamera++; covered.Add(node); if (stack.Any()) //has parent { //cover parent too covered.Add(stack.Peek()); } } //if node is root and is not covered, then cover it else if (!stack.Any() && !covered.Contains(node)) { minCamera++; covered.Add(node); } return minCamera; } public int MinCameraCover(TreeNode root) { int minCamera = 0; //Set contains, list of all coverted nodes HashSet<TreeNode> covered = new HashSet<TreeNode>(); //Iterative - POST Order traversal Stack<TreeNode> stack = new Stack<TreeNode>(); while (root != null || stack.Any()) { while (root != null) { stack.Push(root); root = root.left; } TreeNode temp = stack.Peek(); if (temp.right == null) { temp = stack.Pop(); //Console.Write(temp.val + " "); minCamera = CoverLogic(temp, stack, covered, minCamera); //if the popped elemnt is the right of its parent while (stack.Any() && temp == stack.Peek().right) { temp = stack.Pop(); //Console.Write(temp.val + " "); minCamera = CoverLogic(temp, stack, covered, minCamera); } } else { root = temp.right; } } return minCamera; }