Spread From the Spark
MediumTrees
Problem
A fire starts at the node whose value is start at minute 0. Every minute, the fire spreads from each burning node to every node directly connected to it: its parent and its children.
Given the root (all values are distinct) and start, return the number of minutes until the whole tree is burning.
Example 1
- Input:
- root = [1, 5, 3, null, 4, 10, 6, 9, 2], start = 3
- Output:
- 4
Minute 1: 1, 10, 6. Minute 2: 5. Minute 3: 4. Minute 4: 9 and 2.
Example 2
- Input:
- root = [1], start = 1
- Output:
- 0
Constraints
- 1 ≤ number of nodes ≤ 10^5
- Values are distinct, 1 ≤ node.val ≤ 10^5
- A node with value start exists.
Hint
Show the first hint
Fire can move upwards, but tree nodes only point down. What extra information do you need?
Walkthrough
How to approach it
01Clarify before coding
- Does fire spread to the parent too? Yes, along every edge in both directions.
- Are values unique? Yes, so start identifies one node.
- Single node? 0 minutes.
02Brute force
Simulate minute by minute, scanning the whole tree each minute to find nodes next to burning ones.
Cost: O(n · answer), up to O(n²) on a chain.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.