Amount of Time for Binary Tree to Be Infected | Using BFS | Leetcode 2385
Vložit
- čas přidán 7. 09. 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 34th Video on our playlist "Binary Tree : Popular Interview Problems".
In this video we will try to understand a very good Binary Tree Problem - "Amount of Time for Binary Tree to Be Infected" ( Leetcode 2385 )
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Amount of Time for Binary Tree to Be Infected
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach Summary : The provided video defines a Solution class that calculates the time for a signal to reach a given node in a binary tree. The convert function creates an adjacency list, and the amountOfTime function uses BFS to find the minimum time.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear
Done in just 7 min yes sir improvement ho raha hai kaafi medium me aaj kal sab hi kar letaaa hu 8 out of 10.Thank u sir bas asa hi vedio create karte raho sir i sure ki contest me bhi achi rating hone wali hai jaldi hi.
Initially, I was inclined to use BFS for this problem, based on my Intuition, but I was unsure about how to backtrack to the parent node. I had a vague idea but no concrete solution. However, after watching your explanation for just 7 minutes, it all made sense. I understood what I was missing and managed to write the code by myself. You are an exceptional storyteller. I admire your work immensely. It's evident that anyone who's been through your graph playlist could easily handle this question with just 4 to 7 minutes of your guidance.
Means a lot 🙏🙏❤️❤️
Maja aa Gaya bhai what a fabulous explanation ❤
For anyone like me jo sochra hai unordered_set ke jagah vector use karne ka, toh in that case you will get TLE. The reason is due to the difference in time complexities of search operation for the 2 data structures. For set it's O(1) on average because internally it uses a hash table for storage whereas, for vector it is O(n) as we need to traverse each element to find the searched element.
Now you can use searching techniques but that will make the code look more complex.
PS 1: I'm very very new to graphs and I did not want to make my code look complex :)
PS 2: Amazing explanation, coded entirely on my own (took a bit of reference for the queue thing as I was not using that inner while loop 🫠) after this explanation.
The way use teaches makes it so easy to learn and intuitive to think, thanks a lot
best explanation on entire youtube
aapki voice bahut pyari hai 🥰
My doubt cleared from this video. Thanks a lot mik
best explanation bhai ,, thanks a lot
Most welcome 🙏
Keep uploading Bhaiya, you make me learn a lot 😄
Thank you.
Also watch the One Pass solution 😇
czcams.com/video/Xm8jIjAK_Zs/video.htmlsi=JMM3MECQFApvF0vs
Well explained.
Superb.
Waiting for one pass solution eagerly 😊
Great explanation 🔥
Please update this solution failing the last two test cases , time limit exceeded, use dp to optimise it😅
You made it so easy!
😇❤️🙏
Thanks, bro i did it on my own Please make a video on the Biweekly contest Q4(2999 question)
Really underrerated 😁😁😁😁
🙏🙏🙏
can we also traverse it by dfs and create a parent for each element and store in array for each node and while doing bfs we can just move to left, right and parent of node if not visited.
Yes that should work 👌👌
class Solution {
private Mapadj=new HashMap();
public int amountOfTime(TreeNode root,int start){
convertToGraph(root);
Dequeq=new ArrayDeque();
Setvis=new HashSet();
q.offer(start);
int time=-1;
while(!q.isEmpty()){
time++;
for(int sz=q.size();sz>0;sz--){
int curNode =q.pollFirst();
vis.add(curNode);
if(adj.containsKey(curNode)){
for(int it:adj.get(curNode)){
if(!vis.contains(it))
q.offer(it);
}
}
}
}
return time;
}
private void convertToGraph(TreeNode root){
if(root==null) return;
if(root.left!=null){
adj.computeIfAbsent(root.val,k->new ArrayList()).add(root.left.val);
adj.computeIfAbsent(root.left.val,k->new ArrayList()).add(root.val);
}
if(root.right!=null){
adj.computeIfAbsent(root.val,k->new ArrayList().add(root.right.val);
adj.computeIfAbsent(root.right.val,k->new ArrayList()).add(root.val);
adj.computeIfAbsent( root.right.val,k->new ArrayList()).add(root.val);
}
convertToGraph(root.left);
convertToGraph(root.right);
}
}
dfs apporach.
class Solution {
private int maxDist=0;
public int amountOfTime(TreeNode root,int start){
dfs(root,start);
return maxDist;
}
public int dfs(TreeNode root,int start){
int depth=0;
if(root==null) return depth;
int leftDepth=dfs(root.left,start);
int rightDepth=dfs(root.right,start);
if(root.val==start){
maxDist =Math.max(leftDepth,rightDepth);
depth=-1;
}else if(leftDepth>=0&&rightDepth>=0){
depth=Math.max(leftDepth,rightDepth)+1:
}else{
int dist=Math.abs(leftDepth)+Math.abs(rightDepth);
maxDist=Math.max(maxDist,dist);
depth =Math.min(leftDepth,rightDepth)-1;
}
return depth;
}
}
🎉😂❤
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
I stored node in hashmap but storing the values is the key
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
hi, The time complexity for bfs is O(vertices + edges) can we apply the same here?
Thanks 👍
Guruji ❤❤❤
clean explanation 🔥
❤️🙏
I used stack, although recursion is stack
stack st;
st.push(root);
while(!st.empty()){
auto node = st.top();
st.pop();
if(node->right){
int parent = node->val;
int child = node->right->val;
adj[parent].push_back(child);
adj[child].push_back(parent);
st.push(node->right);
}
if(node->left){
int parent = node->val;
int child = node->left->val;
adj[parent].push_back(child);
adj[child].push_back(parent);
st.push(node->left);
}
}
THANKS!!
some space can be saved by making just the mapping for the parent, since we can already travel to the child
here is the code
class Solution {
public:
unordered_mapmp;
TreeNode* makeMapping(TreeNode*root,int start){
queueq;
q.push(root);
TreeNode* begin = NULL;
while(!q.empty()){
auto node = q.front();
q.pop();
if(node->val == start){
begin = node;
}
if(node->left){
mp[node->left] = node;
q.push(node->left);
}
if(node->right){
mp[node->right] = node;
q.push(node->right);
}
}
return begin;
}
int solve(TreeNode* root, TreeNode* start){
queueq;
q.push(start);
unordered_setvisited;
visited.insert(start);
int time = 0;
for(auto i:mp){
coutright) == 0){
visited.insert(node->right);
q.push(node->right);
}
if(mp.count(node) > 0 && visited.count(mp[node]) == 0){
visited.insert(mp[node]);
q.push(mp[node]);
}
}
if(q.size() > 0){
time++;
}
}
return time;
}
int amountOfTime(TreeNode* root, int start) {
TreeNode*begin = makeMapping(root,start);
return solve(root,begin);
}
};
Nice ❤️🙏
Thank you bhaiya waiting for single traversal approach :)
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
@@codestorywithMIK thank you bro🙏🙏. I am currently searching for internship but can't find anywhere 😔 feels depressing, meantime I am gonna skill up
please upload one pass solution
Yes it’s being uploaded now. Full intuitive explanation 😇❤️🙏
This approach is pretty staright forward , can you please explain the single pass dfs approach
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
it’s being uploaded now. Full intuitive explanation 😇❤️🙏
sir aap ek baar ye code explain kr skte h ???
class Solution {
public static TreeNode parent_link(TreeNode root,Mapmap,int start){
Queueq=new LinkedList();
TreeNode res=null;
q.add(root);
while(!q.isEmpty()){
TreeNode cur=q.poll();
if(cur.val==start) res=cur;
if(cur.left!=null){
map.put(cur.left,cur);
q.add(cur.left);
}
if(cur.right!=null){
map.put(cur.right,cur);
q.add(cur.right);
}
}
return res;
}
public int amountOfTime(TreeNode root, int start) {
Mapparent_map=new HashMap();
TreeNode target=parent_link(root,parent_map,start);
Mapvisit=new HashMap();
Queuequ=new LinkedList();
visit.put(target,true);
qu.add(target);
int minTime=0;
while(!qu.isEmpty()){
int size=qu.size();
int flag=0;
for(int i=0;i
Bhai nayi wali video jo iska 2nd part hai jaldi dalo bhai!!!!
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
please make video of one time traversal for this problem
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
Bro just to inform that this code is giving a tle now when I run the same on lc. Pls check if possible why is it so?
same bro, did you manage to get through the TLE?
when will approach 2 come for this problem ???????????????????????????????????????????????????????
Definitely.
Just getting free from office. Will then upload. Thank you 😇🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
i used for(int i=0;i
Can you please share full code.
Java plz bhaiya ❤
Hi there, JAVA code is available in the GitHub link in the description. Will that help ? ❤️
bhaiya can we do one thing , first we will find on which side their would be the infected node, after that we would calculate nodes from root to that infected node, now we would find height of visited node, then we would find height of the node to the other side of the root , add path from root+ infected root height +height on the other side to get the ans
❤
bhaiya, i am solving the same question, getting "all testcases passed, but took too long" error. here's my code, instead of making it an undirected graph i just assigned parents to all nodes using unordered_map:
class Solution {
public:
Solution(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
unordered_map ump;
unordered_map vis;
TreeNode* target;
int amountOfTime(TreeNode* root, int start) {
if(root==NULL){
return 0;
}
gen(root,start);
vis[target]=1;
queue q;
q.push(target);
int countmin = -1;
while(!q.empty()){
countmin++;
int size = q.size();
while(size--){
TreeNode* node = q.front();
q.pop();
if(node->left!=nullptr && vis[node->left]==0){
q.push(node->left);
vis[node->left]=1;
}
if(node->right!=nullptr && vis[node->right]==0){
q.push(node->right);
vis[node->right]=1;
}
if(node!=root && vis[ump[node]]==0){
q.push(ump[node]);
vis[ump[node]]=1;
}
}
}
return countmin;
}
void gen(TreeNode* root, int start){
if(root == nullptr) return;
if(root->val==start) target=root;
vis[root]=0;
if(root->left!=nullptr){
ump[root->left]=root;
}
gen(root->left,start);
if(root->right!=nullptr){
ump[root->right]=root;
}
gen(root->right,start);
}
};
kya aap bata skte ho kyun ho raha hai aisa?
The way use teaches makes it so easy to learn and intuitive to think, thanks a lot
Means a lot ❤️🙏
One Pass solution being uploaded now. Full intuitive explanation 😇❤️🙏
❤