Binary Tree Cameras — LeetCode Solve using Depth First Search Recursive method

Hey everyone, Hope all are doing good. In this article, we’ll learn how to solve one of the Hard problems in LeetCode “Binary Tree Cameras”.

Image source google.com

Problem statement

Given a binary tree, we need to install cameras onto the nodes that can cover itself, its parent and its immediate children. Find minimum no. of cameras required to cover all the nodes in the binary tree.

Binary Tree Cameras - LeetCode

Approach

Any binary tree problem could be imagined to solve using Depth First Search traversal method. Means that we are trying to solve for one subtree / one node that can be easily recurred to solve for the whole tree.

For this problem, we can come up with DFS recursive method which solves for one node and one subtree first and based on its result, it can solve further.

Let’s take one node for instance, what to do in case we have only one node in the binary tree and that is the root node. Hmm. of course we need a camera to cover that guy. Hence put a camera over there.

// Tree contains only one node.
if (node.left == null && node.right == null) 
    noofcameras++;

Let’s take a subtree has three nodes one root, left and right. For that root node we know that those are leaf nodes. Any leaf node must be covered by its parent. Hence we must install a camera to the root node.

// Tree contains one root, left and right.
if (leftNode == leaf || rightNode == leaf) 
    noofcameras++;

So, here if you see we are referring to a result or state from left and right child and based on that state we need to go further and decide whether to put a camera to the current node or letting the parent to have a camera to cover the current node.

Before going deeper into DFS recursion base cases, we need to understand there are few states involved to make decision.

Let’s define various states that a node can be. And based on that we will be able to decide our return value.

const nothing = 0;
const leaf = 1;
const covered = 2;
const pleasecoverme = 3;
const hascamera = 4;

Let me explain each state one by one.

State “nothing”

In our recursive method, let’s call it as “util”, a parameter named “node” is defined. As a base case if the node is referring to null, then return “nothing”

State “leaf”

If the parameter “node” is referring to a valid node but its left and right children are referring to null, then return “leaf”.

State “covered”

In order to decide to this state, we need state information from left child and right child. If any one of our children (left or right) is in the state “hascamera” then return “covered” because it has been covered by any one them.

State “pleasecoverme”

This is one of the most important state that we need to decide on. This state can also contribute to an optimisation. Means the current node is requesting to the parent node to cover me instead of strictly having a camera here. By doing this, we are letting parent to cover me and as well as my sibling. So only one camera is needed.

How to decide to this state — Well this is the default state to be returned by a node when none of the conditions above hits. That is for current node,

• left and right are not leaf nodes
• left or right child isn’t having a camera
• left or right child is not asking for coverage that is at least one child’s state isn’t “pleasecoverme”

Thus, it exactly means that either left or right or both are in the state “covered”.

State “hascamera”

Whenever we decide to have a camera in the current node, we need to increment no of cameras and return this state.

Watch the video below for Hands on implementation in JavaScript :)

Happy solving :)

Cheersss