Burning Tree

/*
Logic:We can do this while BFS traversal,so we can go down but we can't go up in tree so
we created a map in which we will store parent address and do bfs
similary created a visited map,which will take care of viisted nodes.

Method 2:we can do this in single travesal by levelordertraversal storing parents in map
and when we acheived target we will start bfs algorithm from there.because we won't need
the parent of lower level nodes than the target level node.
*/

void dfs(Node *root,unordered_map<Node*,Node*> &mp){
    if(!root) return;
    if(root->left){ mp[root->left]=root;dfs(root->left,mp);}
    if(root->right){ mp[root->right]=root;dfs(root->right,mp);}
}
Node* find_node(Node *root,int target){
    if(!root) return NULL;
    if(root->data==target) return root;
    Node *t1=find_node(root->left,target);
    Node *t2=find_node(root->right,target);
    if(t1) return t1;
    else return t2;
}
class Solution {
  public:
    int minTime(Node* root, int target) {
       unordered_map<Node*,Node*> mp;
       unordered_map<Node*,bool> visited;
      dfs(root,mp);
      Node* target_node=find_node(root,target);
      deque<Node*> q;
      q.push_back(target_node);
      int time=0;
      visited[target_node]=true;
      while(q.size()){
          int k=q.size();
          for(int i=0;i<k;i++){
              Node *temp=q.front();
              q.pop_front();
              if(temp->left && !visited[temp->left]){ q.push_back(temp->left);visited[temp->left]=true;}
              if(temp->right && !visited[temp->right]){q.push_back(temp->right);visited[temp->right]=true;}
              if(temp!=root && !visited[mp[temp]]){ q.push_back(mp[temp]);  visited[mp[temp]]=true;}
          }
          time++;
      }
      return time-1;
    }
};