☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Minimum time taken to burn the BT from a given Node

Hard TUF ID 120 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree and a start node in it. At time 0 the start node catches fire. Every second, the fire spreads from each burning node to all its neighbours: its left child, its right child, and its parent. Return the number of seconds until every node is burning.

Since the fire moves one edge per second in every direction at once, a node catches fire at the time equal to its distance from start. The answer is therefore the largest distance from start to any node. LeetCode’s “Amount of Time for Binary Tree to Be Infected” is the same problem with an infection instead of a fire.

Constraints (LeetCode): up to 10^5 nodes, values distinct, start exists. The Java methods return -1 if start is not in the tree.

Example 1

          1
        /   \
       2     3
      / \     \
     4   5     6
        / \     \
       7   8     10

start = 8   ->  6

Second 1: 5. Second 2: 2 and 7. Second 3: 1 and 4. Second 4: 3. Second 5: 6. Second 6: 10. The farthest node, 10, is six edges away.

Example 2

Same tree, start = 1. Nothing is above the root, so the fire only travels down. The deepest nodes, 7, 8, and 10, are three edges away, so the answer is 3.

Approach 1: Brute force, distances from root paths

Intuition. We need the maximum of dist(start, v) over all nodes v. The distance between two nodes passes through their lowest common ancestor, which is the last node shared by their root paths. If the root paths have a and b nodes and share common of them, the distance is a + b - 2 * common. Recording every node’s root path in one DFS lets us compute every distance.

Algorithm.

  1. DFS from the root with a shared path; store a copy of the path for every node.
  2. Let ps be the path of start.
  3. For every node’s path pv, count the shared prefix and compute the distance.
  4. Return the largest distance.
static int bruteForce(TreeNode root, TreeNode start) {
    Map<TreeNode, List<TreeNode>> pathOf = new HashMap<>();
    collectPaths(root, new ArrayList<>(), pathOf);
    List<TreeNode> ps = pathOf.get(start);
    if (ps == null) return -1;                                // start is not in the tree
    int worst = 0;
    for (List<TreeNode> pv : pathOf.values()) {
        int common = 0;                                       // nodes shared by both root paths
        while (common < ps.size() && common < pv.size() && ps.get(common) == pv.get(common)) common++;
        worst = Math.max(worst, ps.size() + pv.size() - 2 * common);
    }
    return worst;
}

static void collectPaths(TreeNode node, List<TreeNode> path, Map<TreeNode, List<TreeNode>> pathOf) {
    if (node == null) return;
    path.add(node);
    pathOf.put(node, new ArrayList<>(path));
    collectPaths(node.left, path, pathOf);
    collectPaths(node.right, path, pathOf);
    path.remove(path.size() - 1);
}

Complexity. Time O(n * h) and space O(n * h): each stored path has up to h entries. For a chain of 10^5 nodes that is 5 × 10^9 steps, far too slow.

Approach 2: Parent pointers and a level-by-level BFS

Intuition. Simulate the fire. The difficulty is that a tree only links downward, while fire also climbs to the parent. Record every node’s parent first; then each node has up to three neighbours and the tree behaves like an undirected graph. A BFS from start, processed one level at a time, is exactly the fire: the nodes in round t are the ones that catch fire at second t.

Count the rounds in which at least one new node caught fire. A burnt set (the BFS visited set) keeps the fire from “re-burning” the node it came from.

Algorithm.

  1. DFS once to fill parent[node].
  2. Queue start and mark it burnt. Set time = 0.
  3. While the queue is not empty: pop the whole current level; push every unburnt neighbour among left, right, parent. If anything new was pushed, time++.
  4. Return time.
static int parentMapBfs(TreeNode root, TreeNode start) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    fillParents(root, null, parent);
    if (!parent.containsKey(start)) return -1;
    Set<TreeNode> burnt = new HashSet<>();
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(start);
    burnt.add(start);
    int time = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        boolean spread = false;                               // did this second set any new node on fire?
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            for (TreeNode next : new TreeNode[]{node.left, node.right, parent.get(node)}) {
                if (next != null && burnt.add(next)) {
                    q.add(next);
                    spread = true;
                }
            }
        }
        if (spread) time++;
    }
    return time;
}

static void fillParents(TreeNode node, TreeNode par, Map<TreeNode, TreeNode> parent) {
    if (node == null) return;
    parent.put(node, par);
    fillParents(node.left, node, parent);
    fillParents(node.right, node, parent);
}

Complexity. Time O(n): each node is burnt once and examines three neighbours. Space O(n) for the map, the set, and the queue.

Approach 3: Optimal space, one post-order DFS

Intuition. We can find the farthest node without a parent map by thinking about where the path from start to a node turns.

The answer is the largest of these candidates. A single post-order DFS can produce them all if each call returns two numbers: the height of its subtree, and the distance from the current node down to start (or -1 if start is not below). A parent learns from whichever child returned a non-negative distance that start is on that side, adds one edge for itself, and pairs that distance with the height of the other child.

Algorithm.

  1. burnDfs(null) returns {0, -1}.
  2. Recurse into both children; height = 1 + max(left height, right height).
  3. If the node is start: candidate height - 1; return {height, 0}.
  4. If the left child reported distance l >= 0: d = l + 1, candidate d + right height; return {height, d}.
  5. Symmetric for the right child. Otherwise return {height, -1}.
static int optimal(TreeNode root, TreeNode start) {
    int[] best = new int[1];
    int[] top = burnDfs(root, start, best);
    return top[1] >= 0 ? best[0] : -1;                        // -1 when start was never found
}

/** Returns {height, dist}: the subtree height in nodes, and the distance from node down to start (-1 if start is not below). */
static int[] burnDfs(TreeNode node, TreeNode start, int[] best) {
    if (node == null) return new int[]{0, -1};
    int[] l = burnDfs(node.left, start, best);
    int[] r = burnDfs(node.right, start, best);
    int height = 1 + Math.max(l[0], r[0]);
    if (node == start) {
        best[0] = Math.max(best[0], height - 1);              // fire spreading straight down from start
        return new int[]{height, 0};
    }
    if (l[1] >= 0) {                                          // start is in the left subtree
        int d = l[1] + 1;
        best[0] = Math.max(best[0], d + r[0]);                // up to node, then down the right side
        return new int[]{height, d};
    }
    if (r[1] >= 0) {                                          // start is in the right subtree
        int d = r[1] + 1;
        best[0] = Math.max(best[0], d + l[0]);
        return new int[]{height, d};
    }
    return new int[]{height, -1};
}

Dry run on Example 1 (start = 8), in post-order:

node left result right result candidate returns
4 {0, -1} {0, -1}   {1, -1}
7 {0, -1} {0, -1}   {1, -1}
8 (start) {0, -1} {0, -1} 1 - 1 = 0 {1, 0}
5 {1, -1} {1, 0} d = 1, 1 + 1 = 2 {2, 1}
2 {1, -1} {2, 1} d = 2, 2 + 1 = 3 {3, 2}
10, 6, 3       heights 1, 2, 3, no start
1 {3, 2} {3, -1} d = 3, 3 + 3 = 6 {4, 3}

The best candidate is 6.

Complexity. Time O(n): one visit per node. Space O(h) for the recursion; no map or set is needed.

Edge cases and pitfalls