- 0of 0 votes
You are given a tree and any of the leaf node which is given as input is set to fire. And in each unit time all the neighbouring nodes of the nodes which are already in fire also catch fire. Given a tree find the time taken for the whole tree to catch fire.
The whole catches fire meaning all nodes catches fire.
/ \ / \
7 8 9 10
Assume the source leaf node : 9
At 1 sec : 6 catches fire
At 2 sec : 10 and 4 catches fire
At 3 sec : 5 catches fire
At 4 sec : 7 and 8 catches fire
At 5 sec : 13 and 11 catches fire
At 6 sec : 12 catches fire
If we have access to parent pointers its easy just BFS and keeping track of visited we get the answer.
How to go about the problem if we do not have access to parent pointers ??