Last Updated: 4 Aug, 2020

Time To Burn Tree

Hard

Asked in companies

Solve now

Problem statement

You have a binary tree of 'N' unique nodes and a Start node from where the tree will start to burn. Given that the Start node will always exist in the tree, your task is to print the time (in minutes) that it will take to burn the whole tree.

It is given that it takes 1 minute for the fire to travel from the burning node to its adjacent node and burn down the adjacent node.

For Example :

For the given binary tree: [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
Start Node: 3

    1
   / \
  2   3
     / \
    4   5

Output: 2

Explanation :
In the zeroth minute, Node 3 will start to burn.

After one minute, Nodes (1, 4, 5) that are adjacent to 3 will burn completely.

After two minutes, the only remaining Node 2 will be burnt and there will be no nodes remaining in the binary tree. 

So, the whole tree will burn in 2 minutes.

Input Format :

The first line contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

The second line of input contains the value of the start node.

tree

For example, the input for the tree depicted in the above image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format

Print a single integer denoting the time in minutes that will be taken to burn the whole tree.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea is to first create an undirected graph of the given binary tree and then doing a bfs traversal of the undirected graph starting from the start node. We will keep a variable ‘count’ that will be incremented at each level of bfs traversal. ‘count-1’ is the required time needed to burn the whole tree.

Algorithm

Initialize an unordered map ‘M’ that maps from integer to array of integers that store the edges and vertices of an undirected graph formed.
Store the edges and vertices in ‘M’ using inorder traversal of the tree.
Run BFS traversal from the ‘start’ node and increment the ‘count’ variable at each iteration.
Return count - 1.

Solve now

02 Approach

The total time taken by the tree to burn completely will be equal to the distance of the farthest node from the start node in the tree. So we will find three values for each node.

Algorithm

Above: If the current node is an ancestor of the start node or if it is the start node itself, then the value of “above” for that node will be the shortest distance between the current node and the start node, otherwise, it will be -1.

For the given binary tree and Start node 6

1 2

/ \ Value of Above for each Node: / \

2 3 -1 1

/ \ / \ / \ / \

4 5 6 7 -1 -1 0 -1

/ \ / \

8 9 -1 -1

Below: If the current node is an ancestor of the start node or if it is the start node itself, then “below” denotes the maximum number of edges from the Start node to a leaf node in the Start node's subtree. Otherwise, it denotes the number of edges in the longest path from the current node to the leaf node (in the left or right subtree).

For the given binary tree and Start Node 3,

1 2

/ \ Value of Below for each Node: / \

2 3 1 2

/ \ / \ / \ / \

4 5 6 7 0 0 1 1

/ \ / \

8 9 0 0

Max: This value denotes the length of the longest path that has been achieved so far if the Start node is found, otherwise -1. This can be calculated simply by finding the maximum of these three values:
- The longest path below the starting node from Start node to the leaf node (in the subtree of the Start node). This value will be equal to below if we have found the Start node in any of the subtrees.
- The longest path including the current node and Start node. This can be calculated as:
  - (the number of edges between the current node and Start node (if found) equals to Above) + (number of edges in the longest path in the subtree without Start node equals to Below) + 1 or (below + above + 1)
- The Max value of the subtree in which the Start node is present.
Finally, the Max of the root node will store the total time to burn the whole tree.

Solve now