Log inSign up
hardgeeksforgeeksNot Started

Burning Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree and a leaf node/target node from which fire starts, find the minimum time required to burn the complete binary tree. The fire burns adjacent nodes (left child, right child, and parent) in 1 second.

Example 1 · Example 1: Target Inside Subtree:

Input: root = [1, 2, 3, 4, 5, null, 6, null, null, 7, 8, null, 9, null, null, null, null, null, 10], target = 8 Tree: 1 / \ 2 3 / \ \ 4 5 6 / \ \ 7 8 9 \ 10
Output: 7
Explanation: Fire starts at 8. Takes 7 seconds to reach node 10 through parent 5 -> 2 -> 1 -> 3 -> 6 -> 9 -> 10.

Example 2 · Example 2: 3-Node Tree:

Input: root = [1, 2, 3], target = 2 Tree: 1 / \ 2 3
Output: 2
Explanation: t=0: node 2 burns. t=1: node 1 burns. t=2: node 3 burns.

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 105
  • Target is guaranteed to exist in the tree.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Convert directed tree pointers into an undirected graph via a parent hash map.
  • Simulate simultaneous radial diffusion using level-order BFS.
  • Understand why maximum fire spread time equals graph radius from target.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Infection / burning spread in a tree.
  • Adjacent nodes (left, right, parent) affected per time unit.
  • Maximum distance from an arbitrary tree node.

Algorithmic Decision Tree:

  • Pass 1: Map child -> parent and find pointer to target node.
  • Pass 2: Queue BFS starting from target. Use visited set.
  • Spread to curr.left, curr.right, parentMap[curr].
  • Increment time only when new nodes are ignited.

Connected Patterns:

All Nodes Distance K in Binary TreeAmount of Time for Binary Tree to Be InfectedShortest Path in Unweighted Graph

1. Full Tree to Graph Conversion + BFS

Intuition

Convert tree into an undirected graph representation with adjacency lists. Then run standard BFS from target vertex until all reachable vertices are visited.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Traverse tree to create bidirectional adjacency list adj[u].push(v) and adj[v].push(u).
  2. Step 2: Initialize queue with target, visited set with target.
  3. Step 3: Track levels. For each level, pop all current nodes and enqueue unvisited neighbors.
  4. Step 4: Return total level count - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void buildGraph(TreeNode* node, TreeNode* parent, unordered_map<int, vector<int>>& adj) {
10 if (!node) return;
11 if (parent) {
12 adj[node->val].push_back(parent->val);
13 adj[parent->val].push_back(node->val);
14 }
15 buildGraph(node->left, node, adj);
16 buildGraph(node->right, node, adj);
17 }
18 int minTime(TreeNode* root, int target) {
19 unordered_map<int, vector<int>> adj;
20 buildGraph(root, nullptr, adj);
21 queue<int> q;
22 unordered_set<int> visited;
23 q.push(target);
24 visited.insert(target);
25 int time = 0;
26 while (!q.empty()) {
27 int sz = q.size();
28 bool burned = false;
29 for (int i = 0; i < sz; ++i) {
30 int curr = q.front(); q.pop();
31 for (int nxt : adj[curr]) {
32 if (!visited.count(nxt)) {
33 visited.insert(nxt);
34 q.push(nxt);
35 burned = true;
36 }
37 }
38 }
39 if (burned) time++;
40 }
41 return time;
42 }
43};
44
45int main() {
46 // Sample driver execution
47 cout << "Execution completed successfully." << endl;
48 return 0;
49}
50

Time & Space Complexity

  • Time complexity: O(n) — Graph creation takes O(n); BFS visits all n nodes.
  • Space complexity: O(n) — Graph adjacency list stores 2*(n-1) edges.

2. Single DFS Height Calculation

Intuition

DFS computes distance from target up to each ancestor while concurrently finding the height of opposite subtrees. Time is updated as distanceToTarget + heightOfOppositeSubtree.

When to apply: When attempting to solve without BFS queues.

Algorithm

  1. Step 1: Recursive dfs(node, target): returns height if target not in subtree, or negative distance to target if target found.
  2. Step 2: If target found in left subtree, maxDistance = max(maxDistance, abs(dist) + height(right)).
  3. Step 3: Return updated distance.
  4. Step 4: Return global maxDistance recorded.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int maxTime = 0;
9 int dfs(TreeNode* root, int target) {
10 if (!root) return 0;
11 if (root->val == target) {
12 maxHeight(root->left, 1);
13 maxHeight(root->right, 1);
14 return -1;
15 }
16 int l = dfs(root->left, target);
17 int r = dfs(root->right, target);
18 if (l < 0) {
19 maxTime = max(maxTime, abs(l) + r);
20 return l - 1;
21 }
22 if (r < 0) {
23 maxTime = max(maxTime, abs(r) + l);
24 return r - 1;
25 }
26 return 1 + max(l, r);
27 }
28 void maxHeight(TreeNode* node, int depth) {
29 if (!node) return;
30 maxTime = max(maxTime, depth);
31 maxHeight(node->left, depth + 1);
32 maxHeight(node->right, depth + 1);
33 }
34public:
35 int minTime(TreeNode* root, int target) {
36 maxTime = 0;
37 dfs(root, target);
38 return maxTime;
39 }
40};
41
42int main() {
43 // Sample driver execution
44 cout << "Execution completed successfully." << endl;
45 return 0;
46}
47

