Amount of Time for Binary Tree to Be Infected — LeetCode 2385 Multi-Source BFS

Problem Statement#

You are given the root of a binary tree with unique values and an integer start. At minute 0, an infection starts from the node with value start. Each minute, a neighbor (parent or child) of an already-infected node becomes infected. Return the number of minutes until every node is infected.

Constraints:

• The number of nodes in the tree is in the range [1, 10^5]
• 1 <= Node.val <= 10^5
• All node values are unique
• start exists in the tree

Input:  root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4

Input:  root = [1], start = 1
Output: 0

Why This Problem Matters#

LeetCode 2385 — Amount of Time for a Binary Tree to Be Infected — is a high-frequency Amazon, Google, and Meta interview question that tests whether candidates can recognize when to convert a tree into an undirected graph. The infection moves both up and down, which means tree-only DFS won't suffice — you need a graph BFS (or a clever tree-DP variant).

This is essentially LC 863 All Nodes Distance K in a Binary Tree with the answer being the maximum distance from the start. Companies use it because it forces three skills at once: tree traversal, graph construction, and BFS for shortest distances. It also appears in real systems: epidemic modeling, network failure propagation, and CDN cache-invalidation cascades.

The Core Insight#

The infection spreads in three directions from any node: left child, right child, and parent. That bidirectional motion is the signature of a graph problem, not a tree problem. Build an adjacency list by walking the tree once, then run a BFS from the start node and return the maximum distance reached.

Alternative tree-DP approach: at each node, track depth of infection inside the subtree and propagate up; this avoids the explicit graph but is harder to debug. The BFS solution is the canonical interview answer.

Visual Dry Run#

Tree [1, 5, 3, null, 4, 10, 6, 9, 2], start = 3:

Total: 4 minutes.

Solution (Optimal)#

from collections import defaultdict, deque
from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        graph = defaultdict(list)
 
        def build(node: Optional[TreeNode], parent: Optional[int]) -> None:
            if node is None:
                return
            if parent is not None:
                graph[node.val].append(parent)
                graph[parent].append(node.val)
            build(node.left, node.val)
            build(node.right, node.val)
 
        build(root, None)
 
        visited = {start}
        queue = deque([(start, 0)])
        max_minute = 0
        while queue:
            val, minute = queue.popleft()
            max_minute = max(max_minute, minute)
            for nei in graph[val]:
                if nei not in visited:
                    visited.add(nei)
                    queue.append((nei, minute + 1))
        return max_minute

var amountOfTime = function(root, start) {
    const graph = new Map();
    const addEdge = (a, b) => {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a).push(b);
    };
    const build = (node, parent) => {
        if (!node) return;
        if (parent !== null) {
            addEdge(node.val, parent);
            addEdge(parent, node.val);
        }
        build(node.left, node.val);
        build(node.right, node.val);
    };
    build(root, null);
 
    const visited = new Set([start]);
    const queue = [[start, 0]];
    let maxMinute = 0;
    while (queue.length > 0) {
        const [val, minute] = queue.shift();
        if (minute > maxMinute) maxMinute = minute;
        for (const nei of (graph.get(val) || [])) {
            if (!visited.has(nei)) {
                visited.add(nei);
                queue.push([nei, minute + 1]);
            }
        }
    }
    return maxMinute;
};

Time: O(n) — each node is visited once for graph build, once for BFS. Space: O(n) — adjacency list, visited set, queue.

Common Mistakes#

• Doing tree-only DFS from the start, missing the upward propagation through the parent.
• Using node references as graph keys instead of unique values; works but the values in this problem are guaranteed unique, so values are simpler.
• Forgetting to mark the start node visited before BFS, leading to revisits.
• Initializing max_minute = -1 and returning negative for trees with one node.
• Recursion depth: with n = 10^5, deeply skewed trees will blow Python's default 1000 limit. Consider iterative graph build.

Interview Tips#

• State explicitly that the infection spreads in three directions; this signals graph BFS.
• Mention LC 863 as the cousin problem that asks for nodes at exact distance K rather than the max.
• Sketch a 5-node tree, mark start, and animate the BFS by minute.
• Discuss the tree-DP alternative briefly — show range, but ship the BFS.

Follow-up Questions#

• "What if the start node may not exist?" — Validate with a hash set during build.
• "Multiple start nodes" — Multi-source BFS, push all starts at minute 0.
• "Different infection speed for parent vs. child edges" — Add weights, switch to Dijkstra.
• "Reverse: find the start that minimizes max infection time" — Tree center problem, related to LC 310 Minimum Height Trees.
• "Streaming infection events" — Online BFS layer-by-layer.

Key Takeaways#

• LeetCode 2385 Amount of Time for Binary Tree to Be Infected becomes a graph BFS once you see infection spreads via parent and children.
• Build an undirected adjacency list keyed by node value, then BFS from start.
• Time and space are O(n).
• The answer is the max distance from start in the resulting graph — same as LC 863's deepest distance.
• BFS is preferred over the tree-DP variant for clarity in interviews.
• Frequent at Amazon, Google, and Meta as a tree-to-graph conversion test.
• Generalizes to epidemic modeling, fault propagation, and cache-invalidation cascades.