Time to Burn Entire Tree from a Node
Description
You are given a binary tree and a target node value. Imagine setting the target node on fire. Every second, the fire spreads from a burning node to all of its directly connected neighbours — its left child, right child, and parent. Each node can only catch fire once.
Your task is to determine the minimum number of seconds required for the entire tree to be completely burned.
Note that the tree contains unique node values, so there is exactly one node matching the target.
Examples
Example 1
Input: root = [1, 2, 3, 4, 5, 6, 7], target = 2
1
/ \
2 3
/ \ / \
4 5 6 7
Output: 3
Explanation:
- At t=0: Node 2 is set on fire.
- At t=1: Fire spreads from node 2 to its left child (4), right child (5), and parent (1). Burning nodes: {2, 4, 5, 1}.
- At t=2: Fire spreads from node 1 to its right child (3). Nodes 4 and 5 are leaf nodes so they don't spread further. Burning nodes: {2, 4, 5, 1, 3}.
- At t=3: Fire spreads from node 3 to its children (6, 7). Burning nodes: {2, 4, 5, 1, 3, 6, 7}.
- All nodes are now burned. Total time = 3 seconds.
Example 2
Input: root = [1, 2, 3, 4, 5, N, 7, 8, N, N, 10], target = 10
1
/ \
2 3
/ \ \
4 5 7
/ \
8 10
Output: 5
Explanation:
- At t=0: Node 10 is on fire.
- At t=1: Fire spreads to parent 5.
- At t=2: Fire spreads from 5 to parent 2.
- At t=3: Fire spreads from 2 to children 4 and parent 1.
- At t=4: Fire spreads from 4 to child 8, and from 1 to child 3.
- At t=5: Fire spreads from 3 to child 7.
- All nodes burned. Total time = 5 seconds.
Example 3
Input: root = [1], target = 1
Output: 0
Explanation: The tree has only one node, which is already the target. It is immediately on fire, so 0 seconds are needed.
Constraints
- 1 ≤ number of nodes ≤ 10^5
- 1 ≤ node.data ≤ 10^5
- All node values are unique
- The target node is guaranteed to exist in the tree
Editorial
Brute Force
Intuition
The most straightforward way to think about this problem is to convert the binary tree into an undirected graph and then simulate the fire spreading using a Breadth-First Search (BFS).
In a binary tree, each node naturally connects downward to its children. But fire also spreads upward to the parent. A tree node structure typically only stores pointers to children, not to the parent. So the naive idea is:
- Traverse the entire tree and build an adjacency list representing the tree as an undirected graph — for every parent-child edge, add connections in both directions.
- Find the target node in the adjacency list.
- Run BFS from the target node, level by level. Each BFS level represents one second of fire spreading.
- The number of BFS levels minus one gives the total burn time.
This approach is conceptually clean: it reduces the tree problem to a standard graph BFS problem. However, it requires building a full adjacency list, which means extra memory and a complete first traversal.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, 2, 3, 4, 5, 6, 7], target = 2.
Phase 1: Build Adjacency List
Step 1: Visit node 1. It has left child 2 and right child 3. Add edges: 1↔2, 1↔3.
Step 2: Visit node 2. It has left child 4 and right child 5. Add edges: 2↔4, 2↔5.
Step 3: Visit node 3. It has left child 6 and right child 7. Add edges: 3↔6, 3↔7.
Adjacency list:
- 1: [2, 3]
- 2: [1, 4, 5]
- 3: [1, 6, 7]
- 4: [2]
- 5: [2]
- 6: [3]
- 7: [3]
Phase 2: BFS from target node 2
Step 4: Initialize BFS. Queue = [2], visited = {2}, time = 0.
Step 5: Process level 0 (1 node). Dequeue 2. Enqueue unvisited neighbours: 1, 4, 5. Queue = [1, 4, 5], visited = {2, 1, 4, 5}.
Step 6: Increment time = 1. Process level 1 (3 nodes). Dequeue 1 → enqueue 3. Dequeue 4 → no unvisited neighbours. Dequeue 5 → no unvisited neighbours. Queue = [3], visited = {2, 1, 4, 5, 3}.
Step 7: Increment time = 2. Process level 2 (1 node). Dequeue 3 → enqueue 6, 7. Queue = [6, 7], visited = {2, 1, 4, 5, 3, 6, 7}.
Step 8: Increment time = 3. Process level 3 (2 nodes). Dequeue 6 → no unvisited neighbours. Dequeue 7 → no unvisited neighbours. Queue = []. All nodes visited.
Result: time = 3.
Brute Force BFS — Fire Spreading as Graph Traversal — Watch how the binary tree is treated as an undirected graph, and BFS from the target node simulates fire spreading level by level.
Algorithm
- Traverse the binary tree (using BFS or DFS) to build an undirected adjacency list — for each node with children, add edges in both directions.
- Locate the target node in the adjacency list.
- Initialize BFS from the target node: create a queue with the target, a visited set, and a time counter set to 0.
- While the queue is not empty:
a. Record the current queue size (number of nodes at this level).
b. For each node in the current level, dequeue it and enqueue all unvisited neighbours.
c. If any new nodes were enqueued, increment the time counter. - Return the time counter.
Code
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int minTime(Node* root, int target) {
if (!root) return 0;
// Step 1: Build adjacency list
unordered_map<int, vector<int>> adj;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
if (node->left) {
adj[node->data].push_back(node->left->data);
adj[node->left->data].push_back(node->data);
q.push(node->left);
}
if (node->right) {
adj[node->data].push_back(node->right->data);
adj[node->right->data].push_back(node->data);
q.push(node->right);
}
}
// Step 2: BFS from target
unordered_set<int> visited;
queue<int> bfsQ;
bfsQ.push(target);
visited.insert(target);
int time = 0;
while (!bfsQ.empty()) {
int size = bfsQ.size();
bool spread = false;
for (int i = 0; i < size; i++) {
int curr = bfsQ.front();
bfsQ.pop();
for (int neighbour : adj[curr]) {
if (visited.find(neighbour) == visited.end()) {
visited.insert(neighbour);
bfsQ.push(neighbour);
spread = true;
}
}
}
if (spread) time++;
}
return time;
}
};from collections import deque, defaultdict
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
class Solution:
def minTime(self, root, target):
if not root:
return 0
# Step 1: Build adjacency list
adj = defaultdict(list)
queue = deque([root])
while queue:
node = queue.popleft()
if node.left:
adj[node.data].append(node.left.data)
adj[node.left.data].append(node.data)
queue.append(node.left)
if node.right:
adj[node.data].append(node.right.data)
adj[node.right.data].append(node.data)
queue.append(node.right)
# Step 2: BFS from target
visited = {target}
bfs_queue = deque([target])
time = 0
while bfs_queue:
size = len(bfs_queue)
spread = False
for _ in range(size):
curr = bfs_queue.popleft()
for neighbour in adj[curr]:
if neighbour not in visited:
visited.add(neighbour)
bfs_queue.append(neighbour)
spread = True
if spread:
time += 1
return timeimport java.util.*;
class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
class Solution {
public int minTime(Node root, int target) {
if (root == null) return 0;
// Step 1: Build adjacency list
Map<Integer, List<Integer>> adj = new HashMap<>();
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node node = q.poll();
adj.putIfAbsent(node.data, new ArrayList<>());
if (node.left != null) {
adj.get(node.data).add(node.left.data);
adj.putIfAbsent(node.left.data, new ArrayList<>());
adj.get(node.left.data).add(node.data);
q.add(node.left);
}
if (node.right != null) {
adj.get(node.data).add(node.right.data);
adj.putIfAbsent(node.right.data, new ArrayList<>());
adj.get(node.right.data).add(node.data);
q.add(node.right);
}
}
// Step 2: BFS from target
Set<Integer> visited = new HashSet<>();
Queue<Integer> bfsQ = new LinkedList<>();
bfsQ.add(target);
visited.add(target);
int time = 0;
while (!bfsQ.isEmpty()) {
int size = bfsQ.size();
boolean spread = false;
for (int i = 0; i < size; i++) {
int curr = bfsQ.poll();
for (int neighbour : adj.getOrDefault(curr, new ArrayList<>())) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
bfsQ.add(neighbour);
spread = true;
}
}
}
if (spread) time++;
}
return time;
}
}Complexity Analysis
Time Complexity: O(n)
We traverse all n nodes once to build the adjacency list, and then BFS visits each node exactly once. Both phases are O(n), so the total is O(n).
Space Complexity: O(n)
The adjacency list stores 2 entries per edge. A binary tree with n nodes has n-1 edges, so the adjacency list uses O(n) space. The BFS queue and visited set each hold up to n elements. Total auxiliary space: O(n).
Note: While the time complexity is already optimal at O(n), this approach uses extra space to build a full adjacency list representation of the tree. We can avoid this overhead.
Why This Approach Is Not Efficient
While the brute force runs in O(n) time, it has a significant space overhead: it builds a complete adjacency list as a separate data structure on top of the original tree. This means we store every edge twice (once for each direction) in a hash map, which involves allocation overhead and hash computation.
The core issue is that we build a redundant graph representation. The tree structure already encodes parent→child relationships. We only need to add child→parent edges. Instead of building a full adjacency list, we can simply create a parent pointer map — a single map from each node to its parent. This allows upward traversal without duplicating the entire tree structure.
This leads to a cleaner two-phase approach:
- One BFS/DFS pass to map each node to its parent.
- A second BFS from the target using child pointers (already in the tree) and the parent map for upward traversal.
Optimal Approach - Parent Mapping + BFS
Intuition
The key insight is that in a binary tree, we already have downward links (left and right child pointers). The only missing information for fire propagation is the upward link — how to get from a node to its parent.
Instead of rebuilding the entire tree as a graph, we can make one pass through the tree to create a parent map — a hash map that tells us, for any node, who its parent is. This is much lighter than a full adjacency list.
Once we have the parent map, we can run BFS from the target node. At each step, the fire tries to spread in three directions:
- Left child (using the existing tree pointer)
- Right child (using the existing tree pointer)
- Parent (using our parent map)
We track visited nodes to avoid revisiting burned nodes. Each BFS level represents one second. When the queue empties, the last level number is our answer.
Think of it this way: the parent map gives every child a way to "call" its parent. With that single addition, we can traverse the tree in all directions, just like an undirected graph, but without the overhead of duplicating all edges.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, 2, 3, 4, 5, 6, 7], target = 2.
Phase 1: Build Parent Map
Step 1: BFS starting at root (1). Node 1 has no parent.
Step 2: Visit node 1. Left child is 2 → parent[2] = 1. Right child is 3 → parent[3] = 1. Also, find that node 2 matches target, save a reference to it.
Step 3: Visit node 2. Left child is 4 → parent[4] = 2. Right child is 5 → parent[5] = 2.
Step 4: Visit node 3. Left child is 6 → parent[6] = 3. Right child is 7 → parent[7] = 3.
Parent map: {2→1, 3→1, 4→2, 5→2, 6→3, 7→3}
Target node reference: node with value 2.
Phase 2: BFS from Target Node
Step 5: Initialize. Queue = [node 2], visited = {2}, time = 0.
Step 6: Process level 0. Dequeue node 2. Check three directions:
- Left child: node 4 (not visited) → enqueue.
- Right child: node 5 (not visited) → enqueue.
- Parent: parent[2] = node 1 (not visited) → enqueue.
Queue = [4, 5, 1]. Visited = {2, 4, 5, 1}. Fire spread → time = 1.
Step 7: Process level 1. Dequeue node 4. Left/right are null, parent is 2 (visited). No new nodes.
Dequeue node 5. Left/right are null, parent is 2 (visited). No new nodes.
Dequeue node 1. Left child 2 (visited), right child 3 (not visited) → enqueue 3. Parent doesn't exist (root).
Queue = [3]. Visited = {2, 4, 5, 1, 3}. Fire spread → time = 2.
Step 8: Process level 2. Dequeue node 3. Left child 6 (not visited) → enqueue. Right child 7 (not visited) → enqueue. Parent is 1 (visited).
Queue = [6, 7]. Visited = {2, 4, 5, 1, 3, 6, 7}. Fire spread → time = 3.
Step 9: Process level 3. Dequeue 6 (leaf, no new). Dequeue 7 (leaf, no new). Queue empty. No spread.
Result: time = 3.
Optimal — Parent Mapping + BFS Fire Spread — Watch how we use parent pointers to let fire travel upward, enabling BFS to spread in all three directions from each node.
Algorithm
- Build parent map: Traverse the tree using BFS. For each node, record its parent in a hash map. Also, locate the target node during this traversal.
- BFS from target: Initialize a queue with the target node, a visited set containing the target, and a time counter at 0.
- Process each level:
a. For each node at the current level, attempt to spread fire in three directions:- Left child (if exists and unvisited)
- Right child (if exists and unvisited)
- Parent (from parent map, if exists and unvisited)
b. Mark all newly reached nodes as visited and enqueue them.
- Track time: If any new node was enqueued during this level, increment time.
- Termination: When the queue is empty, return the time counter.
Code
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int minTime(Node* root, int target) {
if (!root) return 0;
// Phase 1: Build parent map and find target node
unordered_map<Node*, Node*> parent;
Node* targetNode = nullptr;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
if (node->data == target) {
targetNode = node;
}
if (node->left) {
parent[node->left] = node;
q.push(node->left);
}
if (node->right) {
parent[node->right] = node;
q.push(node->right);
}
}
// Phase 2: BFS from target node
unordered_set<Node*> visited;
queue<Node*> bfsQ;
bfsQ.push(targetNode);
visited.insert(targetNode);
int time = 0;
while (!bfsQ.empty()) {
int size = bfsQ.size();
bool spread = false;
for (int i = 0; i < size; i++) {
Node* curr = bfsQ.front();
bfsQ.pop();
// Try left child
if (curr->left && visited.find(curr->left) == visited.end()) {
visited.insert(curr->left);
bfsQ.push(curr->left);
spread = true;
}
// Try right child
if (curr->right && visited.find(curr->right) == visited.end()) {
visited.insert(curr->right);
bfsQ.push(curr->right);
spread = true;
}
// Try parent
if (parent.count(curr) && visited.find(parent[curr]) == visited.end()) {
visited.insert(parent[curr]);
bfsQ.push(parent[curr]);
spread = true;
}
}
if (spread) time++;
}
return time;
}
};from collections import deque
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
class Solution:
def minTime(self, root, target):
if not root:
return 0
# Phase 1: Build parent map and find target node
parent = {}
target_node = None
queue = deque([root])
while queue:
node = queue.popleft()
if node.data == target:
target_node = node
if node.left:
parent[node.left] = node
queue.append(node.left)
if node.right:
parent[node.right] = node
queue.append(node.right)
# Phase 2: BFS from target node
visited = {target_node}
bfs_queue = deque([target_node])
time = 0
while bfs_queue:
size = len(bfs_queue)
spread = False
for _ in range(size):
curr = bfs_queue.popleft()
# Try left child
if curr.left and curr.left not in visited:
visited.add(curr.left)
bfs_queue.append(curr.left)
spread = True
# Try right child
if curr.right and curr.right not in visited:
visited.add(curr.right)
bfs_queue.append(curr.right)
spread = True
# Try parent
if curr in parent and parent[curr] not in visited:
visited.add(parent[curr])
bfs_queue.append(parent[curr])
spread = True
if spread:
time += 1
return timeimport java.util.*;
class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
class Solution {
public int minTime(Node root, int target) {
if (root == null) return 0;
// Phase 1: Build parent map and find target node
Map<Node, Node> parent = new HashMap<>();
Node targetNode = null;
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node node = q.poll();
if (node.data == target) {
targetNode = node;
}
if (node.left != null) {
parent.put(node.left, node);
q.add(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
q.add(node.right);
}
}
// Phase 2: BFS from target node
Set<Node> visited = new HashSet<>();
Queue<Node> bfsQ = new LinkedList<>();
bfsQ.add(targetNode);
visited.add(targetNode);
int time = 0;
while (!bfsQ.isEmpty()) {
int size = bfsQ.size();
boolean spread = false;
for (int i = 0; i < size; i++) {
Node curr = bfsQ.poll();
// Try left child
if (curr.left != null && !visited.contains(curr.left)) {
visited.add(curr.left);
bfsQ.add(curr.left);
spread = true;
}
// Try right child
if (curr.right != null && !visited.contains(curr.right)) {
visited.add(curr.right);
bfsQ.add(curr.right);
spread = true;
}
// Try parent
if (parent.containsKey(curr) && !visited.contains(parent.get(curr))) {
visited.add(parent.get(curr));
bfsQ.add(parent.get(curr));
spread = true;
}
}
if (spread) time++;
}
return time;
}
}Complexity Analysis
Time Complexity: O(n)
Phase 1 (parent map construction) traverses all n nodes once via BFS — O(n). Phase 2 (fire BFS) also visits each node at most once — O(n). Total: O(n) + O(n) = O(n).
At each node during the BFS, we do at most 3 constant-time lookups (left child, right child, parent), so the per-node work is O(1).
Space Complexity: O(n)
The parent map stores one entry per non-root node — O(n). The BFS queue holds at most one full level of the tree — O(n) in the worst case (a complete binary tree's last level has ~n/2 nodes). The visited set stores all n nodes. Total: O(n).
This is the same asymptotic complexity as the brute force, but in practice the parent map is lighter than a full adjacency list because it stores only n-1 entries (one per non-root node) with no duplication, compared to the adjacency list which stores 2(n-1) entries.