#include<map>
#include<queue>
BinaryTreeNode<int>* getparent(BinaryTreeNode<int>* root,int start, map<BinaryTreeNode<int>*,BinaryTreeNode<int>*>&parent){
queue<BinaryTreeNode<int>*> q;
parent[root]=NULL;
q.push(root);
BinaryTreeNode<int>* res=NULL;
while(!q.empty()){
BinaryTreeNode<int>* front=q.front();
q.pop();
if(front->data==start) res=front;
if(front->left){
parent[front->left]=front;
q.push(front->left);
}
if(front->right){
parent[front->right]=front;
q.push(front->right);
}
}
return res;
}
int timeToBurnTree(BinaryTreeNode<int>* root, int start)
{
//DS
if(root==NULL) return 0;
map<BinaryTreeNode<int>*,BinaryTreeNode<int>*> parent; //(node,parent) to store parent
map<BinaryTreeNode<int>*,bool> vis; //to store if visited or not
queue<BinaryTreeNode<int>*> q;
//get parent array
//find start node both done by getparent()
BinaryTreeNode<int>* target = getparent(root,start,parent); //target node acquired
//burning starts here !!!
q.push(target);
vis[target]=true;
int ans=0;
while(!q.empty()){
//int ans=0;
bool flag=0;
for(int i=0;i<q.size();i++){
BinaryTreeNode<int>* front=q.front();
q.pop();
if(front->left && !vis[front->left]) {
q.push(front->left);
vis[front->left]=true;
flag=true;
}
if(front->right && !vis[front->right]) {
q.push(front->right);
vis[front->right]=true;
flag=true;
}
if(parent[front]!=NULL && !vis[parent[front]]) {
q.push(parent[front]);
vis[parent[front]]=true;
flag=true;
}
}
if(flag==true) ans++;
}
return ans;
}