Time & Space Complexity

  • Time complexity: O(n) — Single pass over all nodes.
  • Space complexity: O(h) — Call stack up to tree height h.

3. Parent Pointer Map + Radial Fire BFS

Intuition

1. Build parentMap and locate target node pointer using a BFS pass. 2. Start fire BFS with target in queue. Mark target visited. 3. At each second, spread to left child, right child, and parent. If any new node is ignited, time++. 4. Return total elapsed time.

When to apply: Optimal gold-standard solution: most intuitive, bug-free, and directly simulates the physical process.

Algorithm

  1. Step 1: Traverse tree to find target TreeNode* and populate parentMap[child] = parent.
  2. Step 2: Initialize BFS queue with target node. Set visited = {target}, time = 0.
  3. Step 3: While queue is not empty, get size. Flag hasBurned = false.
  4. Step 4: For each node, check unvisited left, right, and parent. Push to queue, mark visited, set hasBurned = true.
  5. Step 5: If hasBurned is true, time++. Return time.

Burning Tree Radial BFS Trace for root = [1, 2, 3], target = 2

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1 (t=0): Target is node 2
Visual state
Values and pointers at this exact step
tree
Root
1
L (Ignited)
2 (Fire!)
R
3

Node order shown; add connections to display explicit tree edges.

fire (t=0): 2
Check / comparison
Fire begins at target node 2.
Decision / next transition
Enqueue 2, mark as burned.
Why this step matters

Step 1 (t=0): Target is node 2. Ignite node 2. Queue contains [2]. Visited = {2}. Parent map: parent[2]=1, parent[3]=1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minTime(TreeNode* root, int target) {
10 unordered_map<TreeNode*, TreeNode*> parentMap;
11 TreeNode* targetNode = nullptr;
12 queue<TreeNode*> q;
13 q.push(root);
14 while (!q.empty()) {
15 TreeNode* cur = q.front(); q.pop();
16 if (cur->val == target) targetNode = cur;
17 if (cur->left) { parentMap[cur->left] = cur; q.push(cur->left); }
18 if (cur->right) { parentMap[cur->right] = cur; q.push(cur->right); }
19 }
20 unordered_set<TreeNode*> visited;
21 queue<TreeNode*> fireQ;
22 fireQ.push(targetNode);
23 visited.insert(targetNode);
24 int time = 0;
25 while (!fireQ.empty()) {
26 int sz = fireQ.size();
27 bool hasBurned = false;
28 for (int i = 0; i < sz; ++i) {
29 TreeNode* cur = fireQ.front(); fireQ.pop();
30 if (cur->left && !visited.count(cur->left)) {
31 visited.insert(cur->left);
32 fireQ.push(cur->left);
33 hasBurned = true;
34 }
35 if (cur->right && !visited.count(cur->right)) {
36 visited.insert(cur->right);
37 fireQ.push(cur->right);
38 hasBurned = true;
39 }
40 TreeNode* p = parentMap[cur];
41 if (p && !visited.count(p)) {
42 visited.insert(p);
43 fireQ.push(p);
44 hasBurned = true;
45 }
46 }
47 if (hasBurned) time++;
48 }
49 return time;
50 }
51};
52
53int main() {
54 // Sample driver execution
55 cout << "Execution completed successfully." << endl;
56 return 0;
57}
58

Time & Space Complexity

  • Time complexity: O(n) — Parent mapping is O(n), fire BFS is O(n). Total runtime is O(n).
  • Space complexity: O(n) — Queue, parent map, and visited set all take O(n) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Adjacency List Graph + BFSO(n)O(n)Full graph conversion with 2*(n-1) edges.Excess allocations.
2.Single DFS Height CalculationO(n)O(h)Calculates distance to target and opposite heights on unwind.Prone to subtle logic bugs.
3.Parent Pointer Map + Radial Fire BFSOptimalO(n)O(n)Parent pointer map followed by radial BFS level expansion.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: Target is root, fire burns tree in 0 seconds.
  • Target is root: Fire only spreads downward.
  • Target is leaf: Fire must travel all the way up through root to burn opposite subtree.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether time starts at 0 (fire starts at target at t=0, neighbors burn at t=1).
  2. Be careful to increment time only if at least one adjacent node caught fire during the current iteration.
  3. Mention that this is equivalent to LeetCode 2385 (Amount of Time for Binary Tree to Be Infected).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the fire BFS loop only increment time when hasBurned is true?

Back to DSA Sheet