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:

• Merge Overlapping Intervals in C++
• Password Validation in C++