# C++: Minimum time to burn a Tree starting from a Leaf node

In this tutorial we will learn about how to find minimum time to burn a tree from a given leaf node.
Consider the following binary tree as an input:

```  20
/
10
/    \
4      5
\
3
/  \
6   8
\
11

Leaf = 11
Output(Minimum time to burn the whole tree): 5(units)```
```Initially 11 is set to fire at 0th sec.

20
/
10
/    \
4      5
\
3
/  \
6   8
\
F
After 1s: 8 is set to fire.

20
/
10
/    \
4      5
\
3
/  \
6   F
\
F
After 2s: 3 is set to fire.

20
/
10
/    \
4      5
\
F
/  \
6   F
\
F
After 3s: 5, 6 are set to fire.

20
/
10
/    \
4      F
\
F
/  \
F   F
\
F
After 4s: 10 is set to fire.

20
/
F
/    \
4      F
\
F
/  \
F   F
\
F
After 5s: 4, 20 are set to fire.

F
/
F
/    \
F     F
\
F
/  \
F   F
\
F```

It takes 5s to burn the complete tree. Now from the above example we can closely see that burning a tree completely form a given leaf node is equal to the distance of the farthest node from the leaf node in the tree. Here in this case farthest node from 11 is 4 or 20 and distance between a leaf node and one of these nodes is 5.
So basically we have to calculate the farthest node distance from the leaf node which in a way corresponds to the minimum time required to burn the tree.

### Algorithm:

• Keep the track of ancestors of the leaf by assigning -1 to the nodes which are not ancestors.
• Now calculate the distance of the leaf node from its ancestor and add the distance of the other subtree from that ancestor to it.
• Calculate this distance from each ancestor and result in the distance which is the maximum of all.

This algorithm can be illustrated using the following code:

```#include<bits/stdc++.h>
using namespace std;
//creating structure of a node
struct Node{
int key;
Node *left;
Node*right;
Node()
{
left=NULL;
right=NULL;
}
};
//function to create a new node
Node *nNode(int data)
{
Node *temp=new Node;
temp->key=data;
return temp;
}
//function to calculate minimum time to burn the tree from a given leaf
int Min_time(Node *root, int leaf, int &dis,int &res)
{
if(root==NULL)
return 0;  //base case
if(root->key==leaf){dis=0;return 1;} //base case
int leftdis= -1; int rightdis=-1;//keep track of nodes which are not ancestor of the leaf node by assigning value -1
int lh=Min_time(root->left, leaf, leftdis, res);
int rh=Min_time(root->right, leaf, rightdis, res);
if(leftdis!=-1)
{
dis=leftdis+1;
res=max(res,dis+rh);//calculation of farthest distance from the leaf node in the tree
}
if(rightdis!=-1)
{
dis=rightdis+1;
res=max(res,dis+lh);//calculation of farthest distance from the leaf node in the tree
}
return max(lh,rh)+1; //function returns height
}
int main()
{
Node* root = nNode(20);
root->left = nNode(10);
root->left->left = nNode(4);
root->left->right = nNode(5);
root->left->right->right = nNode(3);
root->left->right->right->left=nNode(6);
root->left->right->right->right=nNode(8);
root->left->right->right->right->left=nNode(11);
// given leaf node is 11
int leaf = 11;
int result=0;
int distance=-1;
int h;
h=Min_time(root, leaf, distance, result);
//Since minimum time required to burn the tree is equal to the farthest distance from the leaf node in the tree
cout<<result;//result corresponds to minimum time

return 0;
}```
`The output of the following program is: 5`

That’s all for this tutorial.