2385 · Amount of Time for Binary Tree to Be Infected

The same trick as distance-K (863), pointed at a different question: instead of "which nodes are exactly K away", this asks "how far away is the furthest node from the start" — the eccentricity of one node in the tree, treated as a graph.

1 — The problem

An infection starts at a given node and spreads to every directly connected node — left child, right child, and parent — once per minute. Return the total number of minutes until every node in the tree is infected. That's exactly the BFS-as-graph technique from 863, run to completion instead of stopped at a fixed depth: the answer is simply the depth of the last node the BFS reaches.

Framed in graph terms: infection time = the eccentricity of the start node = the length of the longest shortest-path from it to any other node. Nothing about "infection" changes the mechanics — it's the same parent-map-then-BFS shape as 863, just asking for max(depth) over the whole run instead of the frontier at one specific depth.

2 — Visualizing the spread

Map<TreeNode, TreeNode> parent = new HashMap<>();buildParentMap(root, null, parent);Set<TreeNode> infected = new HashSet<>();Queue<TreeNode> frontier = new LinkedList<>();frontier.add(start); infected.add(start);int minutes = 0;while (!frontier.isEmpty()) {    boolean spread = false;    int sz = frontier.size();    for (int i = 0; i < sz; i++) {        TreeNode nd = frontier.poll();        for (TreeNode nb : List.of(nd.left, nd.right, parent.get(nd))) {            if (nb != null && infected.add(nb)) { frontier.add(nb); spread = true; }        }    }    if (spread) minutes++;}

The clock only advances on a minute that actually infects someone new — the spread flag exists so the final, empty round (where the frontier drains without reaching anyone) doesn't count an extra minute. Watch the last two nodes to catch fire, 9 and 2: they're the furthest from node 3, reached only after climbing all the way up to the root and back down the other side.

3 — Complexity and edge cases

• Time: O(n) — building the parent map and running the BFS are each a single pass over every node.
• Space: O(n) for the parent map, the infected set and the queue.
• Single-node tree: 0 minutes — the frontier starts and ends at just the start node, nothing ever spreads.
• Start node is a leaf far from the root: no special handling needed; the parent map lets the BFS climb toward the root exactly like descending into any child.
• Off-by-one to watch for: incrementing minutes unconditionally, every iteration of the outer while, over-counts by exactly one — the loop's very last pass typically finds no new neighbours and shouldn't count. The spread flag is the guard against that.

4 — Reference implementation

public int amountOfTime(TreeNode root, int start) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    TreeNode startNode = buildParentMap(root, null, start, parent);

    Set<TreeNode> infected = new HashSet<>();
    Queue<TreeNode> frontier = new LinkedList<>();
    frontier.add(startNode);
    infected.add(startNode);

    int minutes = 0;
    while (!frontier.isEmpty()) {
        boolean spread = false;
        int sz = frontier.size();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = frontier.poll();
            for (TreeNode nb : List.of(nd.left, nd.right, parent.get(nd))) {
                if (nb != null && infected.add(nb)) { frontier.add(nb); spread = true; }
            }
        }
        if (spread) minutes++;
    }
    return minutes;
}

private TreeNode buildParentMap(TreeNode nd, TreeNode par, int start, Map<TreeNode, TreeNode> parent) {
    if (nd == null) return null;
    parent.put(nd, par);
    TreeNode found = (nd.val == start) ? nd : null;
    if (found == null) found = buildParentMap(nd.left, nd, start, parent);
    if (found == null) found = buildParentMap(nd.right, nd, start, parent);
    return found;
}