Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
@soumyohalder9636 Жыл бұрын
It can be done by DFS very easily, just need to find the max distance of a leaf from the target. convert into an undirected-graph and proceed, class Solution { public: int ans=0; void dfs(Node* root,vector& g) { if(root==NULL) return; if(root->left) { g[root->data].push_back(root->left->data); g[root->left->data].push_back(root->data); } if(root->right) { g[root->data].push_back(root->right->data); g[root->right->data].push_back(root->data); } dfs(root->left,g); dfs(root->right,g); } void dfs2(int node,vector& g,vector& vis,int t) { vis[node]=1; t+=1; ans=max(ans,t); for(int it:g[node]) { if(!vis[it]) { dfs2(it,g,vis,t); } } } int minTime(Node* root, int target) { int N=1e4; vector g(N+1); dfs(root,g); vector vis(N+1,0); vector iT(N+1,0); dfs2(target,g,vis,0); return ans-1; } };
@acandfungroup40394 ай бұрын
@@soumyohalder9636pair dfs(BinaryTreeNode* Node, int &ans , int &target){ if(Node == NULL) return{0,0} ; pair left = dfs(Node->left,ans,target) ; pair right = dfs(Node->right,ans,target) ; if(left.second | right.second){ ans = max(ans , left.first + right.first + 1); return {(left.second ? left.first : right.first) + 1,1 }; } else { if(Node->data == target){ ans = max(left.first , right.first) + 1 ; return {1,1} ; } else return {max(left.first,right.first) + 1 , 0} ; } } int timeToBurnTree(BinaryTreeNode* root, int start) { // Write your code here int ans = 0 ; dfs(root,ans,start) ; return ans -1; } a better one
@sparshsharma60682 жыл бұрын
This problem was exactly similar to that of the previous one, yet there was no difference in your enthusiasm or efforts in explaining the solution. Hats off bhaiya!! And yes, likeeeed, shareeeed, subscribeeeeeeeed and understood🔥🔥
@VrickzGamer2 жыл бұрын
I had to face rejection due to this question on Amazon
@omsalpekar88762 жыл бұрын
@@VrickzGamer they asked the same exact qn?
@mananpurohit92992 жыл бұрын
@@VrickzGamer Kill it next time , good luck buddy
@Rajesh-op8zx Жыл бұрын
@@VrickzGamer Which college ?
@Rajesh-op8zx Жыл бұрын
@@omsalpekar8876 Which college?
@nitinkumarsingh79592 жыл бұрын
you can also try it by slighly different approach. After making parent map, instead of taking another bfs to find the time, You can find the height of tree using dfs cosidering target node as root node and also taking the help of visited map. The code of this part is similar to find the height or bt with slight modification. Code: int height(Node* root , unordered_map&par , unordered_map&vis) { if(!root) return 0; vis[root]=1; int lh= INT_MIN; int rh= INT_MIN; int ph= INT_MIN; if(!vis[root->left]) lh= height(root->left, par, vis); if(!vis[root->right]) rh= height(root->right, par, vis); if(!vis[par[root]]) ph= height(par[root] , par, vis); return max(ph, max(lh,rh)) +1; } The final ans will be height-1;
@rhythmbhatia89062 жыл бұрын
I used the same approach! Good to see someone with similar approach.
@amanbhadani88402 жыл бұрын
Can You tell me why did u assigned lh,rh,ph with INT_MIN??
@krishnavamsichinnapareddy2 жыл бұрын
Cool
@hoola_amigos Жыл бұрын
@@amanbhadani8840 for this logic it doesn't matter what you assign to these variables as you are setting them to 0 in the base case. But in general it's a good practice to set such values to minimum possible so that in case base condition is missed it doesn't cause issues.
@ganavin3423 Жыл бұрын
Time limit Exceeded in gfg
@arvindersingh95882 жыл бұрын
I think we can use dfs, since it is a tree not graph (ie acyclic), here ans would be max of all depths from start node, simply max of distance you can go from start, while maintaining visited. For parent mapping, obviously bfs is only option. However, bfs is more natural as intuitive to come up with, but dfs is also possible approach to follow after parent mapping.
@takeUforward2 жыл бұрын
Yeah, my bad. We will consider the node as the parent and then it becomes basically find the height of the tree!
@deepaksarvepalli23442 жыл бұрын
I am not getting this, could you please explain
@deepaksarvepalli23442 жыл бұрын
@@takeUforward I am not getting this, could you please explain this .
@vipuljain36432 жыл бұрын
Why we can't use dfs for parent mapping?
@sriramkrishnamurthy44732 жыл бұрын
@@vipuljain3643 ofc we can , we'll just have to use a prev pointer that's all in preorder traversal
@ahmedadebisi8812 жыл бұрын
It makes me sooo happy that I could apply the technique in the previous video to solve this problem. Kudos striver!! ❤️
@sarangtamrakar87232 жыл бұрын
Just based on Print all the node from given node understanding I am able to write same exact code logic... Thnaks for making learning very smooth..
@eklavyaprasad50092 жыл бұрын
Thank You Bhaiya for the amazing explanation. I watched the prev. video of allNodesAtKthDistance form a node and paused this video and applied your logic and got it right.
@rudranshsrivastava41673 ай бұрын
Thanks, understood your explanation and was able to implement on my own. Great work.🎉
@DivineVision201 Жыл бұрын
bhaiya i have done this question by myself at first. really happy that i am able to understand approach of question and its all because of you. At first i felt the previous question a bit tough then i practiced it and because of that only i am able to solve it. Thanks and lots of love. Your way of solving and explaining approach towards any problem is just awesome. Loved it
@cinime Жыл бұрын
Understood! So wonderful explanation as always, thank you very much!!
@vadirajjahagirdar93422 жыл бұрын
Very clear explanation. That is why we love your channel. Thanks :) :)
@manusisodia5814 Жыл бұрын
Great... struggling with this problem And concluded now that this is a simple hashing and level order line by line problem 🙂
@sanginigupta13122 жыл бұрын
solved this on my own! recursion playlist is helping me a lot in writing code effectively for hard tree problems!
@priyansh85322 жыл бұрын
same
@stith_pragya8 ай бұрын
Thank You So Much for this wonderful video.....🙏🙏🙏
@stith_pragya8 ай бұрын
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@ishangujarathi108 ай бұрын
lovedd the intuition explanations and appraoch, you make problme solving so muchhh fun and easier :)!!
@shaddyrogue9430 Жыл бұрын
Solved the question on my own after Understanding prev Question. Thanks for Great Explanation.
@VineetKumar-fk2rl4 ай бұрын
Solved this question by own bcz of previous question, very happy 😊. Thanks striver for your invaluable content!!!
@YVGamers Жыл бұрын
Leetcode problem link:- leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/
@parthsalat Жыл бұрын
Dev Manus
@harshexploring4922 Жыл бұрын
I am in love with the way of your explanation.
@ketonesgaming11212 ай бұрын
Hey thanks striver ! I did this problem myself just applied the logic of your previous video 💌
@Weirdvloggertrue2 жыл бұрын
Woah!! 🔥❤️ This type of variations in questions requires a lot of research and hard work. Hats off to you. Great work👏 I'll be watching the entire series and will make sure that I solve any question of trees topic. Thanks for everything 🙂❤️
@VrickzGamer2 жыл бұрын
This question was asked in my Amazon Round-2 and I messed it , never saw such a question before
@Weirdvloggertrue2 жыл бұрын
Bhai thanks, linkedin pe bhej jaldi
@prachigupta2430 Жыл бұрын
I am preparing for product based organization. learning concepts :) i m very grateful for such amazing content on utube.
@rishabhgupta1222Ай бұрын
is that u in ur pfp ???
@sujoyseal1952 жыл бұрын
Which ever node in the tree burns first, we can imagine that node to be the root . We can do a level order traversal from this node . The number of levels is the required answer since all nodes in the same level burns at the same time.
@adolft_official Жыл бұрын
by converting tree to a graph
@yeswanthh50688 ай бұрын
Nice approach ❤
@CodeSuccessChronicle2 жыл бұрын
On point and very clear, Thank you Bhaiyya. Please make more videos like this.
@MandeepKumar-ue3zy2 жыл бұрын
Awesome explanation . Thanks man 💓
@mritunjay70652 жыл бұрын
Awesome Explanation !👌👌👌👌
@TarunKumar-cn6in Жыл бұрын
Excellent explanation ever thanks
@lilupardhan69 Жыл бұрын
Thank you so much sir, you are great!
@user-tk2vg5jt3l3 ай бұрын
Thank you Bhaiya
@Kpriyasing2 жыл бұрын
Very helpful ❤️
@navinagarwal89062 жыл бұрын
Thank you so much for your efforts
@tapeshvashisth7726 Жыл бұрын
Great solution! This is my dfs solution for this question 😅 typedef BinaryTreeNode node; int ans = 0; int helper(node * root, int target) { if (root) { int left = helper(root->left, target); int right = helper(root->right, target); if (root->data == target) { ans = max(abs(left), max(abs(right), ans)); return 1; } if (left
@gandhijainamgunvantkumar67832 жыл бұрын
Understood :) and amazing explanation.
@clarencegomes60762 жыл бұрын
Gazab! Thanks Striver for your videos.
@ajayjangid11642 жыл бұрын
the main moto of the problem is to find the length of longest-path from the given node, and this we can do via dfs also.
@animeshsingh70602 жыл бұрын
bro can u send code for that, i also thought the same but couldn't implement it
@mansisethi8127Ай бұрын
interesting questions
@sejalrai302 жыл бұрын
you are awesome thank you so much
@Dontpushyour_luck8 ай бұрын
making hard problems look so easy. only striver can do that!
@satyamsrivastava90342 жыл бұрын
I just saw the half video and written the whole code for this problem and that was accepted.. Your videos are damm good
@taukirkhatri33682 жыл бұрын
@@madhabkafle8898 You do not have to feel bad! May be you were not focused at the time of solving or you have seen the code too early or there can be multiple reasons. The key idea here was the part in the BFS algorithm while finding the minimum time or when to increment the answer. Just keep this in mind next time and you will be able to solve the problems with similar concept : )
@srijanprasad8319 Жыл бұрын
god level explanation. loved it
@uRamPlus2 жыл бұрын
Self Notes: 🍊 Mark each node to its parent to traverse upwards in a binary tree 🍊 We will do a BFS traversal from our starting node. 🍊 Traverse up, left, right until 1 radial level (adjacent nodes) are burned and increment our timer. this problem uses same pattern and techniques as nodes at Kth distance problem: kzbin.info/www/bejne/n2qyg597rpt4qas&ab_channel=takeUforward
@ajitheshgupta30172 жыл бұрын
What changes has to be made if the question is from leaf node?
@gandhijainamgunvantkumar67832 жыл бұрын
@@ajitheshgupta3017 nothing, because you will be given the value of the node. Now, as we are finding the address of the node, it doesn't matter whether it is leaf node or any other node.
@tankuharshida28552 жыл бұрын
I am enjoying coding cause of you
@154poojadas72 жыл бұрын
Thanks you so much 💗
@mohitejaikumar23 күн бұрын
great
@rahularity21 Жыл бұрын
This solution is not accepted in Interviews, It is simply make the graph out of the given tree and now the solution is easy. In interviews it will be required to solve it without making a graph. (i.e,. without extra space)
@rickk3300 Жыл бұрын
class Solution { int height(Node *root) { if(!root) return 0; return 1 + max(height(root->left), height(root->right)); } bool findPath(Node *root, vector& path, int target) { if(root) { path.push_back(root); if(root->data == target) return true; if(findPath(root->left, path, target) or findPath(root->right, path, target)) return true; path.pop_back(); } return false; } public: int minTime(Node* root, int target) { vector path; findPath(root, path, target); // "path" stores the path from the root node to the target node int ans = 0; int n = path.size(); for(int i = 0; i < n - 1; i++) { if(path[i]->left == path[i + 1]) { ans = max(ans, height(path[i]->right) + n - i - 1); } else { ans = max(ans, height(path[i]->left) + n - i - 1); } } ans = max(ans, height(path[n - 1]) - 1); return ans; } }; // What about my code? This is accepted on GFG. While traversing the path from the root node to the target node, I am basically calculating the length of the path from the target node through the current node all the way down to the deepest leaf node on the other side. All these lengths can be a probable answer and I am just returning the max. of all of them.
@pranayavnish802810 ай бұрын
exactly, I tried searching for the optimized approach in YT couldnt find it. there's a reason it's a medium. Half knowledge is definitely dangerous.
@pranayavnish802810 ай бұрын
@@rickk3300 u are still using a vector i.e. extra space
@acandfungroup40394 ай бұрын
pair dfs(BinaryTreeNode* Node, int &ans , int &target){ if(Node == NULL) return{0,0} ; pair left = dfs(Node->left,ans,target) ; pair right = dfs(Node->right,ans,target) ; if(left.second | right.second){ ans = max(ans , left.first + right.first + 1); return {(left.second ? left.first : right.first) + 1,1 }; } else { if(Node->data == target){ ans = max(left.first , right.first) + 1 ; return {1,1} ; } else return {max(left.first,right.first) + 1 , 0} ; } } int timeToBurnTree(BinaryTreeNode* root, int start) { // Write your code here int ans = 0 ; dfs(root,ans,start) ; return ans -1; }
@RituSingh-ne1mk6 ай бұрын
Understood!
@UECAshutoshKumar11 ай бұрын
Thank you sir
@harshitjaiswal94395 ай бұрын
understood.
@alesblaze47452 жыл бұрын
thanks mate!
@nagavedareddy58912 жыл бұрын
Huge respect...❤👏
@AmanKumar-qz4jz6 ай бұрын
understood
@deepakjain44818 ай бұрын
we are mapping parent for every node instead we make changes default like right left parent it will be like doubly linked lists and it takes up the same amount of space
@araragikoyomi71862 жыл бұрын
One correction, you said we can't do this problem using dfs but we can , we just need to find the maximum distance node from the start node so we can do tree dp like thing here every node will return a maximum depth from itself and when we visit the target node we will store its depth and when we are at some node and we found the start node on the left subtree then we can maximize the distance like maxi = max(maxi, startDepth - currDepth + rightMaxi +1) and similar if we found it on right subtree. Yeah but if we have been given multiple burning nodes then dfs fails there then multisource bfs will be the best solution there. my code for single source using dfs: class Solution { public: int rec(Node *root,int target,int &maxi,bool &found,int &tlevel,int level,int &mxt){ if(!root){ return -1; } if(root->data == target){ found = true; int leftMaxi = rec(root->left,target,maxi,found,tlevel,level+1,mxt); int rightMaxi = rec(root->right,target,maxi,found,tlevel,level+1,mxt); tlevel = level; maxi = max({maxi,leftMaxi,rightMaxi})+1; return mxt = max(leftMaxi,rightMaxi)+1; }else{ bool lef = false,rig =false; int leftMaxi = rec(root->left,target,maxi,found,tlevel,level+1,mxt); if(found) lef = true; int rightMaxi = rec(root->right,target,maxi,found,tlevel,level+1,mxt); // cout
@user-yy6gz2fl7v7 ай бұрын
Understood
@PrinceKumar-el7ob2 жыл бұрын
A quick observation here striver -> Instead of using if(f1) time++; we know that at last leaf node will not be able to burn anyone then why don't we just return time-1 . Instead of writing 5 lines of code returning time-1 is sufficient. It passed all test case on interview bit and seems logical to me .
@hd26882 жыл бұрын
Code ur words
@AnandKumar-oo2oy2 жыл бұрын
Bro what is the difference between BinaryTreeNode* Or BinaryTeeNode*
@sommayghosh46172 жыл бұрын
@@AnandKumar-oo2oy serves the same purpose the former one uses template so can also be any other data type within it making it generalised
@amalsuresh56602 жыл бұрын
yeah, I did the same
@paulbarsha1740 Жыл бұрын
Why the type of node is BinaryTree* rather than any simple Node* like BinaryTree* that we usually get....whats the difference
@KOUSTUBH_-ok6up Жыл бұрын
best explaination in comparison to love babbar and anuj bhaiya
@JohnWick-kh7ow2 жыл бұрын
For C++, unordered_map will be better because we don't need ordered sequence of keys.
@rhythmbhatia89062 жыл бұрын
Actually worst case complexity of an unordered map is O(n) for a search, whereas for an ordered_map, it is O(logn). Thus, there might be a case of TLE on using unordered_map.
@Dontpushyour_luck8 ай бұрын
@@rhythmbhatia8906 in most cases, unordered_map works in O(1) complexity. It uses very effective hashing in its implementation. Only one time till date I faced the issue of TLE on unordered map as compared to accepted when using map. In rest all of the cases, it is better than map
@Y0gi72 жыл бұрын
a dfs approach can be:- public static int minTime(Node root, int target) { Mapmap=new HashMap(); find(root,target,map); int time=0; time=dfs(root,map.get(root),map); return time; } private static int find(Node root, int target, Map map) { if(root==null){ return -1; } if(root.data==target){ map.put(root,0); return 0; } int left=find(root.left, target, map); if(left>=0){ map.put(root, left+1); return left+1; } int right=find(root.right,target,map); if(right>=0){ map.put(root,right+1); return right+1; } return -1; } private static int dfs(Node root, int time, Map map) { if(root==null) return time-1; if(map.containsKey(root))time=map.get(root); int left=dfs(root.left, time+1, map); int right=dfs(root.right, time+1, map); return Math.max(left, right); }
@bhushankorg5606 Жыл бұрын
Don't use this you wil get TLE
@parthsalat Жыл бұрын
Understood kaka
@vinaykumaryenni78789 ай бұрын
PYTHON GFG SOLUTION BASED ON STRIVER EXPLANATION class Solution: def find(self,root,proot,r,p): q=[root] while(q): for i in range(len(q)): node=q.pop(0) if(node.data==p): r.append(node) if(node.left!=None): proot[node.left]=node q.append(node.left) if(node.right!=None): proot[node.right]=node q.append(node.right) def minTime(self, root,target): # code here proot={} q=[] self.find(root,proot,q,target) visit={} c=0 # for i in proot: # print(i.data,proot[i].data) visit[q[0]]=1 while(q): f=0 for i in range(len(q)): node=q.pop(0) if(node.left!=None and node.left not in visit): visit[node.left]=1 q.append(node.left) f=1 if(node.right!=None and node.right not in visit): visit[node.right]=1 q.append(node.right) f=1 if(proot.get(node) is not None and proot[node] not in visit): visit[proot[node]]=1 q.append(proot[node]) f=1 if(f!=0): c=c+1 return c
@jasmeenkaur60012 жыл бұрын
thanks alottttt
@prasantkumar322 жыл бұрын
Nice video
@parthsalat Жыл бұрын
Here are my detailed notes on this question: garmadon.notion.site/Time-needed-to-burn-the-tree-ff17bc7379e241ff98298d9ff8e03f2d
@qabdurrazzaq2 жыл бұрын
Great Explanation Bro. Will a problem occur if the root is NULL or the tree has only one node?
@takeUforward2 жыл бұрын
Logically then time would be 0
@joichirogaming2 жыл бұрын
Should we use iterative solution using queue for most of the questions?? Recursive approach is little confusing sometimes.
@sommayghosh46172 жыл бұрын
jaha layers dikhe level wise kaam hum ko help krega go for queue(distance related stuff), and for traversals and othr problems that have been defined recursively approach them recursively! , you will observe the pattern while doing questions for sure!
@krishnavamsichinnapareddy2 жыл бұрын
Understood 👍
@sayakmondal4610 Жыл бұрын
In the C++ code, BinaryTreeNode* root; Can anyone explain what does this mean I am seeing this for the first time. I have just seen this BinaryTreeNode* root;
@harshlakhotia40372 жыл бұрын
Respected Sir , Your approach is clear and efficient but , Please tell that in c++ code , 1. Why have u used map and why have u not used unordered_map . 2. Insert , search , delete all 3 are of log(n) time complexity in map and O(1) in unordered_map . So we should prefer unordered_map if possible . If I use unordered_map everywhere in the c++ code ,where u have used map , will it be wrong . If it wont be wrong, then we must use unordered_map as this will help to reduce time complexity . 3. How have u assumed time complexity of ordered map to be O(1) . Thanking You
@takeUforward2 жыл бұрын
You can use anything, since unordered worst case is o(n) hence i use map. Again as long as you can convey what you said to the interviewer, its absolutely fine :)
@harshlakhotia40372 жыл бұрын
@@takeUforward Thank u very much .U r doing great job of helping out students
@gladyouseen81602 жыл бұрын
@@takeUforward cant we just say that convert this to regular graph and do regular bfs?.
@AKASHKUMAR-li7li20 күн бұрын
This problem can be easily solved using 1) Finding node to root path 2) Finding height
@rishabhgupta9846 Жыл бұрын
Solved it my own
@devanshmesson27772 жыл бұрын
Parent of a node can also be found out by a dfs.
@arnabpaul682311 ай бұрын
maza aygaya
@user-wu4ww8em5b10 ай бұрын
a very simmilar question of rotten oranges
@mriduljain1981 Жыл бұрын
completed 31 lecture of free ka tree series.
@chandrachurmukherjeejucse5816 Жыл бұрын
Hey Striver here is the leetcode problem: 2385. Amount of Time for Binary Tree to Be Infected
Similar Question on Leetcode - Amount of Time for Binary Tree to be Infected
@jas5997 Жыл бұрын
Why cant we use the same solution as of find nodes at distance k with code handling to return TreeNode of source if source int value is given in question while map construction and use the same NodeVsParent node map and BFS till queue is empty and return the level-1 as time taken to burn
@mandon2608 Жыл бұрын
you are god bro
@soumyohalder9636 Жыл бұрын
It can be done by DFS very easily, just need to find the max distance of a leaf from the target. convert into an undirected-graph and proceed, class Solution { public: int ans=0; void dfs(Node* root,vector& g) { if(root==NULL) return; if(root->left) { g[root->data].push_back(root->left->data); g[root->left->data].push_back(root->data); } if(root->right) { g[root->data].push_back(root->right->data); g[root->right->data].push_back(root->data); } dfs(root->left,g); dfs(root->right,g); } void dfs2(int node,vector& g,vector& vis,int t) { vis[node]=1; t+=1; ans=max(ans,t); for(int it:g[node]) { if(!vis[it]) { dfs2(it,g,vis,t); } } } int minTime(Node* root, int target) { int N=1e4; vector g(N+1); dfs(root,g); vector vis(N+1,0); vector iT(N+1,0); dfs2(target,g,vis,0); return ans-1; } };
@iamnottech89186 күн бұрын
In this q even if we donot maintain vis. answer will be correct but yes ethically it should not be burnt again , a burnt node should be respected R.I.P lol.. and dfs can be used I don't know why he said maybe he is occupied in some work .
@AbidAhsan-yp4dc2 жыл бұрын
explanation was very good , but why did you change the implementation so much from the previous question ..?
@momilijaz2712 жыл бұрын
done!
@assymptote67872 жыл бұрын
can you please elaborate more the case of leaf nodes??
@piyushacharya7696 Жыл бұрын
It will not have the left and right nodes, but it will have the parent pointer to the above node, so it will go up and then compute based on the upper nodes' left, right, and up nodes.
@iswhyte14 күн бұрын
can we find the min time using dfs?
@kaju_29 Жыл бұрын
Bhaiya relevel not sending otp when i trying for signup and i try with different phone number and on different system but it does not responding
@zacian49412 жыл бұрын
Hey striver, you told in one of your videos (about interview tips) on the other channel that you should not alter/change the data structure given in the interview. But you are creating parent pointers here. why? Also, if modification is allowed, can't we simply make the given target node as the root and then calculate the height (max depth) of the tree as the answer? Please reply because you don't...
@takeUforward2 жыл бұрын
Parenr pointers are kept in hashmap. No you cannot make them as root, think properly.
@zacian49412 жыл бұрын
@@takeUforward I get the hashmap part but what I mean is - suppose modification was allowed. Then can I consider the given node as parent and simply find the height of the tree using DFS?
@binitrajshah93542 жыл бұрын
@@zacian4941 you can't take the given target as root suppose if there is a node in the left subtree's leaf and right subtree is long enough then your possible answer is in right subtree as left subtree height will be less than that of right. Take this question simply as finding longest distance between given node and farthest leaf node.
@zacian49412 жыл бұрын
@@binitrajshah9354 "Take this question as simply finding longest distance between given node and farthest leaf node" I guess that indeed is height (max depth) of the tree if given node is root.
@priyankasetiya135815 күн бұрын
class Solution { private static int findMinimumTime(Node node,Map map){ Map visited=new HashMap(); Queue queue=new LinkedList(); int maxi=0; queue.offer(node); visited.put(node,1); while(!queue.isEmpty()){ int sz=queue.size(); boolean flag=false; for(int i=0;i
@pulkitjain5159 Жыл бұрын
pattern : convert BT to undirected graph and the question turns to simple dfs , bfs of undirected graph
@ankurmishra1833 Жыл бұрын
Bhaiya can be simplify it step 1 : find the diameter of tree lets call it diam; step 2: find the lower height of target node lets call it low_height final step : return max(low_height, diam-low_height ) complexity O(N) please reply if i'm correct
@preethimelody89294 ай бұрын
The question is similar to Rotten Oranges
@iamnottech89186 күн бұрын
I avoided flag by starting time from -1
@AdityaDey4242 жыл бұрын
How many videos will be in this tree playlist ??
@takeUforward2 жыл бұрын
50+
@vibhu6132 жыл бұрын
❤
@vikasrajpurohit87304 күн бұрын
Why do we need the flag variable? I haven't used flag variable and returned minTime-1 it works!!
@alesblaze47452 жыл бұрын
shouldn't Space Complexity be O(N^2) as we are using Queue and Map both?
@rajeshg8649 Жыл бұрын
No it's O(N+N) ~ O(N)
@piyushacharya7696 Жыл бұрын
we are not storing the map inside the queue. so it's O(n) + O(n)
@nimeshpareek953 Жыл бұрын
After doing the last question I was able to think the approach of this one but my code was giving error and when I saw striver code then I am more like ki ab map bhi nhi aata