If you are a programmer, binary trees are a must learn topic! 

Binary Tree Camera problem is a common question raised in most technical round interviews. It’s a relatively tougher problem and presented primarily to experienced candidates.

But recent graduates should prepare for this problem as well. Hence, if you want better detailing on this subject you are at the right place. 

In this article, we will explain how to determine the minimum number of cameras needed to monitor all nodes of a binary tree.

What is a Binary Tree Data Camera?

As a quick refresher, let’s define what a binary tree data structure is and the various types.

Binary tree is any tree-like structure with a maximum of two branches. These branches are known as children and the two are called ‘left’ and ‘right’ child.

The tree is represented by a pointer, with the root serving as the topmost node. In case the tree is empty, the root’s value is defined as NULL.

Every node in the tree can have three parts, which are: data, pointer to left child, pointer to the right child.

In a binary tree camera, you are given the roots of a binary tree. Each camera at its node will monitor the parent, itself or the immediate children.

Want to know more about it? Let’s study in detail! 

Input and Output Format to Solve the Binary Tree Camera Problem

Now let’s begin to solve the problem.

It asks us to install the cameras on the tree nodes so that all the nodes can be monitored. The cameras are capable of monitoring each node, the parent, and the immediate children.

Input format

First, let’s look at the tree and design the input format:

Input:

1

2 3

4 -1 5 6

-1 7 -1 -1 -1 -1

-1 -1

Here’s the explanation for the input format:

Level 1: The root node in the binary tree is 1

Level 2: The left child and right child are 2 and 3 respectively

Level 3: The left child of node 2 is 4 and it has no right child or null (-1). The left child of node 3 is 5 and the right child is 6.

Level 4: Left child of node 4 is null (-1) the right child is 7. The node 5 has no children, so (-1) and (-1). The node 6 has no children as well, so (-1) and (-1).

Level 5: Node 7 has no children, so null in both cases, (-1) and (-1)

The inputs end when all the nodes are null. In this case that’s Level 5.

Please note that the multi-line format illustrated above is just for clarity purposes. For real life programming, you’ll put together the sequence in a single line like this:

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

Output format

For every test case, the output should return an integer indicating the minimum number of cameras needed to monitor all the nodes.

Approaches

There are two approaches to solving the binary tree camera problem. As a programmer, you should know both these approaches.

Approach 1 - Using DFS traversal of the binary tree 

For every node, there are two possibilities. Either it can have a camera or it cannot. For nodes with cameras, they are covered by default. And in case they do not have cameras, there are two possibilities. Either the children node covers the current node or the parent does that.

Thus, by this approach, the node can be of following three types:

• Case 0 - The PRESENT_NODE is not monitored but the nodes in the children are
• Case 1 - The PRESENT_NODE is monitored but doesn’t have a camera of its own
• Case 2 - The PRESENT_NODE has a camera and all children nodes are monitored as well

To write an algorithm to solve this problem, here are the steps involved:

• On the binary tree, perform a depth-first-search. It’d return an array of size 3, each number corresponding to the three cases mentioned above.
• When the PRESENT_NODE is null, you should return {0,0,1}. It’s not ideal for leaf nodes to have cameras on them. So for leaf nodes, you want CASE2 to be 1
• Perform a depth-first search on the left child and place the result in LEFT_CHILD
• Likewise, perform the depth-first search on the right child and place the result in RIGHT_CHILD
• Initialize CASE0 to LEFT_CHILD[1] + RIGHT_CHILD[1]. That’s because the CURRENT_NODE isn’t monitored. Therefore, it’s an ideal situation for the children nodes to not have cameras and only be monitored
• Similarly, initialize CASE1 to min( LEFT_CHILD[2] + min(RIGHT_CHILD[1], RIGHT_CHILD[2]), RIGHT_CHILD[2] + min(LEFT_CHILD[1], LEFT_CHILD[2]). That’s because in this case, the PRESENT_NODE is monitored but doesn’t have a camera. Therefore, one of the child nodes should possess 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])
• Finally, return the array {CASE0, CASE1, CASE2}

Approach 2 - Bottom-Up Approach 

In this approach, you follow the bottom-up approach from leaf nodes to the parents and passing the information on where to place the cameras. Ideally, you’d want the parent nodes to have the cameras. That way they can cover themselves and also the child nodes and their respective parents.

For the information being passed, there could be three cases. These are:

• Place the camera on the parent node if the current node requires a camera.
• If there’s a camera on the current node and the parent is covered, do not place the camera on the parent node
• If the current node is covered, place the camera on the parent of the parent node

To write an algorithm for this approach, here are the steps:

• Take three states. 0 if there’s camera on the current node ; -1 if you need a camera on the current node; and 1 if current node is covered
• Perform a depth-first search and it should return an integer.
• You don’t need cameras in the child nodes. So if the PRESENT_NODE is null, return 1.
• Perform a depth-first search on the left child and place the result in LEFT_CHILD. Do the same for the right child and save results in RIGHT_CHILD
• When the child nodes need a camera (RIGHT_CHILD and LEFT_CHILD == -1), you place the camera here. Return 0 and increase the TOTAL_CAMERA by 1
• When RIGHT_CHILD and LEFT_CHILD == 0, return 1. This informs the parent node that children nodes are already covered
• Return -1 when the children nodes nor the parent nodes need a camera
• If the root requires a camera, you need to place the camera on the root’s parent node.

Subarray Sums Divisible by K

Besides binary tree cameras, another important programming approach is Subarray Sums Divisible by K. Here, for a given integer array number and a K integer, return the non-integer number of its subarray problem. 

Conclusion 

We hope that this piece of information has made you aware about the binary tree camera and the approaches it follows.

Use it in your problem statement and get effective results!