Why is parent information required?

A binary tree normally provides references only to its children. Since fire can also move from a node to its parent, an additional parent connection is required unless the recursive approach is used.

Why is a burned set required in the BFS approaches?

Once upward movement is introduced, a child can reach its parent and the parent can lead back to the same child. The burned set prevents such revisits and ensures that every node catches fire only once.

What happens when the target is the only node in the tree?

The complete tree is already burning at time 0, so the minimum burning time is 0.

Why is the answer equal to the maximum distance from the target?

Every node at distance d from the target catches fire after exactly d seconds. Therefore, the entire tree finishes burning when the node farthest from the target catches fire.

Which approach is generally preferred in interviews?

The parent mapping + BFS approach is generally the easiest to implement and explain because it directly models the burning process. The postorder DFS approach also runs in O(N) time and uses only O(H) recursion space, but its distance calculations require more careful reasoning.

Minimum Time to Burn a Binary Tree from a Given Node

Given the root of a binary tree and a target node present in the tree, determine the minimum time required to burn the entire tree if the fire starts from the target.

The fire spreads every second from a burning node to all directly connected nodes:

its left child,
its right child,
its parent.

A node burns only once, and all possible neighboring nodes catch fire simultaneously.

Example 1

Input:
root = [1, 2, 3, 4, 5, null, 6], target = 2

Output:
3

Explanation:
At time 0, node 2 starts burning. After 1 second, nodes 1, 4, and 5 burn. After 2 seconds, node 3 burns, and after 3 seconds, node 6 burns. Therefore, the entire tree burns in 3 seconds.

Example 2

Input:
root = [1], target = 1

Output:
0

Explanation:
The target is the only node in the tree, so the complete tree is already burning at time 0.

Practice it by yourself before moving onto the solutionTry now

Approach 1

A binary tree normally provides links only from a parent to its children. Burning, however, must be allowed to spread in both directions.

Therefore, every parent-child connection is converted into an undirected edge. Once this conversion is performed, the tree behaves like an undirected graph in which the fire can move to every directly connected node.

A BFS is then started from the target.

A queue is used because nodes that burn at the same second must be processed together. The variable levelSize stores the number of nodes burning during the current second so that exactly one BFS level can be processed at a time.

A set named burned is maintained to represent nodes that have already caught fire. It prevents the same node from being reached repeatedly through the bidirectional graph.

A boolean variable spread is used to record whether at least one new node caught fire during the current BFS level. Time is increased only when spread becomes true, because a second should be counted only when the fire actually reaches another node.

Algorithm

An adjacency list is constructed by traversing the binary tree, and every parent-child connection is stored in both directions so that fire can spread both upward and downward.
A BFS queue is initialized with the target, and the target is inserted into the burned set because it is already burning at time 0.
For each BFS iteration, the current queue size is stored in levelSize so that all nodes burning during the same second are processed together.
A boolean variable spread is initialized as false before the current level is processed so that it can record whether the fire reaches at least one new node.
For every node in the current level, all adjacent nodes that are not present in burned are marked as burned, inserted into the queue, and spread is set to true.
After the complete level has been processed, the burning time is increased by 1 only if spread is true, because at least one new node has caught fire.
The process is continued until the queue becomes empty, after which the recorded time is returned.

Dry Run

Burning Tree Approach 1 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Builds an undirected graph so fire
  // can move between parent and child.
  void buildGraph(
      TreeNode* node,
      unordered_map<TreeNode*, vector<TreeNode*>>& graph
  ) {
      if (node == nullptr) {
          return;
      }
27
      // Both directions are stored because
      // fire can spread upward and downward.
      if (node->left != nullptr) {
          graph[node].push_back(node->left);
          graph[node->left].push_back(node);
33
          buildGraph(node->left, graph);
      }
36
      if (node->right != nullptr) {
          graph[node].push_back(node->right);
          graph[node->right].push_back(node);
40
          buildGraph(node->right, graph);
      }
  }
44
45public:
  // Returns the minimum time required
  // to burn the complete tree.
  int minTime(
      TreeNode* root,
      TreeNode* target
  ) {
      if (root == nullptr) {
          return 0;
      }
55
      unordered_map<TreeNode*, vector<TreeNode*>> graph;
      buildGraph(root, graph);
58
      queue<TreeNode*> nodesQueue;
      unordered_set<TreeNode*> burned;
61
      nodesQueue.push(target);
63
      // The target starts burning at time 0,
      // so it is marked before BFS begins.
      burned.insert(target);
67
      int time = 0;
69
      while (!nodesQueue.empty()) {
          int levelSize = nodesQueue.size();
72
          // spread records whether at least one
          // new node catches fire this second.
          bool spread = false;
76
          // levelSize keeps all nodes burning
          // during the same second together.
          for (int i = 0; i < levelSize; i++) {
              TreeNode* node = nodesQueue.front();
              nodesQueue.pop();
82
              for (TreeNode* neighbor : graph[node]) {
                  if (burned.find(neighbor) == burned.end()) {
                      burned.insert(neighbor);
                      nodesQueue.push(neighbor);
                      spread = true;
                  }
              }
          }
91
          // Time advances only when the fire
          // actually spreads to another node.
          if (spread) {
              time++;
          }
      }
98
      return time;
  }
