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.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^51 <= Node.val <= 10^5all node values are distincta node with value start exists in the tree
Hints for Amount of Time for Binary Tree to Be Infected
Hint 1
The infection spreads to parents as well as children, so treat the tree as an undirected graph.
Hint 2
A node gets infected at a minute equal to its distance from the start node. The answer is the largest distance.
Hint 3
Record each node's neighbours (parent and children) by value in one walk, then run a breadth-first search from
startand 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
- Walk the tree once, recording for every value the values of its parent and children (its neighbours).
- Run a breadth-first search from
start, one level per minute, marking values as visited. - 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 minutesJava
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)