data-structures binary-tree breadth-first-search

Getting Wrong Answer in "Binary Tree Cameras" LeetCode Hard

I get a Wrong Answer in LeetCode question 968. Binary Tree Cameras:

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.

My approach

I count the number of cameras required at odd or even levels and the minimum of them will be the answer. If any of the even or odd level camera's count is zero then we need at least 1 camera in case there's a node present in the tree.

My Code

class Solution
{
public:
    int minCameraCover(TreeNode *root)
    {
        int ans = 0;
        if (root)
        {
            // cameras at odd or even level
            int odd = 0, even = 0;
            bool isEvenLevel = false;
            queue<TreeNode*> q;
            q.push(root);
            while (q.size())
            {
                int sz = q.size();                
                // adding the count of cameras required at each level
                if (isEvenLevel) even += sz;
                else odd += sz;
                while (sz--)
                {
                    root = q.front(), q.pop();
                    if (root->left) q.push(root->left);
                    if (root->right) q.push(root->right);
                }
                isEvenLevel = !isEvenLevel;
            }
            // we're adding minimum no. of cameras either it be on odd levels or even levels
            ans = min(odd, even);
            // for a single root we have to add atleast 1 camera
            if (!ans) ans = max(odd, even);
        }
        return ans;
    }
};

Test case for which my solution failed

Input: [0, 0, null, null, 0, 0, null, null, 0, 0]
My Ouput: 3
Expected Output: 2

Question

Why is my answer not correct? What have I to change without changing my approach? -- I think my approach can work.

Solution

Why is my answer not correct?

The tree for which your code gives the wrong answer, looks like this:

Your code will place cameras like so:

      0 camera
     / 
    0
     \
      0 camera
     /
    0
     \
      0 camera
     /
    0

But the optimal placement is:

What have I to change without changing my approach?

Your approach has these characteristics:

It assumes that the vertical distance between two cameras on the same path should be 2, but that is not true, as that generally means that the node between two such cameras is monitored by both cameras. In some cases this can be avoided, by making the vertical distance between cameras 3. This is the case in the above test case.
It assumes that the optimal solution with cameras on a particular level, will not have cameras on the levels just above and below that level. This is not generally true. Take for example the following tree:
```
        0
       / \
      1   2
     / \
    3   4
   /   / \
  5   6   7
 / \
8   9
```
Your code will return 5 for this tree, but an optimal solution can do it with just 3 cameras, placed at the nodes 0, 4 and 5. An optimal solution needs to place cameras at both levels 3 and 4.
It assumes that if a camera is positioned on a certain level, that all nodes on that level need a camera. Again, this is not true, as can be seen in the example above.

In conclusion: your algorithm is cannot be tuned to work in all cases. The approach is based on assumptions that are not true. If this were the solution, the problem would not have been marked "hard". You'll have to go back to the drawing board and think of an entirely different approach.

Hint 1:

Apply a bottom up approach

Hint 2:

When going upwards through the tree, delay the placing of cameras as much as possible

Hint 3:

A node can be in three states: it has a camera, it can be monitored by a camera, it is node monitored by a camera

Hint 4:

If we know the state of the child/children of a node, we can decide what the state should be of the current node (potentially placing a camera)

Spoiler: Solution in C++

#define NOT_MONITORED 0 #define CAMERA 1 #define MONITORED 2 class Solution { public: int dfs(TreeNode* node, int &camCount) { if (node == nullptr) { return MONITORED; } int stateLeft = dfs(node->left, camCount); int stateRight = dfs(node->right, camCount); // state depends on states of children int state = (min(stateLeft, stateRight) + 1) % 3; if (state == CAMERA) { camCount++; } return state; } int minCameraCover(TreeNode* root) { int camCount = 0; int state = dfs(root, camCount); return camCount + (int)(state == NOT_MONITORED); } };