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) {
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🔥🔥
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;
@@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.
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.
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.
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
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: th-cam.com/video/i9ORlEy6EsI/w-d-xo.html&ab_channel=takeUforward
@@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.
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.
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 .
yep, i did the same. and i think that their will never be the case when there is no change (in a single source bfs) if we are not putting visited nodes in the queue in first place. probably if their is singe node then no parent and no child, in that case t-1 suffices the need. also if we start at t = -1 which indicates that from t= -1 to t= 0 target node burns, it makes more sense as at t= 0 node is already burnt and hence at t = 1, 1 degree nodes get burnt. And then just return t; also another approach I figured out in comments can be finding max depth from that node using dfs.
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 🙂❤️
@@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 : )
The problem gets similar to finding depth. Here the variation would be that the root node will be the target node and for better understanding we can assume we are finding depth of tree with three children. Left,Right and Up and to avoid infinite loop we check if the node is already visited via visited data structure.
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
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)
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.
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
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
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
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 :)
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
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.
@@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
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; } };
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
question can be done without using internal for loop class Solution { // to find minimum time to infect the tree int findMin(unordered_map &m,TreeNode* target){ queueq; q.push({target,0}); unordered_map vis; vis[target]=1; int mini=0; while(!q.empty()){ bool flag=false; auto p=q.front(); auto node=p.first; int steps=p.second; coutleft if it exists and isn't visited if(node->left&&!vis[node->left]){ vis[node->left]=1; flag=true; q.push({node->left,steps+1}); } // visit node->left if it exists and isn't visited if(node->right&&!vis[node->right]){ vis[node->right]=1; flag=true; q.push({node->right,steps+1}); } // visit node->parent(using map) if it exists and isn't visited if(m[node]&&!vis[m[node]]){ vis[m[node]]=1; flag=true; q.push({m[node],steps+1}); } // if any of the node is infected in this visit update mini; if(flag) mini=max(mini,steps+1); } return mini; } // To Map Parent Elements of a node TreeNode* mapParents(TreeNode* root,unordered_map &m,int start){ queue q; q.push(root); TreeNode* res; while(!q.empty()){ TreeNode* node=q.front(); q.pop(); // store start value node in res if(node->val==start) res=node; if(node->left){ m[node->left]=node; q.push(node->left); } if(node->right){ m[node->right]=node; q.push(node->right); } } return res; } public: int amountOfTime(TreeNode* root, int start) { unordered_map m; TreeNode* target=mapParents(root,m,start); return findMin(m,target); } };
Here's my approach...Just came to see your approach and found similar.. Steps: 1)Build Parent Map (unordered_map , child->parent map) 2)Find the target Node using a tree traversal(Be sure to check NULL cases) 3)Initialize a burn timer, a queue, a visited set/array, map to store child,parent relation and a source node in which we will store the node which has the start data 4)Use level order BFS to find the burn time. 5)Return burn-1, since we know the burn time of starting tree is zero... _*CODE*_(SPOILERS AHEAD) *BUILD PARENT CHILD MAPPING* void buildMap(BinaryTreeNode* root, unordered_map &mpp){ if(root==NULL){ return; } if(root->left!=NULL){ mpp[root->left]=root; } if(root->right!=NULL){ mpp[root->right]=root; } buildMap(root->left,mpp); buildMap(root->right,mpp); return; } *FIND THE NODE HAVING DATA AS STARTING NODE* BinaryTreeNode* findNode(BinaryTreeNode* node, int key) { if(node != NULL){ if(node->data==key){ return node; } else { BinaryTreeNode* foundNode = findNode(node->left,key); if(foundNode == NULL) { foundNode = findNode(node->right,key); } return foundNode; } } else { return NULL; } } *LET'S GET BURNING (SORRY FOR DEFORESTATION)* int timeToBurnTree(BinaryTreeNode* root, int start) { int burn=0; queue q; //FOR LEVEL ORDER BFS unordered_set vis; //Use set if nodes may have same value or use vector unordered_map mpp; buildMap(root,mpp); //Built the child-->parent relation BinaryTreeNode* source=findNode(root,start); //Found the unlucky node to burn first q.push(source); //Start the AGNI🔥🔥🔥 while(!q.empty()){ int size=q.size(); while(size--){ auto curr=q.front(); q.pop(); vis.insert(curr); //Marking ,....Its dead😥😥 if(curr->left!=NULL && vis.find(curr->left)==vis.end()){ //if it exist and still alive q.push(curr->left); //Pushing it in queue for its turn to burn } if(curr->right!=NULL && vis.find(curr->right)==vis.end()){ q.push(curr->right); } if(mpp[curr]!=NULL && vis.find(mpp[curr])==vis.end()){ //Sorry dad😅 q.push(mpp[curr]); } } burn++; //ALL ADJACENTS ELIMINATED } return burn-1; //return the time } THANKS
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;
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 .
Observation- 1. all the nodes in a particular level burns simultaneously i.e in constant time 2. The target node will be at some level 3. So wouldnt the answer always be the (height of the tree-1)?
@HD correct... i was a bit wrong the approach should be considering the tree rooted at target and the respective directions will be left right and parent, then the ans becomes height -1.
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!
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
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;
}
};
@@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
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🔥🔥
I had to face rejection due to this question on Amazon
@@VrickzGamer they asked the same exact qn?
@@VrickzGamer Kill it next time , good luck buddy
@@VrickzGamer Which college ?
@@omsalpekar8876 Which college?
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;
I used the same approach! Good to see someone with similar approach.
Can You tell me why did u assigned lh,rh,ph with INT_MIN??
Cool
@@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.
Time limit Exceeded in gfg
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.
Yeah, my bad. We will consider the node as the parent and then it becomes basically find the height of the tree!
I am not getting this, could you please explain
@@takeUforward I am not getting this, could you please explain this .
Why we can't use dfs for parent mapping?
@@vipuljain3643 ofc we can , we'll just have to use a prev pointer that's all in preorder traversal
It makes me sooo happy that I could apply the technique in the previous video to solve this problem. Kudos striver!! ❤️
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..
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.
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
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: th-cam.com/video/i9ORlEy6EsI/w-d-xo.html&ab_channel=takeUforward
What changes has to be made if the question is from leaf node?
@@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.
Awesome Explanation ❤
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.
Great...
struggling with this problem
And concluded now that this is a simple hashing and level order line by line problem 🙂
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 .
Code ur words
Bro what is the difference between
BinaryTreeNode* Or BinaryTeeNode*
@@AnandKumar-oo2oy serves the same purpose the former one uses template so can also be any other data type within it making it generalised
yeah, I did the same
yep, i did the same. and i think that their will never be the case when there is no change (in a single source bfs) if we are not putting visited nodes in the queue in first place. probably if their is singe node then no parent and no child, in that case t-1 suffices the need. also if we start at t = -1 which indicates that from t= -1 to t= 0 target node burns, it makes more sense as at t= 0 node is already burnt and hence at t = 1, 1 degree nodes get burnt. And then just return t;
also another approach I figured out in comments can be finding max depth from that node using dfs.
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 🙂❤️
This question was asked in my Amazon Round-2 and I messed it , never saw such a question before
Bhai thanks, linkedin pe bhej jaldi
crisp and concise, so well explained!👏
solved this on my own! recursion playlist is helping me a lot in writing code effectively for hard tree problems!
same
Solved this question by own bcz of previous question, very happy 😊.
Thanks striver for your invaluable content!!!
I just saw the half video and written the whole code for this problem and that was accepted.. Your videos are damm good
@@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 : )
The problem gets similar to finding depth. Here the variation would be that the root node will be the target node and for better understanding we can assume we are finding depth of tree with three children. Left,Right and Up and to avoid infinite loop we check if the node is already visited via visited data structure.
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
Thanks, understood your explanation and was able to implement on my own. Great work.🎉
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thank You So Much for this wonderful video.....🙏🙏🙏
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.
bro can u send code for that, i also thought the same but couldn't implement it
I am in love with the way of your explanation.
class Solution {
public:
unordered_map parent; // Map child value -> parent node
Node* findtargetpointer(Node* root, int target) {
queue q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
if (temp->data == target) return temp;
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
}
return nullptr; // Handle case where target is not found
}
void buildParentMap(Node* root) {
if (root == NULL) return;
queue q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
if (temp->left) {
parent[temp->left->data] = temp; // Map left child to parent
q.push(temp->left);
}
if (temp->right) {
parent[temp->right->data] = temp; // Map right child to parent
q.push(temp->right);
}
}
}
void cal_dist(Node* target, int& maxDist) {
unordered_set visited; // Keep track of visited nodes
queue q;
q.push(target);
visited.insert(target->data);
while (!q.empty()) {
int size = q.size();
bool expanded = false; // Track if any new nodes are added at this level
while (size--) {
Node* temp = q.front();
q.pop();
// Add left child if not visited
if (temp->left && visited.find(temp->left->data) == visited.end()) {
q.push(temp->left);
visited.insert(temp->left->data);
expanded = true;
}
// Add right child if not visited
if (temp->right && visited.find(temp->right->data) == visited.end()) {
q.push(temp->right);
visited.insert(temp->right->data);
expanded = true;
}
// Add parent if not visited
if (parent.find(temp->data) != parent.end() && visited.find(parent[temp->data]->data) == visited.end()) {
q.push(parent[temp->data]);
visited.insert(parent[temp->data]->data);
expanded = true;
}
}
if (expanded) maxDist++;
}
}
int minTime(Node* root, int targetValue) {
Node* target = findtargetpointer(root, targetValue);
if (!target) return 0; // If target node is not found, return 0
buildParentMap(root); // Build parent-child relationships
int maxDist = 0;
cal_dist(target, maxDist); // Calculate maximum distance
return maxDist;
}
};
Hey thanks striver ! I did this problem myself just applied the logic of your previous video 💌
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)
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.
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.
@@rickk3300 u are still using a vector i.e. extra space
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;
}
Solved the question on my own after Understanding prev Question. Thanks for Great Explanation.
Understood! So wonderful explanation as always, thank you very much!!
lovedd the intuition explanations and appraoch, you make problme solving so muchhh fun and easier :)!!
Very clear explanation. That is why we love your channel.
Thanks :) :)
Python Easy DFS Solution:
def time_dfs(root, time):
if not root or root in self.vis: return None
self.vis.add(root)
self.ans = max(self.ans, time)
if root.left: time_dfs(root.left, time+1)
if root.right: time_dfs(root.right, time+1)
if self.parents[root]: time_dfs(self.parents[root], time+1)
time_dfs(self.target, 0)
return self.ans
I am preparing for product based organization. learning concepts :) i m very grateful for such amazing content on utube.
is that u in ur pfp ???
making hard problems look so easy. only striver can do that!
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
Why the type of node is BinaryTree* rather than any simple Node* like BinaryTree* that we usually get....whats the difference
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);
}
Don't use this you wil get TLE
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
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
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 :)
@@takeUforward Thank u very much .U r doing great job of helping out students
@@takeUforward cant we just say that convert this to regular graph and do regular bfs?.
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
I am enjoying coding cause of you
We don't require to maintain fl flag here as we are only pushing into queue the not burned nodes and running while loop till queue isn't empty.
Nice approach ❤
Hey Striver here is the leetcode problem: 2385. Amount of Time for Binary Tree to Be Infected
Here are my detailed notes on this question:
garmadon.notion.site/Time-needed-to-burn-the-tree-ff17bc7379e241ff98298d9ff8e03f2d
Similar Question on Leetcode - Amount of Time for Binary Tree to be Infected
For C++, unordered_map will be better because we don't need ordered sequence of keys.
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.
@@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
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;
}
};
pattern : convert BT to undirected graph and the question turns to simple dfs , bfs of undirected graph
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
This problem can be easily solved using
1) Finding node to root path
2) Finding height
best explaination in comparison to love babbar and anuj bhaiya
Thank you sir
completed 31 lecture of free ka tree series.
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
On point and very clear, Thank you Bhaiyya. Please make more videos like this.
question can be done without using internal for loop
class Solution {
// to find minimum time to infect the tree
int findMin(unordered_map &m,TreeNode* target){
queueq;
q.push({target,0});
unordered_map vis;
vis[target]=1;
int mini=0;
while(!q.empty()){
bool flag=false;
auto p=q.front();
auto node=p.first;
int steps=p.second;
coutleft if it exists and isn't visited
if(node->left&&!vis[node->left]){
vis[node->left]=1;
flag=true;
q.push({node->left,steps+1});
}
// visit node->left if it exists and isn't visited
if(node->right&&!vis[node->right]){
vis[node->right]=1;
flag=true;
q.push({node->right,steps+1});
}
// visit node->parent(using map) if it exists and isn't visited
if(m[node]&&!vis[m[node]]){
vis[m[node]]=1;
flag=true;
q.push({m[node],steps+1});
}
// if any of the node is infected in this visit update mini;
if(flag)
mini=max(mini,steps+1);
}
return mini;
}
// To Map Parent Elements of a node
TreeNode* mapParents(TreeNode* root,unordered_map &m,int start){
queue q;
q.push(root);
TreeNode* res;
while(!q.empty()){
TreeNode* node=q.front();
q.pop();
// store start value node in res
if(node->val==start) res=node;
if(node->left){
m[node->left]=node;
q.push(node->left);
}
if(node->right){
m[node->right]=node;
q.push(node->right);
}
}
return res;
}
public:
int amountOfTime(TreeNode* root, int start) {
unordered_map m;
TreeNode* target=mapParents(root,m,start);
return findMin(m,target);
}
};
interesting questions
Here's my approach...Just came to see your approach and found similar..
Steps:
1)Build Parent Map (unordered_map , child->parent map)
2)Find the target Node using a tree traversal(Be sure to check NULL cases)
3)Initialize a burn timer, a queue, a visited set/array, map to store child,parent relation and a source node in which we will store the node which has the start data
4)Use level order BFS to find the burn time.
5)Return burn-1, since we know the burn time of starting tree is zero...
_*CODE*_(SPOILERS AHEAD)
*BUILD PARENT CHILD MAPPING*
void buildMap(BinaryTreeNode* root, unordered_map &mpp){
if(root==NULL){
return;
}
if(root->left!=NULL){
mpp[root->left]=root;
}
if(root->right!=NULL){
mpp[root->right]=root;
}
buildMap(root->left,mpp);
buildMap(root->right,mpp);
return;
}
*FIND THE NODE HAVING DATA AS STARTING NODE*
BinaryTreeNode* findNode(BinaryTreeNode* node, int key) {
if(node != NULL){
if(node->data==key){
return node;
}
else {
BinaryTreeNode* foundNode = findNode(node->left,key);
if(foundNode == NULL) {
foundNode = findNode(node->right,key);
}
return foundNode;
}
} else {
return NULL;
}
}
*LET'S GET BURNING (SORRY FOR DEFORESTATION)*
int timeToBurnTree(BinaryTreeNode* root, int start) {
int burn=0;
queue q; //FOR LEVEL ORDER BFS
unordered_set vis; //Use set if nodes may have same value or use vector
unordered_map mpp;
buildMap(root,mpp); //Built the child-->parent relation
BinaryTreeNode* source=findNode(root,start); //Found the unlucky node to burn first
q.push(source); //Start the AGNI🔥🔥🔥
while(!q.empty()){
int size=q.size();
while(size--){
auto curr=q.front();
q.pop();
vis.insert(curr); //Marking ,....Its dead😥😥
if(curr->left!=NULL && vis.find(curr->left)==vis.end()){ //if it exist and still alive
q.push(curr->left); //Pushing it in queue for its turn to burn
}
if(curr->right!=NULL && vis.find(curr->right)==vis.end()){
q.push(curr->right);
}
if(mpp[curr]!=NULL && vis.find(mpp[curr])==vis.end()){ //Sorry dad😅
q.push(mpp[curr]);
}
}
burn++; //ALL ADJACENTS ELIMINATED
}
return burn-1; //return the time
}
THANKS
where are you marking the nodes visited ???
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;
a very simmilar question of rotten oranges
Excellent explanation ever thanks
LeetCode problem->amount-of-time-for-binary-tree-to-be-infected.
god level explanation. loved it
Thanks striver!
UNDERSTOOD;
class Solution {
private:
TreeNode*f(TreeNode* root, int start,map&mpp){
mpp[root]=NULL;
TreeNode*target=NULL;
queueq;
q.push(root);
while(!q.empty()){
TreeNode*front=q.front();
q.pop();
if(front->val==start){
target=front;
}
if(front->right){
mpp[front->right]=front;
q.push(front->right);
}
if(front->left){
mpp[front->left]=front;
q.push(front->left);
}
}
return target;
}
int g(TreeNode*target,map&mpp){
mapvis;
vis[target]=1;
queueq;
int ans=0;
q.push(target);
while(!q.empty()){
int size=q.size();
bool flag=0;
for(int i=0;iright && !vis[front->right]){
flag=1;
vis[front->right]=1;
q.push(front->right);
}
if(front->left && !vis[front->left]){
flag=1;
vis[front->left]=1;
q.push(front->left);
}
if(mpp[front] && !vis[mpp[front]]){
flag=1;
vis[mpp[front]]=1;
q.push(mpp[front]);
}
}
if(flag==1){
ans+=1;
}
}
return ans;
}
public:
int amountOfTime(TreeNode* root, int start) {
mapmpp;
TreeNode*target=f(root,start,mpp);
int ans=g(target,mpp);
return ans;
}
};
Gazab! Thanks Striver for your videos.
you are awesome thank you so much
Awesome Explanation !👌👌👌👌
Parent of a node can also be found out by a dfs.
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 .
TC Is 0(3N) and in the worst it would be 0(N²)
Understood kaka
Observation-
1. all the nodes in a particular level burns simultaneously i.e in constant time
2. The target node will be at some level
3. So wouldnt the answer always be the (height of the tree-1)?
@HD correct... i was a bit wrong the approach should be considering the tree rooted at target and the respective directions will be left right and parent, then the ans becomes height -1.
Thank you Bhaiya
Thank you So much !
Thank you so much for your efforts
Why do we need the flag variable? I haven't used flag variable and returned minTime-1 it works!!
Thank you so much sir, you are great!
Very helpful ❤️
Awesome explanation .
Thanks man 💓
Solved it my own
Here is my solution C++
class Solution {
public:
void markParent(Node* root, unordered_map &umap,Node* &tar, int target){
if(root==NULL) return;
if(root->data == target) tar = root;
if(root->left){
umap[root->left] = root;
}
if(root->right){
umap[root->right] = root;
}
markParent(root->left,umap,tar,target);
markParent(root->right,umap,tar,target);
}
int minTime(Node* root, int target)
{
unordered_map umap;
Node* tar;
markParent(root,umap,tar,target);
queue q;
unordered_map vis;
vis[tar] = true;
q.push(tar);
int time = 0;
while(!q.empty()){
int count = q.size();
time++;
for(int i=0;ileft && !vis[node->left]){
q.push({node->left});
vis[node->left] = true;
}
if(node->right && !vis[node->right]){
q.push({node->right});
vis[node->right] = true;
}
if(umap.find(node)!=umap.end() && !vis[umap[node]]){
q.push({umap[node]});
vis[umap[node]] = true;
}
}
}
return time-1;
}
};
2385. Amount of Time for Binary Tree to Be Infected
Should we use iterative solution using queue for most of the questions??
Recursive approach is little confusing sometimes.
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!
thanks mate!
explanation was very good , but why did you change the implementation so much from the previous question ..?
Thanks you so much 💗
understood
Great Explanation Bro.
Will a problem occur if the root is NULL or the tree has only one node?
Logically then time would be 0
understood
Not compulsory to use size loop just make pair
Node* parents(Node* root, int tar, unordered_map& mp) {
queue q;
q.push(root);
Node* target = nullptr;
while (!q.empty()) {
Node* current = q.front();
q.pop();
if (current->data == tar) {
target = current;
}
if (current->left) {
mp[current->left] = current;
q.push(current->left);
}
if (current->right) {
mp[current->right] = current;
q.push(current->right);
}
}
return target;
}
int minTime(Node* root, int tar) {
unordered_map mp;
Node* target = parents(root, tar, mp);
unordered_map visited;
queue qq;
qq.push({target,0});
visited[target] = true;
int ans = 0;
while (!qq.empty()) {
bool flag = false;
Node* node = qq.front().first;
int time = qq.front().second + 1;
qq.pop();
if (node->left && !visited[node->left]) {
qq.push({node->left,time});
visited[node->left] = true;
flag = true;
}
if (node->right && !visited[node->right]) {
qq.push({node->right,time});
visited[node->right] = true;
flag = true;
}
if (mp[node] && !visited[mp[node]]) {
qq.push({mp[node],time});
visited[mp[node]] = true;
flag = true;
}
if (flag) ans = max(ans, time);
}
return ans;
}
Understood
Huge respect...❤👏
Understood 👍
Understood!
great
I avoided flag by starting time from -1