How Long Until Fire Reaches the Whole Tree
Solve this ProblemYou are given the root of a binary tree with distinct node values and a value start that exists in the tree. At minute 0 the node holding start catches fire. Every minute the fire spreads from each burning node to all of its neighbours: its left child, its right child and its parent. Return how many minutes it takes until every node in the tree is on fire.
You can convert the tree to a graph and run a breadth-first search, or compute the answer in a single recursive pass by combining subtree heights with the distance from each ancestor to the start node.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 1 ≤ node.val ≤ 1000 - ◆
start is a value that exists in the tree (if the tree is empty the answer is 0) - ◆
The tree is given as its root node; each node has a val, a left child and a right child - ◆
At minute 0 the node holding start catches fire. Every minute, fire spreads from each burning node to all of its neighbours — its parent and both its children. Return the number of minutes until every node is burning (0 if the tree has a single node)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Build a Graph, Breadth-First Search From the Start Node
GoodFire spreads exactly like a breadth-first search: everything one step away catches fire next minute, everything two steps away the minute after, and so on. Since the fire also moves UP to the parent, make the tree an undirected graph first (parent- child pairs recorded in both directions). Then run a BFS from the start node recording each node's distance; the largest distance found is the number of minutes until the last node ignites. O(n) time and O(n) space for the graph and the distance table.
O(n)O(n)1class Solution {
2 public int burnTime(TreeNode root, int start) {
3 if (root == null) return 0;
4 Map<Integer, List<Integer>> links = new HashMap<>();
5 connect(root, links);
6 Map<Integer, Integer> dist = new HashMap<>();
7 Queue<Integer> queue = new ArrayDeque<>();
8 dist.put(start, 0);
9 queue.add(start);
10 int minutes = 0;
11 while (!queue.isEmpty()) {
12 int cur = queue.poll();
13 minutes = Math.max(minutes, dist.get(cur));
14 for (int next : links.getOrDefault(cur, new ArrayList<>())) {
15 if (!dist.containsKey(next)) {
16 dist.put(next, dist.get(cur) + 1);
17 queue.add(next);
18 }
19 }
20 }
21 return minutes;
22 }
23
24 private void connect(TreeNode node, Map<Integer, List<Integer>> links) {
25 if (node == null) return;
26 for (TreeNode child : new TreeNode[]{node.left, node.right}) {
27 if (child == null) continue;
28 links.computeIfAbsent(node.val, x -> new ArrayList<>()).add(child.val);
29 links.computeIfAbsent(child.val, x -> new ArrayList<>()).add(node.val);
30 connect(child, links);
31 }
32 }
33}Optimal — One Recursive Pass That Tracks the Fire's Path and Subtree Heights
OptimalThe last node to burn is the farthest node from start. It is either BELOW start, or it is reached by climbing to some ancestor and then descending into that ancestor's OTHER subtree. Compute this in one bottom-up pass with a signed return value: a non-negative number means "this subtree has no start inside and its height is this value"; a negative number −(d + 1) means "start is inside, and this node is d steps from it". At the start node itself, the fire goes down: candidate = the taller of its two subtree heights. At each ancestor (one child returned a negative value), the candidate is d (steps up to reach this ancestor) plus the height of the other subtree. Keep the maximum candidate. No graph and no parent links are built: O(n) time, O(h) space.
O(n)O(h)1class Solution {
2 private int best;
3
4 public int burnTime(TreeNode root, int start) {
5 best = 0;
6 spread(root, start);
7 return best;
8 }
9
10 // >= 0: subtree height (start not inside); < 0: start is inside, -(distance from this node to start + 1)
11 private int spread(TreeNode node, int start) {
12 if (node == null) return 0;
13 int left = spread(node.left, start);
14 int right = spread(node.right, start);
15 if (node.val == start) {
16 best = Math.max(best, Math.max(left, right));
17 return -1;
18 }
19 if (left >= 0 && right >= 0) return 1 + Math.max(left, right);
20 int dist = left < 0 ? -left : -right;
21 int other = left < 0 ? right : left;
22 best = Math.max(best, dist + other);
23 return -(dist + 1);
24 }
25}