DSA Tracker

Visualize

Burning Tree

Multi-source BFS over the tree treated as an undirected graph

time O(n)space O(n)

Fire spreads to ALL adjacent nodes each minute, and adjacency here means left child, right child, AND parent — a plain top-down traversal only reaches descendants. So the tree is first converted into an undirected graph by recording each node's parent while locating the start. Then a round-based BFS radiates outward: every round, every currently-burning node checks its three neighbors, and any unburned one catches fire. The minute counter only advances on a round that actually ignites a new node — a round that finds nothing new means the whole tree is already burning, and the loop can stop without counting that round.

Details

Animated on: Tree [1, 2, 3, 4, 5, 6, 7], start = 3 — find the minimum time (minutes) for fire starting at node 3 to reach every node.

Problem:Burning TreeHard

Multi-source BFS over the tree treated as an undirected graph

step 1 / 11

4
2
5
1
6
3
0
7

Locate the start node 3 and record every node's parent while walking down (path from root: 1 -> 3). The tree is now an undirected graph — fire can spread through left, right, AND parent edges, not just downward.

Pseudocode
1FUNCTION minTimeToBurn(root, start):
2  parent <- MAP()
3  target <- LOCATE(root, start, parent)
4  visited <- SET(target)
5  frontier <- [target]
6  time <- 0
7  WHILE frontier NOT EMPTY:
8    next <- []
9    FOR EACH node IN frontier:
10      FOR EACH nb IN {node.left, node.right, parent[node]}:
11        IF nb != null AND nb NOT IN visited: ADD nb TO visited, APPEND nb TO next
12    IF LENGTH(next) > 0: time <- time + 1
13    frontier <- next
14  RETURN time

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Locate the start node 3 and record every node's parent while walking down (path from root: 1 -> 3). The tree is now an undirected graph — fire can spread through left, right, AND parent edges, not just downward.
  2. Minute 0: only 3 is on fire. visited = {3}, frontier = {3}, time = 0.
  3. Check every neighbor (left, right, parent) of each currently-burning node {3} to see which unburned nodes are adjacent.
  4. 6, 7, 1 catch fire this round, so time is incremented: time <- 1. burnTime now covers 4 of 7 nodes.
  5. Check every neighbor (left, right, parent) of each currently-burning node {6, 7, 1} to see which unburned nodes are adjacent.
  6. 2 catch fire this round, so time is incremented: time <- 2. burnTime now covers 5 of 7 nodes.
  7. Check every neighbor (left, right, parent) of each currently-burning node {2} to see which unburned nodes are adjacent.
  8. 4, 5 catch fire this round, so time is incremented: time <- 3. burnTime now covers 7 of 7 nodes.
  9. Check every neighbor (left, right, parent) of each currently-burning node {4, 5} to see which unburned nodes are adjacent.
  10. Neither of {4, 5} has an unburned neighbor. newlyBurned stays false, so time is NOT incremented — the whole tree is already on fire.
  11. frontier is empty, so the loop ends. minTimeToBurn(root, 3) = 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Burning Tree in the editorAll Binary Trees problemsBack to roadmap