L31: Minimum Time Taken to Burn the Binary Tree from a Node

1. Problem Statement and Objective

The objective of this problem is to calculate the minimum total time (in seconds) required to completely burn a binary tree starting from a given target node.

In this simulation, burning spreads radially outwards from the burning node to its immediate neighbors (left child, right child, and parent) at a uniform rate of $1$ second per hop.

CODE

Example Tree:
       1
     /   \
    2     3
   /     / \
  4     5   6
   \
    7

If we ignite Node 2:
- Time 0: Node 2 ignites.
- Time 1: Neighbors of Node 2 ignite (Parent: 1, Left Child: 4).
- Time 2: Neighbors of 1 and 4 ignite (Node 3 via Node 1; Node 7 via Node 4).
- Time 3: Neighbors of 3 ignite (Nodes 5 and 6).
- Total Minimum Time = 3 seconds.

2. Real-Life Mental Model & Analogy

Real-Life Analogy: Imagine dropping a spark into a complex system of interconnected rooms or fuse wires. Fire does not care whether a room is upstairs, downstairs, or sideways; it radiates outward simultaneously in all available directions (left, right, and up through the ceiling/parent).

Because standard binary tree nodes only contain pointers pointing downward (left and right), fire can easily travel down, but it hits a dead end when trying to travel up toward the parent node. To fix this, we must first map all upward pathways.

3. Why DFS Fails (And Why BFS is Mandatory)

A Depth-First Search (DFS) explores a tree by diving deep down a single branch before backtracking.

The Flaw of DFS: Fire burns all adjacent nodes simultaneously at each time step (level-by-level propagation). DFS would simulate burning an entire branch completely to the bottom before exploring sibling branches, which distorts the timeline.
The Power of BFS: Breadth-First Search naturally processes nodes level by level (radially outwards). This perfectly models wave propagation and simultaneous burning across adjacent nodes (left, right, and parent).

4. Two-Phase Algorithm Architecture

To solve this problem cleanly, the algorithm is split into two distinct phases:

Phase 1: Parent Mapping & Target Location
- Perform a level-order traversal (BFS) starting from the root.
- During traversal, record every node's parent pointer in a hash map (parent_map).
- Simultaneously check if the current node matches our target value (start), and capture its exact memory address.
Phase 2: Radial Wave Propagation (The Burning BFS)
- Initialize a queue with the target node and mark it as visited.
- Run a level-order traversal simulating the fire spreading to three directions: Left Child, Right Child, and Parent.
- Increment our timer by $1$ unit for every wave level that successfully burns at least one unvisited adjacent node.

5. Step-by-Step Flow Walkthrough

Let's trace the execution steps for burning the tree starting from Node 2.

Phase 1: Mapping Parents via Level-Order Traversal

Queue starts with [1]. We pop 1, record its children (2 and 3), and map their parents:

parent_map[2] = 1
parent_map[3] = 1

Next, we process 2 and 3:

parent_map[4] = 2
parent_map[5] = 3
parent_map[6] = 3

Next, we process 4, 5, 6:

parent_map[7] = 4

Now our parent_map is fully established, and we have isolated the memory address of Node 2.

Phase 2: Radial Wave Simulation

Time = 0:
- Queue: [2]
- Visited set: {2}
- Check neighbors of 2:
  - Parent (1): Not visited -> Burn 1, push to queue, mark visited.
  - Left (4): Not visited -> Burn 4, push to queue, mark visited.
  - Right (null): None.
- Since at least one node was burned, timer increments to 1.
Time = 1:
- Queue: [1, 4] (Nodes burned at time 1)
- Process Node 1:
  - Parent: None.
  - Left (2): Already visited.
  - Right (3): Not visited -> Burn 3, push to queue, mark visited.
- Process Node 4:
  - Parent (2): Already visited.
  - Left (null): None.
  - Right (7): Not visited -> Burn 7, push to queue, mark visited.
- Since new nodes were burned, timer increments to 2.
Time = 2:
- Queue: [3, 7]
- Process Node 3:
  - Parent (1): Already visited.
  - Left (5): Burn 5, push to queue, mark visited.
  - Right (6): Burn 6, push to queue, mark visited.
- Process Node 7:
  - Parent (4): Already visited.
  - Children: None.
- Since new nodes (5, 6) were burned, timer increments to 3.
Time = 3:
- Queue: [5, 6]
- Process Node 5 and Node 6: All adjacent nodes (parents and children) are already visited or nonexistent. No new nodes burn.
- timer does not increment.
Queue becomes empty. Final Minimum Time = 3 seconds.

6. Complete C++ & Java Implementation

C++ Implementation