101};
102
103int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->right = new TreeNode(6);
110
  TreeNode* target = root->left;
112
  Solution solution;
114
  cout << solution.minTime(root, target) << endl;
116
  return 0;
118}

Complexity Analysis

Let N be the number of nodes in the binary tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every tree edge is added to the adjacency structure a constant number of times, and every node is processed at most once during BFS.

Space Complexity: O(N). The adjacency list, burned set, and BFS queue can together store information for up to N nodes.

Approach 2

Constructing a complete undirected graph is unnecessary because every node already provides references to its left and right children.

The only missing connection is:

child → parent

Therefore, a map named parentTrack can be maintained. The name indicates that it is used to track the parent of each node, allowing the fire to move upward during BFS.

After this preprocessing, every node effectively has at most three neighbors:

left child,
right child,
parent.

A queue is then used to simulate the burning process level by level.

The variable levelSize stores how many nodes are burning during the current second. A set named burned keeps track of nodes that have already caught fire so that the fire cannot move back and forth between a node and its parent.

A boolean variable spread records whether any new node catches fire during the current level. The elapsed time is increased only when this happens.

Algorithm

A queue-based traversal is performed from the root, and a map named parentTrack is constructed so that every non-root node is associated with its parent.
The root is stored with no parent, or is treated separately, because no node exists above it.
A BFS queue is initialized with the target, and the target is inserted into the burned set because it burns at time 0.
At the beginning of each BFS level, the number of currently burning nodes is stored in levelSize, while spread is initialized as false.
For every node in that level, its left child, right child, and mapped parent are examined.
Whenever an existing neighbor has not already been burned, it is inserted into burned and the queue, while spread is set to true.
After all levelSize nodes have been processed, the elapsed time is increased only when spread is true, indicating that the fire has reached at least one new node.
Once the queue becomes empty, the recorded time is returned as the minimum time required to burn the entire tree.

Dry Run

Burning Tree Approach 2 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Builds child-to-parent links so fire
  // can also spread upward.
  void buildParentTrack(
      TreeNode* root,
      unordered_map<TreeNode*, TreeNode*>& parentTrack
  ) {
      queue<TreeNode*> nodesQueue;
      nodesQueue.push(root);
26
      // The root has no parent, so nullptr
      // marks the end of upward movement.
      parentTrack[root] = nullptr;
30
      while (!nodesQueue.empty()) {
          TreeNode* node =
              nodesQueue.front();
34
          nodesQueue.pop();
36
          if (node->left != nullptr) {
              parentTrack[node->left] = node;
              nodesQueue.push(node->left);
          }
41
          if (node->right != nullptr) {
              parentTrack[node->right] = node;
              nodesQueue.push(node->right);
          }
      }
  }
