Last Updated: 11 Mar, 2021
Binary Tree Cameras
Hard
Asked in companies
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.
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:
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
Approaches
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-
- Case - 0: ‘CURRENT_NODE’ is not monitored but all nodes in the subtree are monitored.
- Case - 1: ‘CURRENT_NODE’ is monitored but no camera. All nodes in the subtree of this node are also monitored.
- Case - 2: ‘CURRENT_NODE’ has a camera and all nodes in the subtree are monitored.
The algorithm is as follows:
- 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.
- 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.
- Do a depth-first search on the left subtree, and save the result to ‘LEFT_CHILD’.
- Do a depth-first search on the right subtree, and save the result to ‘RIGHT_CHILD’.
- 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.
- 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.
- Initialize ‘CASE2’ to 1 + min(LEFT_CHILD[0], LEFT_CHILD[1], LEFT_CHILD[2]) + min(RIGHT_CHILD[0], RIGHT_CHILD[1], RIGHT_CHILD[2]).
- Return {CASE0, CASE1, CASE2}.
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.
Example - Let’s say, we have a binary tree of four nodes.
To cover the leaf nodes it is always optimal to give the camera to the parent because if leaf nodes are given cameras then two cameras have to be given and if the camera is given to a parent of the leaf nodes, then it not only covers itself, its children but also its parent. Using this observation, we can proceed bottom-up from the leaf node and pass information to the parent.
There are three cases about the information passed by the current node to the parent-
- If the current node needs a camera then the parent has no option other than having a camera.
- If the current node has a camera, then the parent is already covered, it’s optimal that we don’t place a camera at the parent.
- If the current node is covered, then instead of placing the camera at the parent, it’s optimal to place the camera at the parent of the parent.
The algorithm is as follows:
- Let’s define three states -1 if the current node needs a camera, 0 if the current node has a camera, 1 if the current node is covered.
- Do a depth-first-search on the binary tree which returns an integer, denoting the minimum number of cameras to be placed in the subtree rooted at ‘CURRENT_NODE’.
- If the ‘CURRENT_NODE’ is null then return 1, since we don’t want a leaf node to have a camera.
- Do a depth-first search on the left subtree, and save the result to ‘LEFT_CHILD’.
- Do a depth-first search on the right subtree, and save the result to ‘RIGHT_CHILD’.
- If ‘LEFT_CHILD’ == -1 or ‘RIGHT_CHILD’ == -1, then we have to place a camera here, so increment the ‘CAMERA_COUNT’ by 1 and return 0 i.e tell the parent node I’ve a camera.
- If ‘LEFT_CHILD’ == 0 or ‘RIGHT_CHILD’ == 0, then return 1 i.e tell the parent that the current node is already covered.
- Now, both children don't need a camera and they don’t have a camera, then tell the parent node to place a camera i.e return -1.
- Now, if the root of the tree demands a camera, our algorithm will ask for the root’s parent to have a camera.
- But, we don’t have such a node, we can simply increment ‘CAMERA_COUNT’ by 1 if the parent node return -1
Similar problems