Leetcode – 968 – Binary Tree Cameras

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

1) If a node has any uncovered child, then cover it and it’s parent(if any)
2) If node is root and is not covered, then cover it

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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s