48
49public:
  // Simulates the fire using left,
  // right, and parent connections.
  int minTime(
      TreeNode* root,
      TreeNode* target
  ) {
      if (root == nullptr) {
          return 0;
      }
59
      unordered_map<TreeNode*, TreeNode*> parentTrack;
61
      buildParentTrack(
          root,
          parentTrack
      );
66
      queue<TreeNode*> nodesQueue;
      unordered_set<TreeNode*> burned;
69
      nodesQueue.push(target);
      burned.insert(target);
72
      int time = 0;
74
      while (!nodesQueue.empty()) {
          int levelSize =
              nodesQueue.size();
78
          // spread tells whether fire moved
          // to at least one new node.
          bool spread = false;
82
          // levelSize represents all nodes
          // burning during the current second.
          for (int i = 0; i < levelSize; i++) {
              TreeNode* node =
                  nodesQueue.front();
88
              nodesQueue.pop();
90
              if (
                  node->left != nullptr &&
                  burned.find(node->left) == burned.end()
              ) {
                  burned.insert(node->left);
                  nodesQueue.push(node->left);
                  spread = true;
              }
99
              if (
                  node->right != nullptr &&
                  burned.find(node->right) == burned.end()
              ) {
                  burned.insert(node->right);
                  nodesQueue.push(node->right);
                  spread = true;
              }
108
              TreeNode* parent =
                  parentTrack[node];
111
              // parentTrack supplies the upward
              // connection missing from the tree.
              if (
                  parent != nullptr &&
                  burned.find(parent) == burned.end()
              ) {
                  burned.insert(parent);
                  nodesQueue.push(parent);
                  spread = true;

Complexity Analysis

Let N be the number of nodes in the binary tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Building parentTrack visits every node once, and the subsequent BFS processes every node at most once.

Space Complexity: O(N). The parentTrack map, burned set, and BFS queue can each contain information for up to N nodes in the worst case.

Approach 3

The total burning time is equal to the maximum distance from the target to any node in the tree.

Instead of explicitly creating parent connections and simulating every second, this maximum distance can be determined using postorder DFS.

For every subtree, two pieces of information are useful:

height represents how far the deepest node lies below the current subtree.
distanceFromTarget represents the distance from the current node to the target. A value of -1 indicates that the target is absent from that subtree.

Suppose the target is found in the left subtree. If distanceFromTarget represents the distance from the current node to the target, the fire can reach a node in the opposite right subtree by travelling:

target → current node → right subtree

If the opposite subtree has height oppositeHeight, the total distance to its deepest node becomes:

distanceFromTarget + 1 + oppositeHeight

The additional 1 represents the edge from the current node into the root of the opposite subtree.

The same reasoning is applied symmetrically when the target lies in the right subtree.

By evaluating this maximum distance at every ancestor, the farthest node from the target is found.

Algorithm

A postorder DFS is performed so that information from the left and right child subtrees is available before the current node is processed.
For every subtree, its height is calculated so that the maximum downward distance available through that subtree is known.
A value named distanceFromTarget is maintained to represent the number of edges between the current node and the target, while -1 is used when the target is absent from that subtree.
When the target itself is reached, distanceFromTarget is set to 0, and the subtree height is used to account for nodes lying below the target.
If the target is found in the left subtree, its returned distance is increased by 1 to obtain the current node's distanceFromTarget.
The farthest distance through the opposite right subtree is then calculated using distanceFromTarget + 1 + rightHeight, where the additional 1 represents the edge from the current node to the right child.
The same calculation is performed symmetrically when the target is found in the right subtree, using the height of the left subtree.
The maximum burning distance is updated whenever a larger candidate is obtained, and distanceFromTarget is propagated upward.
After the root has been completely processed, the maximum recorded distance is returned as the minimum burning time.

Dry Run

Burning Tree Approach 3 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  struct Info {
      int height;
      int distanceFromTarget;
  };
22
  // Returns subtree height and the distance
  // from the current node to the target.
  Info dfs(
      TreeNode* node,
      TreeNode* target,
      int& maxTime
  ) {
      if (node == nullptr) {
          return {-1, -1};
      }
33
      Info left =
          dfs(node->left, target, maxTime);
36
      Info right =
          dfs(node->right, target, maxTime);
39
      int height =
          1 + max(left.height, right.height);
42
      // When target is reached, its subtree
      // height gives the farthest downward burn.
      if (node == target) {
          maxTime = max(
              maxTime,
              height
          );
50
          return {height, 0};
      }
53
      if (left.distanceFromTarget != -1) {
          int distanceFromTarget =
              left.distanceFromTarget + 1;
57
          // The route moves from target to this
          // ancestor, then one edge into the
          // opposite subtree and to its deepest node.
          maxTime = max(
              maxTime,
              distanceFromTarget
              + 1
              + right.height
          );
67
          return {
              height,
              distanceFromTarget
          };
      }
73
      if (right.distanceFromTarget != -1) {
          int distanceFromTarget =
              right.distanceFromTarget + 1;
77
          // The left subtree is the opposite
          // branch when target lies on the right.
          maxTime = max(
              maxTime,
              distanceFromTarget
              + 1
              + left.height
          );
86
          return {
              height,
              distanceFromTarget
          };
      }
92
      return {height, -1};
  }
95
96public:
  // Finds the maximum distance from target
  // without storing explicit parent links.
  int minTime(
      TreeNode* root,
      TreeNode* target
  ) {
      if (root == nullptr) {
          return 0;
      }
106
      int maxTime = 0;
108
      dfs(
          root,
          target,
          maxTime
      );
114
      return maxTime;
  }
117};
118
119int main() {
  TreeNode* root = new TreeNode(1);

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is processed once during the postorder traversal.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Interview follow-up Questions

Fire spreads through exactly one edge every second. BFS also explores nodes one edge farther from the starting node at each level, so one BFS level corresponds directly to one second.

Minimum Time to Burn a Binary Tree from a Given Node

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 3

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Minimum Time to Burn a Binary Tree from a Given Node

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 3

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why does BFS naturally represent the burning process?

Why is parent information required?

Why is a burned set required in the BFS approaches?

What happens when the target is the only node in the tree?

Why is the answer equal to the maximum distance from the target?

Which approach is generally preferred in interviews?

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree