C++: Minimum time to burn a Tree starting from a Leaf node
By Himanshu BaranwalIn 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.
Also read:
Can you analyze the Time complexity for this solution?