Burning Tree | GfG Problem of the Day | Binary Tree | BFS

In this video I'll be discussing the solution of Burning Tree.

Timestamps :
0:00 - Problem Statement
0:47 - Explanation
11:40 - Code

#dsa #problemsolving #binarytree #datastructureandalgorithm #bfs

[codetips-byRochak]

class Solution {
public:
int t=0;
void gettime(map<Node*, Node*>&mp, Node* start){
queue<Node*>q;
q.push(start);
map<Node*, int>vis;
vis[start]=1;
while(!q.empty()){
int s=q.size();
int flag=0;
for(int i=0;i<s;i++){
Node* node=q.front();
q.pop();

flag=1;
vis[node->left]=1;
q.push(node->left);
}

flag=1;
vis[node->right]=1;
q.push(node->right);
}
if(mp[node]&&!vis[mp[node]]){
flag=1;
vis[mp[node]]=1;
q.push(mp[node]);
}
}
if(flag){
t++;
}
}

}
Node* bfs(Node* root, int target, map<Node*, Node*>&mp){
queue<Node*>q;
Node* start;
q.push(root);
while(!q.empty()){
Node* node=q.front();
q.pop();
if(node->data==target){
start=node;
}
if(node->left){
mp[node->left]=node;
q.push(node->left);
}
if(node->right){
mp[node->right]=node;
q.push(node->right);
}
}
return start;
}
int minTime(Node* root, int target)
{
map<Node*, Node*>mp;
Node* start=bfs(root, target, mp);
gettime(mp, start);
return t;
}
};