Skip to content

Burning Tree

Fire Doesn't Respect Parent-Child Relationships

Problem: A fire starts at a given node in a binary tree. Each second, the fire spreads to all directly connected nodes (children and parent). Return the minimum time to burn the entire tree.

        1
       / \
      2   3
     / \    \
    4   5    6

Fire starts at node 2. Here's how it spreads:

  • \(t = 0\): node 2 is burning.
  • \(t = 1\): fire spreads to 4, 5, and 1 (parent).
  • \(t = 2\): fire spreads from 1 to 3.
  • \(t = 3\): fire spreads from 3 to 6.

Total time: 3 seconds.

The fire spreads in all directions — down to children AND up to the parent. Sound familiar? This is the same "bidirectional movement" from the previous lesson.

The mental shift: stop thinking "tree" and start thinking "graph." A tree with parent edges is just an undirected graph. Fire spreading level-by-level is just BFS.

Fire spreading from the source node outward through the tree as an undirected graph, one level per second

The Approach: Convert + BFS

Two steps, same pattern as LC 863:

  1. Convert the tree to an adjacency list. Every edge becomes bidirectional.
  2. BFS from the fire source. Count the number of BFS levels until every node is visited. That's the burn time.

The only difference from the previous lesson: last time we stopped BFS at distance \(k\). This time we run BFS to completion and count the total number of levels.

Step 1: Build the Adjacency List

Walk the tree with DFS. For every parent-child pair, add edges in both directions.

        1
       / \
      2   3
     / \    \
    4   5    6
Edge Found Add to Graph
1 → 2 graph[1] += 2, graph[2] += 1
2 → 4 graph[2] += 4, graph[4] += 2
2 → 5 graph[2] += 5, graph[5] += 2
1 → 3 graph[1] += 3, graph[3] += 1
3 → 6 graph[3] += 6, graph[6] += 3

Final adjacency list:

Node Neighbors
1 [2, 3]
2 [1, 4, 5]
3 [1, 6]
4 [2]
5 [2]
6 [3]

This is now a standard undirected graph. The tree structure is gone — every node is just an integer with a list of neighbors.

Step 2: BFS from the Source

Start BFS from node 2. Process level by level. Each level = one second of fire spreading.

Full BFS Trace

Time Queue (start of level) Nodes Processed New Nodes Added Burning Nodes
0 [2] 2 1, 4, 5 {2}
1 [1, 4, 5] 1 → adds 3; 4 → none new; 5 → none new 3 {2, 1, 4, 5}
2 [3] 3 → adds 6 6 {2, 1, 4, 5, 3}
3 [6] 6 → no new neighbors — {2, 1, 4, 5, 3, 6}

After time step 3, the queue is empty. All 6 nodes have been visited. Answer: 3.

Notice: BFS processes 3 full levels after the initial level (time 0). The time counter starts at \(-1\) and increments once per level, or equivalently, it's the number of levels minus 1.

The Code

void buildAdjacencyList(TreeNode* node,
                        unordered_map<int, vector<int>>& graph) {
    if (!node) return;
    if (node->left) {
        graph[node->val].push_back(node->left->val);
        graph[node->left->val].push_back(node->val);
        buildAdjacencyList(node->left, graph);
    }
    if (node->right) {
        graph[node->val].push_back(node->right->val);
        graph[node->right->val].push_back(node->val);
        buildAdjacencyList(node->right, graph);
    }
}

int timeToBurnTree(TreeNode* root, int startVal) {
    unordered_map<int, vector<int>> graph;
    buildAdjacencyList(root, graph);

    queue<int> bfsQueue;
    unordered_set<int> visited;
    bfsQueue.push(startVal);
    visited.insert(startVal);
    int timeSteps = -1;

    while (!bfsQueue.empty()) {
        int levelSize = bfsQueue.size();
        for (int i = 0; i < levelSize; i++) {
            int current = bfsQueue.front();
            bfsQueue.pop();
            for (int neighbor : graph[current]) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    bfsQueue.push(neighbor);
                }
            }
        }
        timeSteps++;
    }
    return timeSteps;
}

Complexity: \(O(n)\) time, \(O(n)\) space.

Why Adjacency List Instead of Parent Pointers?

In the previous lesson, we used parent pointers (a map from TreeNode* to TreeNode*). Here we use an adjacency list (a map from int to vector<int>). Both work. The difference:

  • Parent pointers keep the tree structure — you still navigate via node->left, node->right, and parentMap[node]. You work with TreeNode* throughout.
  • Adjacency list abandons the tree entirely. Nodes become integers. Edges become neighbor lists. You're working with a pure graph.

The adjacency list approach is more general. If you later need to solve the problem on an n-ary tree (not binary), the adjacency list code works unchanged. Parent pointers would require modifying the BFS to iterate over all children.

Pattern: when a tree problem requires bidirectional traversal, convert to an adjacency list. This is not a tree technique — it's a graph technique applied to a tree. The Graph course covers BFS/DFS in full generality. What you're learning here is the conversion step.

Adjacency List vs Parent Map: When to Use Which

Situation Use
Binary tree, need parent access only Parent pointer map
Need to treat tree as undirected graph for BFS/DFS Adjacency list
N-ary tree, bidirectional traversal Adjacency list
Need to preserve tree structure during BFS Parent pointer map

Both approaches are \(O(n)\) to build and \(O(n)\) space. The adjacency list is slightly more work to construct but gives you a cleaner BFS loop.

Try It

The starter code has a timeToBurnTree function with a TODO. Fill in the body.

Input: Tree = [1,2,3,4,5,null,6], start = 2
Output: 3

Predict before running: What if the fire starts at a leaf? Say node 6 in the example tree. The fire has to travel all the way across the tree. The answer would be the distance from node 6 to the farthest node (node 4 or 5), which is 4.

Challenge: What if the tree has only one node and the fire starts there? BFS processes one level (the source), increments time from \(-1\) to 0, and returns 0. Correct — a single node burns instantly.

Edge Cases to Watch For

  • Adjacency list with duplicate edges: When building the adjacency list, each parent-child pair should add exactly TWO directed edges (one in each direction). If you accidentally add the same direction twice, duplicate neighbors can cause incorrect BFS behavior if your visited check has any bugs.

Problems

Problem Link Difficulty
LC 2385 — Amount of Time for Binary Tree to Be Infected leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected Medium
LC 863 — All Nodes Distance K in Binary Tree leetcode.com/problems/all-nodes-distance-k-in-binary-tree Medium
Burning Tree (GFG) geeksforgeeks.org/burn-the-binary-tree-starting-from-the-target-node Medium