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.
Also read:
Can you analyze the Time complexity for this solution?