C++

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    // Helper BFS to map parents and locate target node address
    TreeNode* bfsToMapParents(TreeNode* root, int start, unordered_map<TreeNode*, TreeNode*>& parent_map) {
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* targetNode = nullptr;

        while (!q.empty()) {
            TreeNode* current = q.front();
            q.pop();

            if (current->val == start) {
                targetNode = current;
            }

            if (current->left) {
                parent_map[current->left] = current;
                q.push(current->left);
            }
            if (current->right) {
                parent_map[current->right] = current;
                q.push(current->right);
            }
        }
        return targetNode;
    }

public:
    int amountOfTime(TreeNode* root, int start) {
        unordered_map<TreeNode*, TreeNode*> parent_map;
        TreeNode* target = bfsToMapParents(root, start, parent_map);

        if (!target) return 0;

        unordered_map<TreeNode*, int> visited;
        queue<TreeNode*> q;

        q.push(target);
        visited[target] = 1;

        int elapsedTime = 0;

        while (!q.empty()) {
            int size = q.size();
            bool burnedNewNode = false;

            for (int i = 0; i < size; i++) {
                TreeNode* current = q.front();
                q.pop();

                // Check Left Child
                if (current->left && !visited[current->left]) {
                    burnedNewNode = true;
                    visited[current->left] = 1;
                    q.push(current->left);
                }

                // Check Right Child
                if (current->right && !visited[current->right]) {
                    burnedNewNode = true;
                    visited[current->right] = 1;
                    q.push(current->right);
                }

                // Check Parent Pointer
                if (parent_map.count(current) && !visited[parent_map[current]]) {
                    burnedNewNode = true;
                    visited[parent_map[current]] = 1;
                    q.push(parent_map[current]);
                }
            }

            if (burnedNewNode) {
                elapsedTime++;
            }
        }

        return elapsedTime;
    }
};

Java Implementation

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    
    // Helper BFS to map parents and return target node reference
    private TreeNode bfsToMapParents(TreeNode root, int start, Map<TreeNode, TreeNode> parentMap) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        TreeNode targetNode = null;

        while (!q.isEmpty()) {
            TreeNode current = q.poll();

            if (current.val == start) {
                targetNode = current;
            }

            if (current.left != null) {
                parentMap.put(current.left, current);
                q.offer(current.left);
            }
            if (current.right != null) {
                parentMap.put(current.right, current);
                q.offer(current.right);
            }
        }
        return targetNode;
    }

    public int amountOfTime(TreeNode root, int start) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        TreeNode target = bfsToMapParents(root, start, parentMap);

        if (target == null) return 0;

        Map<TreeNode, Integer> visited = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();

        q.offer(target);
        visited.put(target, 1);

        int elapsedTime = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            boolean burnedNewNode = false;

            for (int i = 0; i < size; i++) {
                TreeNode current = q.poll();

                // Check Left Child
                if (current.left != null && !visited.containsKey(current.left)) {
                    burnedNewNode = true;
                    visited.put(current.left, 1);
                    q.offer(current.left);
                }

                // Check Right Child
                if (current.right != null && !visited.containsKey(current.right)) {
                    burnedNewNode = true;
                    visited.put(current.right, 1);
                    q.offer(current.right);
                }

                // Check Parent
                TreeNode parent = parentMap.get(current);
                if (parent != null && !visited.containsKey(parent)) {
                    burnedNewNode = true;
                    visited.put(parent, 1);
                    q.offer(parent);
                }
            }

            if (burnedNewNode) {
                elapsedTime++;
            }
        }

        return elapsedTime;
    }
}

7. Complexity Analysis

Analysis Type	Complexity	Rationale
Time Complexity	$O(N)$	We traverse every node once during the parent-mapping BFS, and visit each node and edge once during the burning BFS. (Assuming hash map insertions/lookups take $O(1)$ average time).
Space Complexity	$O(N)$	The queue, `visited` hash map, and `parent_map` each store references to up to $N$ nodes in the binary tree.

Summary and Key Takeaways

Problem Nature: Finding the minimum burn time requires simulating radial wave expansion, making Breadth-First Search (BFS) mandatory over DFS.
Upward Traversal Limitation: Standard binary trees lack upward pointers; hence, Phase 1 must construct a hash-based parent_map via level-order traversal.
Simultaneous Propagation: At each time tick ( $t$ ), the algorithm processes all nodes burning at that exact level simultaneously.
Three-Direction Check: When expanding from any node, always inspect Left Child, Right Child, and Parent (provided they exist and have not been visited).
Timer Increments: The timer increments only when a wave successfully ignites at least one unvisited neighboring node.
Scalability: The approach generalizes effortlessly whether the ignition starts from an internal node, root node, or leaf node.