Burn A Tree

So the question is as follows:

Given a binary tree denoted by root node A and a leaf node B from this tree.

It is known that 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.

You need to find the minimum time required to burn the complete binary tree.

Problem Constraints

2 <= number of nodes <= 105

1 <= node value, B <= 105

node value will be distinct

Input Format

First argument is a root node of the binary tree, A.

Second argument is an integer B denoting the node value of leaf node.

Output Format

Return an integer denoting the minimum time required to burn the complete binary tree.

Example Input

Input 1:

Tree :       1 
            / \ 
           2   3 
          /   / \
         4   5   6
 B = 4

Input 2:

Tree :       1
            / \
           2   3
          /     \
         4       5 
 B = 5

Example Output

Output 1:

4

Output 2:

4

Example Explanation

Explanation 1:

After 1 sec: Node 4 and 2 will be burnt. 
 After 2 sec: Node 4, 2, 1 will be burnt.
 After 3 sec: Node 4, 2, 1, 3 will be burnt.
 After 4 sec: Node 4, 2, 1, 3, 5, 6(whole tree) will be burnt.

Explanation 2:

After 1 sec: Node 5 and 3 will be burnt. 
 After 2 sec: Node 5, 3, 1 will be burnt.
 After 3 sec: Node 5, 3, 1, 2 will be burnt.
 After 4 sec: Node 5, 3, 1, 2, 4(whole tree) will be burnt.

C++ Code:

#define t TreeNode*
int findDepth(t A,int B,int d)
{
    if(A==NULL) return 0;
    if(A->val==B) return d;
    return max(findDepth(A->left,B,d+1),findDepth(A->right,B,d+1));
}
int depth(t A)
{
    if(A==NULL) return 0;
    return 1+max(depth(A->right),depth(A->left));
}
int find(t A,int &mx,int B,int d)
{
    if(A==NULL) return 0;
    if(A->val==B) 
    {
         mx = max(mx,max(depth(A->right),depth(A->left)));
         return 1;
    }
    if(find(A->left,mx,B,d-1))
    {
        mx = max(mx,depth(A->right)+d);
        return 1;
    }
    if(find(A->right,mx,B,d-1))
    {
        mx = max(mx,depth(A->left)+d);
        return 1;
    }
    return 0;
}
int Solution::solve(TreeNode* A, int B) {
    int d = findDepth(A,B,0);
    int mx = 0;
    find(A,mx,B,d);
    return mx;
}

Explaination

First of all we need to find the depth of the first node of the tree that was set to fire from the root.

Tree :       1 
            / \ 
           2   3 
          /   / \
         4   5   6
 B = 4

In the above example the node will be B(i.e. 4) the height will be 2.

After that for each node(i.e. each subtree) we are calculating how much time will it take to burn that subtree:

• If it is NULL then zero
• If it is B(i.e. the first node that was set to fire) then the total time taken to burn this subtree(having B as root will be)

Height of Right SubTree + Height of Left SubTree

• Else if any other node then the total time taken to burn this subtree will be

If B(the first node to be burnt) is on left then

Height of Right Sub Tree + Number of levels between present node and B.

If B(the first node to be burnt) is on right then

Height of Left Sub Tree + Number of levels between present node and B.

Now we need to find the maximum time of all the times taken by each subtree to get burnt.