Practice Now
binary tree
algorithm
tree burning
computational problem
data structures

Given a node, how long will it take to burn the whole binary tree?

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms
AlgorithmsData Structures

Introduction

The "burning tree" problem asks: given a binary tree and a starting node (the fire source), how many seconds does it take for fire to spread to every node, if fire spreads to all adjacent nodes (parent, left child, right child) each second? This is equivalent to finding the farthest node from the source — the answer is the maximum distance from the source to any node in the tree.

Example

 
1        1
2       / \
3      2   3
4     / \
5    4   5

Starting fire at node 4:

  • Time 0: Node 4 is on fire
  • Time 1: Node 2 catches fire (parent of 4)
  • Time 2: Nodes 1 and 5 catch fire
  • Time 3: Node 3 catches fire

Answer: 3 seconds

Approach: BFS from Source Node

The key insight is that fire spreads like BFS (breadth-first search) from the source. But a binary tree only has child pointers, not parent pointers. So we first build a parent map, then BFS from the source in all directions.

Step 1: Map Each Node to Its Parent

python
1from collections import deque
2
3class TreeNode:
4    def __init__(self, val=0, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9def build_parent_map(root):
10    parent = {}
11    queue = deque([root])
12    while queue:
13        node = queue.popleft()
14        if node.left:
15            parent[node.left] = node
16            queue.append(node.left)
17        if node.right:
18            parent[node.right] = node
19            queue.append(node.right)
20    return parent

Step 2: BFS from the Source

python
1def burn_tree(root, target_val):
2    # Find the target node
3    target = find_node(root, target_val)
4    if not target:
5        return -1
6
7    # Build parent map
8    parent = build_parent_map(root)
9
10    # BFS from target
11    queue = deque([(target, 0)])
12    visited = {target}
13    max_time = 0
14
15    while queue:
16        node, time = queue.popleft()
17        max_time = max(max_time, time)
18
19        # Spread to left child
20        if node.left and node.left not in visited:
21            visited.add(node.left)
22            queue.append((node.left, time + 1))
23
24        # Spread to right child
25        if node.right and node.right not in visited:
26            visited.add(node.right)
27            queue.append((node.right, time + 1))
28
29        # Spread to parent
30        if node in parent and parent[node] not in visited:
31            visited.add(parent[node])
32            queue.append((parent[node], time + 1))
33
34    return max_time
35
36def find_node(root, val):
37    if not root:
38        return None
39    if root.val == val:
40        return root
41    return find_node(root.left, val) or find_node(root.right, val)

Complete Solution

python
1# Build the example tree
2root = TreeNode(1)
3root.left = TreeNode(2)
4root.right = TreeNode(3)
5root.left.left = TreeNode(4)
6root.left.right = TreeNode(5)
7
8print(burn_tree(root, 4))  # Output: 3
9print(burn_tree(root, 2))  # Output: 2
10print(burn_tree(root, 1))  # Output: 2

Complexity

  • Time: O(n) — BFS visits each node once, parent map construction is O(n)
  • Space: O(n) — parent map stores n-1 entries, visited set stores n entries, queue holds at most O(n)

Alternative: DFS Approach

You can also solve this with a single DFS that returns the depth from the target:

python
1def burn_tree_dfs(root, target_val):
2    max_time = [0]
3
4    def dfs(node):
5        """Returns distance from node to target, or -1 if target not in subtree."""
6        if not node:
7            return -1
8        if node.val == target_val:
9            # Mark distances of all nodes below target
10            mark_children(node, 0)
11            return 0
12
13        left_dist = dfs(node.left)
14        right_dist = dfs(node.right)
15
16        if left_dist >= 0:
17            # Target is in left subtree
18            dist = left_dist + 1
19            max_time[0] = max(max_time[0], dist)
20            # Fire reaches right subtree through this node
21            mark_children(node.right, dist + 1)
22            return dist
23
24        if right_dist >= 0:
25            dist = right_dist + 1
26            max_time[0] = max(max_time[0], dist)
27            mark_children(node.left, dist + 1)
28            return dist
29
30        return -1
31
32    def mark_children(node, dist):
33        if not node:
34            return
35        max_time[0] = max(max_time[0], dist)
36        mark_children(node.left, dist + 1)
37        mark_children(node.right, dist + 1)
38
39    dfs(root)
40    return max_time[0]
41
42print(burn_tree_dfs(root, 4))  # Output: 3

This avoids building the parent map and uses O(h) stack space where h is the tree height.

Java Implementation

java
1public int burnTree(TreeNode root, int target) {
2    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
3    TreeNode targetNode = buildParentMap(root, parentMap, target);
4
5    Queue<TreeNode> queue = new LinkedList<>();
6    Set<TreeNode> visited = new HashSet<>();
7    queue.offer(targetNode);
8    visited.add(targetNode);
9    int time = -1;
10
11    while (!queue.isEmpty()) {
12        time++;
13        int size = queue.size();
14        for (int i = 0; i < size; i++) {
15            TreeNode node = queue.poll();
16            if (node.left != null && visited.add(node.left))
17                queue.offer(node.left);
18            if (node.right != null && visited.add(node.right))
19                queue.offer(node.right);
20            if (parentMap.containsKey(node) && visited.add(parentMap.get(node)))
21                queue.offer(parentMap.get(node));
22        }
23    }
24    return time;
25}

Common Pitfalls

  • Forgetting to visit parent: A binary tree only has child pointers. Without building a parent map (or using the DFS approach), you cannot spread fire upward, giving an incorrect answer.
  • Not marking visited nodes: Without a visited set, BFS revisits nodes through the parent pointer, causing an infinite loop.
  • Level-based vs node-based BFS: To get the time (number of seconds), process the BFS level by level. Using the (node, time) tuple approach shown above also works.
  • Target not found: If the target node does not exist in the tree, handle the edge case. The function should return -1 or raise an error.
  • Single-node tree: If the tree has only the root and the root is the target, the answer is 0 (already burning).

Summary

  • The burning tree problem equals finding the maximum distance from the source node to any other node
  • Build a parent map (O(n)), then BFS from the source in all three directions (left, right, parent)
  • Time complexity: O(n), Space complexity: O(n)
  • Alternative DFS approach avoids the parent map with O(h) space
  • The answer is the number of BFS levels minus 1 (or the maximum time recorded during traversal)
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.