Amount of Time for Binary Tree to Be Infected

Medium
1957.

Amount of Time for Binary Tree to Be Infected

Amount of Time for Binary Tree to Be Infected is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

You are given the root of a binary tree whose node values are distinct, and an integer start. At minute 0 an infection starts at the node whose value is start.

Each minute, every uninfected node that is adjacent to an infected node (its parent or one of its children) becomes infected. Return the number of minutes needed for the whole tree to be infected.

Example 1

Input
root = [1,5,3,null,4,10,6,9,2], start = 3
Output
4
Explanation
Minute 1: 1, 10, 6. Minute 2: 5. Minute 3: 4. Minute 4: 9 and 2 — every node is infected.

Example 2

Input
root = [1], start = 1
Output
0
Explanation
The only node is infected from the start.

Example 3

Input
root = [1,2,null,3,null,4], start = 1
Output
3
Explanation
The infection walks down the chain one node a minute: 2, 3, then 4.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
  • a node with value start exists in the tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function(root, start) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Amount of Time for Binary Tree to Be Infected — Solution

Amount of Time for Binary Tree to Be Infected solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Amount of Time for Binary Tree to Be Infected is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given the root of a binary tree whose node values are distinct, and an integer start. At minute 0 an infection starts at the node whose value is start.

Each minute, every uninfected node that is adjacent to an infected node (its parent or one of its children) becomes infected. Return the number of minutes needed for the whole tree to be infected.

Example 1

Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: Minute 1: 1, 10, 6. Minute 2: 5. Minute 3: 4. Minute 4: 9 and 2 — every node is infected.

Example 2

Input: root = [1], start = 1
Output: 0
Explanation: The only node is infected from the start.

Example 3

Input: root = [1,2,null,3,null,4], start = 1
Output: 3
Explanation: The infection walks down the chain one node a minute: 2, 3, then 4.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
  • a node with value start exists in the tree

Hints for Amount of Time for Binary Tree to Be Infected

  1. Hint 1

    The infection spreads to parents as well as children, so treat the tree as an undirected graph.

  2. Hint 2

    A node gets infected at a minute equal to its distance from the start node. The answer is the largest distance.

  3. Hint 3

    Record each node's neighbours (parent and children) by value in one walk, then run a breadth-first search from start and count its rounds.

How to solve Amount of Time for Binary Tree to Be Infected

The minute a node is infected is its graph distance from start, so the answer is the farthest distance — the number of rounds of a breadth-first search from start over the tree with parent links added.

Approach

  1. Walk the tree once, recording for every value the values of its parent and children (its neighbours).
  2. Run a breadth-first search from start, one level per minute, marking values as visited.
  3. Count the levels after the first; that count is the answer.

Why it works

Each minute the infected set grows by exactly the uninfected neighbours of the infected set, which is what one breadth-first level adds. So level d of the search is the set infected at minute d, and the last non-empty level is the last minute anything changes.

Complexity

  • Time — O(n)
  • Space — O(n) for the adjacency and the queue

Pitfalls

  • Following only child pointers misses the spread upwards through the parent.
  • Count minutes, not nodes: the start alone is minute 0.

Reference solution

Python

from typing import Optional
from collections import defaultdict

def amountOfTime(root: Optional[TreeNode], start: int) -> int:
    adj = defaultdict(list)
    stack = [root]
    while stack:
        node = stack.pop()
        for child in (node.left, node.right):
            if child:
                adj[node.val].append(child.val)
                adj[child.val].append(node.val)
                stack.append(child)
    seen = {start}
    level = [start]
    minutes = -1
    while level:
        minutes += 1
        nxt = []
        for u in level:
            for w in adj[u]:
                if w not in seen:
                    seen.add(w)
                    nxt.append(w)
        level = nxt
    return minutes

Java

public static int amountOfTime(TreeNode root, int start) {
    Map<Integer, List<Integer>> adj = new HashMap<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        for (TreeNode child : new TreeNode[] {node.left, node.right}) {
            if (child == null) continue;
            adj.computeIfAbsent(node.val, k -> new ArrayList<>()).add(child.val);
            adj.computeIfAbsent(child.val, k -> new ArrayList<>()).add(node.val);
            stack.push(child);
        }
    }
    Set<Integer> seen = new HashSet<>();
    seen.add(start);
    List<Integer> level = new ArrayList<>();
    level.add(start);
    int minutes = -1;
    while (!level.isEmpty()) {
        minutes++;
        List<Integer> next = new ArrayList<>();
        for (int u : level) {
            for (int w : adj.getOrDefault(u, Collections.emptyList())) {
                if (seen.add(w)) next.add(w);
            }
        }
        level = next;
    }
    return minutes;
}

C++

int amountOfTime(TreeNode* root, int start) {
    unordered_map<int, vector<int>> adj;
    vector<TreeNode*> stack{root};
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        for (TreeNode* child : {node->left, node->right}) {
            if (!child) continue;
            adj[node->val].push_back(child->val);
            adj[child->val].push_back(node->val);
            stack.push_back(child);
        }
    }
    unordered_set<int> seen{start};
    vector<int> level{start};
    int minutes = -1;
    while (!level.empty()) {
        minutes++;
        vector<int> next;
        for (int u : level)
            for (int w : adj[u])
                if (seen.insert(w).second) next.push_back(w);
        level.swap(next);
    }
    return minutes;
}

JavaScript

var amountOfTime = function(root, start) {
    var adj = new Map();
    var link = function(a, b) {
        if (!adj.has(a)) adj.set(a, []);
        if (!adj.has(b)) adj.set(b, []);
        adj.get(a).push(b);
        adj.get(b).push(a);
    };
    var stack = [root];
    while (stack.length > 0) {
        var node = stack.pop();
        if (node.left !== null) { link(node.val, node.left.val); stack.push(node.left); }
        if (node.right !== null) { link(node.val, node.right.val); stack.push(node.right); }
    }
    var seen = new Set([start]), level = [start], minutes = -1;
    while (level.length > 0) {
        minutes++;
        var next = [];
        for (var i = 0; i < level.length; i++) {
            var ns = adj.get(level[i]) || [];
            for (var j = 0; j < ns.length; j++) {
                if (!seen.has(ns[j])) { seen.add(ns[j]); next.push(ns[j]); }
            }
        }
        level = next;
    }
    return minutes;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)