Corona Vaccine GeeksforGeeks Problem of the day | Binary Tree Cameras | Leetcode 968. | Binary Tree

Geek has developed an effective vaccine for Corona virus and he wants each of the N houses in Geek Land to have access to it. Given a binary tree where each node represents a house in Geek Land, find the minimum number of houses that should be supplied with the vaccine kit if one vaccine kit is sufficient for that house, its parent house and it's immediate child nodes.



Example 1:

Input:
1
/ \
2 3
\
4
\
5
\
6

Output:
2
Explanation:
The vaccine kits should be
supplied to house numbers 1 and 5.
Example 2:

Input:
1
/ \
2 3
Output:
1
Explanation:
The vaccine kits should be
supplied to house number 1.

Check out our other playlists:

Dynamic Programming:

Trees:

Heaps and Maps:

Arrays and Maths:

Bit Manipulation:

Greedy Algorithms:

Sorting and Searching:

Strings:

Linked Lists:

Stack and Queues:

Two Pointers:

Graphs, BFS, DFS:

Backtracking:

Non- DSA playlists:

Probability:

SQL-Basic Join functions:

SQL-Basic Aggregate functions:

[probabilitycodingisfunis]

Time Complexity -> O(N)
int novaccines = 0;
int supplyVaccine(Node* root){
// Your code goes here

if(vaccine(root)=="want")
novaccines++;
return novaccines;
}

string vaccine(Node* root)
{
if(root==NULL)
return "ok";
string left =vaccine(root->left);
string right =vaccine(root->right);

if(left=="want" || right =="want")
{
novaccines++;
return "provide";
}
else if(left=="provide" || right =="provide")
return "ok";
return "want";
}

[iamnoob]

WOW, Wow, Fantastic explanation . Thank you

[Nikita-hvjm]

thanks a lot for such an awesome explanation

[sigma]

Mind blowing dude . Hats off. Breaked all the limits

[aryanpatidar]

quite a fresh and unique take on question

[HeyRajSingh]

"Please add POP filter with mic" -- suggestions
Because the pop pop air sound is disturbing...

[pateladarsh]

Amazing, Thank you for making videos ... ur videos are very helpful

[shadowaj]

Ahhh amazing and very gracefully explained. After this go and try out leetcode binary tree camera 📷

[Man_of_Culture.]

I think there should be one more if condition i.e when from both left and right child gives "ok" then node should itself provide vaccine . Please correct me.

[MilindGupta]

Watching this again forgot how did i approached it :\

[pranshukashyap]

In the Question, it's given that the input tree is a binary tree but in some of your examples you had taken a tree with node having more than 2 children, but the overall explanation and solution was really awesome !! Nice Approach ..

[chiraggoel]

Watching ur first video and u just nailed it...way u return string is 👌

[shwetanksingh]

This is more intuitive than using a map.

[virusnetic]

Great Explanation, Keep up the good work and contribution to this community.

[Scovers]

Why the same code is not executing in Java? And serious issues?

[gautamjangir]

Explanation is Awesome but please do discuss about the complexity( Space and Time )....Thanks.

[dhananjoydey]

can you upload solution of the leetcode problem "1675. Minimize Deviation in Array"?

[greatred]

Hey, please make a video on Maximum Width of Binary Tree, lc662