InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Burn a Tree


Problem Description

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.
 



NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Burn a Tree on Interview Code Editor
Sign Up
to access hints and editorial solutions for Burn a Tree
Asked In:

Discussion


Loading...
Click here to start solving coding interview questions