Not getting the logic present on geeksforgeeks

help
, ,
1

Minimum time to burn a Tree starting from a Leaf node
Given a binary tree and a leaf node from this tree. It is known that in 1s all nodes connected to a given node (left child, right child and parent) get burned in 1 second. Then all the nodes which are connected through one intermediate get burned in 2 seconds, and so on. The task is to find the minimum time required to burn the complete binary tree.

Examples:

Input :
1
/
2 3
/ \
4 5 6
/ \
7 8 9

10
Leaf = 8
Output : 7
Initially 8 is set to fire at 0th sec.
1
/
2 3
/ \
4 5 6
/ \
7 F 9

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

10
After 2s: 2, 7 are set to fire.
1
/
F 3
/ \
4 F 6
/ \
F F 9

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

10
After 4s: 3 is set to fire.
F
/
F F
/ \
F F 6
/ \
F F 9

10
After 5s: 6 is set to fire.
F
/
F F
/ \
F F F
/ \
F F 9

10
After 6s: 9 is set to fire.
F
/
F F
/ \
F F F
/ \
F F F

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

F
It takes 7s to burn the complete tree.

Please help me with some optimised and easy solution, please explain if possible.

2

Take a single second to look at how disgusting the diagrams you copy-pasted in turned out to be. You might as well have just told us to look at the link to understand the problem because yours are actually more confusing.

Anyway, this problem is practically the definition of BFS. The solution they give is definitely valid but seems overcomplicated.

1 Like
3 

class Solution {
  public:
     int mnTime =0;
     
    void kdown(Node* root, int k , Node* blockNode){
        if(!root)
            return;
        if(root==blockNode)
            return;
        
        mnTime = max(mnTime,k);
        kdown(root->left, k+1,blockNode);
        kdown(root->right,k+1,blockNode);
    }
      int rootToNodePath(Node* root, int target){
        if(!root)
            return -1;
        
        if(root->data==target){
            kdown(root,0,NULL);  /// target found,
            // from here distance is k and no block node is there
            return 1;
        }
        
        int lres = rootToNodePath(root->left,target);  
        if(lres != -1){  // if node is found on left
            kdown(root,lres,root->left);  // whatever is the value returned that signifies its distance from target node
            return lres+1; // add 1 and return
        }
        int rres = rootToNodePath(root->right,target);
        if(rres != -1){  // similarly for right node
            kdown(root,rres,root->right);
            return rres+1;
        }
        
        return -1;  // neither found on left nor on right
        
        
    }
    int minTime(Node* root, int target) 
    {
        // Your code goes here
        mnTime=0;
        rootToNodePath(root,target);
        return mnTime;
    }
};