Binary Tree Cameras

Hard
0/120
Average time to solve is 50m
profile
Contributed by
18 upvotes
Asked in companies
UberOYOAmazon

Problem statement

Given a binary tree, we need to install cameras on the nodes of the tree. Each camera at a node monitors its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image will be:

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).
Note : 
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format: 
For each test case, return an integer denoting the minimum number of cameras needed to monitor all nodes of the tree.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= DATA <=10^5 and DATA != -1

Time limit: 1 sec
Sample Input 1:
2
0 1 -1 2 3 -1 -1 -1 -1
0 1 -1 2 -1 3 -1 -1 4 -1 -1
Sample Output 1:
1
2
Explanation for Sample Input 1:
For the first test case, we can monitor all the nodes if we place the camera at node - 1.

alt text

For the second test case, we can monitor all the nodes by placing cameras at nodes - 1, 3.

alt text

Sample Input 2:
2
0 -1 1 -1 -1
0 -1 -1
Sample Output 2:
1
1
Hint

Try to find the cases when we have only three nodes.

Approaches (2)
Dynamic Programming

Every node has two options either it can have a camera or it cannot. If a node has a camera, then it definitely covers itself, and if it doesn’t have a camera then there are two options either the children nodes cover the current node or the parent node covers the current node. 

 

A node can be of three types-

  1. Case - 0: ‘CURRENT_NODE’ is not monitored but all nodes in the subtree are monitored.
  2. Case - 1: ‘CURRENT_NODE’ is monitored but no camera. All nodes in the subtree of this node are also monitored.
  3. Case - 2: ‘CURRENT_NODE’ has a camera and all nodes in the subtree are monitored.

 

The algorithm is as follows:

  1. Do a depth-first-search on the binary tree which returns an array of size three, denoting the number of cameras corresponding to the three cases mentioned above.
  2. If the ‘CURRENT_NODE’ is null then return {0, 0, 1}, since for the leaf node we want ‘CASE2’ to be 1 as it is never optimal to place a camera on a leaf node.
  3. Do a depth-first search on the left subtree, and save the result to ‘LEFT_CHILD’.
  4. Do a depth-first search on the right subtree, and save the result to ‘RIGHT_CHILD’.
  5. Initialize ‘CASE0’ to LEFT_CHILD[1] + RIGHT_CHILD[1], since the ‘CURRENT_NODE’ is not monitored, so the most optimal choice will be that both the children nodes should be monitored but should have no camera.
  6. Initialize ‘CASE1’ to min( LEFT_CHILD[2] + min(RIGHT_CHILD[1], RIGHT_CHILD[2]), RIGHT_CHILD[2] + min(LEFT_CHILD[1], LEFT_CHILD[2]), since the ‘CURRENT_NODE’ is monitored but it has no camera means at least one of the children nodes should have a camera.
  7. Initialize ‘CASE2’ to 1 + min(LEFT_CHILD[0], LEFT_CHILD[1], LEFT_CHILD[2]) + min(RIGHT_CHILD[0], RIGHT_CHILD[1], RIGHT_CHILD[2]).
  8. Return {CASE0, CASE1, CASE2}.
Time Complexity

O(N), where ‘N’ is the total number of nodes in the binary tree.

 

Here we are just running a post-order-traversal in the binary tree and visiting each node exactly twice. So, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the total number of nodes in the binary tree.

 

The maximum recursive stack can grow up to the order of ‘N’ in the case of a skewed binary tree. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Binary Tree Cameras
Full screen
Console