Minimum time taken to burn the BT from a given Node
HardBFS from the target, counting levels
Problem
Fire starts at a target node and spreads to adjacent nodes each minute. Return minutes to burn the whole tree.
With parent links, BFS outward from the start; the number of waves is the minutes to burn everything.
The idea
Fire spreads to parents and children alike, so build parent pointers and BFS outward from the start node. The number of levels the BFS completes before the queue empties is the time to burn the whole tree.
The trick
- The answer is the eccentricity of the target — its distance to the furthest node.
- Count a minute only when the next level is non-empty.
- Same parent-pointer setup as nodes-at-distance-k.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — tree, start node Values: 0.
1build parent map2BFS from target (left,right,parent)3return number of levels - 1Input
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,3,4,5,null,6,null,null,7,8], start = 3
- Output:
- 4
- Explanation:
- Fire spreads to every node in 4 minutes.
Example 2
- Input:
- tree = [1,2,3], start = 1
- Output:
- 1
- Explanation:
- From the root, both children burn in 1.
Example 3
- Input:
- tree = [1], start = 1
- Output:
- 0
- Explanation:
- A single node is already burnt → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.