Start practising

Amount of Time for Binary Tree to Be Infected

Medium Trees & BST Child + Ancestor Handling Original on LeetCode

Amount of Time for Binary Tree to Be Infected is a medium trees & bst problem solved with the child + ancestor handling pattern. The best approach, one dfs (depth to start + max depth), runs in O(n) time and O(h) space. Below are 2 approaches in Java, from parent map + bfs up.

Problem

At minute 0, the node with value start becomes infected. Each minute, infection spreads from every infected node to its adjacent nodes (children and parent). Return how many minutes it takes to infect the whole tree.

Examples

Example 1

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

Example 2

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

Constraints

  • The tree has 1 to 10^5 nodes, unique values; start exists.
  • Infection spreads to parent and children each minute.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Parent map + BFSO(n)O(n)
One DFS (depth to start + max depth)O(n)O(h)

1Parent map + BFS

TimeO(n)
SpaceO(n)

Turn the tree into an undirected graph by recording each node's parent. Then BFS from the start node, level by level. The number of levels minus one is the answer.

  1. DFS to build parent[child] = node and find the start node.
  2. BFS from start over left, right and parent, skipping visited nodes.
  3. Count the minutes (levels).
Java
class Solution {
    public int amountOfTime(TreeNode root, int start) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        TreeNode src = null;
        Deque<TreeNode> st = new ArrayDeque<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode n = st.pop();
            if (n.val == start) src = n;
            if (n.left != null) { parent.put(n.left, n); st.push(n.left); }
            if (n.right != null) { parent.put(n.right, n); st.push(n.right); }
        }
        Set<TreeNode> seen = new HashSet<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(src);
        seen.add(src);
        int minutes = -1;
        while (!q.isEmpty()) {
            minutes++;
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                for (TreeNode nb : new TreeNode[] { n.left, n.right, parent.get(n) })
                    if (nb != null && seen.add(nb)) q.add(nb);
            }
        }
        return minutes;
    }
}

2One DFS (depth to start + max depth)

TimeO(n)
SpaceO(h)No parent map; only the recursion stack.

Postorder DFS returns the depth of each subtree, but returns a negative number when the subtree contains start (−distance to start). At each ancestor on the path to start, the farthest node through it is distance-to-start plus the depth of its other subtree. Take the maximum.

  1. At start: record the max depth below it; return -1.
  2. If one side returned negative d: answer = max(answer, |d| + depth of the other side); return d - 1.
  3. Otherwise return 1 + max(left, right).
Java
class Solution {
    private int best = 0;

    public int amountOfTime(TreeNode root, int start) {
        dfs(root, start);
        return best;
    }

    // returns the subtree height if it does not contain start,
    // otherwise -(distance from this node to start)
    private int dfs(TreeNode n, int start) {
        if (n == null) return 0;
        int l = dfs(n.left, start), r = dfs(n.right, start);
        if (n.val == start) {
            best = Math.max(best, Math.max(l, r));
            return -1;
        }
        if (l >= 0 && r >= 0) return 1 + Math.max(l, r);
        int dist = -Math.min(l, r);             // distance from n to start
        int other = l >= 0 ? l : r;             // height of the side without start
        best = Math.max(best, dist + other);
        return -(dist + 1);
    }
}

Edge cases to test

  • start is the root
  • start is a leaf deep in the tree

Hints

Hint 1

Children are easy to reach, but the parent is not. Record each node's parent (or build a graph), then BFS from start.

FAQ

What is the best time complexity for Amount of Time for Binary Tree to Be Infected?

One DFS (depth to start + max depth) runs in O(n) time and O(h) extra space.

Which pattern does Amount of Time for Binary Tree to Be Infected use?

It is a trees & bst problem that uses the child + ancestor handling pattern. Other problems with the same pattern: Burning Tree, All Nodes Distance K in Binary Tree.

Is there a brute force solution for Amount of Time for Binary Tree to Be Infected?

Yes. Parent map + BFS takes O(n) time and O(n) space. Turn the tree into an undirected graph by recording each node's parent.

Which edge cases should I test for Amount of Time for Binary Tree to Be Infected?

start is the root; start is a leaf deep in the tree.