Amount of Time for Binary Tree to Be Infected
Problem
Given the root of a binary tree with unique values and the value of a starting node, an infection begins at that node. Each minute the infection spreads from every infected node to all of its directly connected neighbors (its children and its parent) that are not yet infected. Return the number of minutes it takes for every node in the tree to become infected.
tree = [1,5,3,null,4,10,6,9,2], start = 34from collections import deque
def amountOfTime(root, start):
parent = {}
def dfs(node, par):
if not node: return
parent[node] = par
dfs(node.left, node); dfs(node.right, node)
dfs(root, None)
startNode = next(n for n in parent if n.val == start)
seen = {startNode}
q = deque([startNode])
minutes = -1
while q:
minutes += 1
for _ in range(len(q)):
cur = q.popleft()
for nb in (cur.left, cur.right, parent[cur]):
if nb and nb not in seen:
seen.add(nb); q.append(nb)
return minutesfunction amountOfTime(root, start) {
const parent = new Map();
(function dfs(node, par) {
if (!node) return;
parent.set(node, par);
dfs(node.left, node); dfs(node.right, node);
})(root, null);
let startNode = null;
for (const n of parent.keys()) if (n.val === start) startNode = n;
const seen = new Set([startNode]);
let q = [startNode], minutes = -1;
while (q.length) {
minutes++;
const next = [];
for (const cur of q) {
for (const nb of [cur.left, cur.right, parent.get(cur)]) {
if (nb && !seen.has(nb)) { seen.add(nb); next.push(nb); }
}
}
q = next;
}
return minutes;
}class Solution {
Map<TreeNode, TreeNode> parent = new HashMap<>();
TreeNode startNode = null;
public int amountOfTime(TreeNode root, int start) {
dfs(root, null, start);
Set<TreeNode> seen = new HashSet<>(); seen.add(startNode);
Deque<TreeNode> q = new ArrayDeque<>(); q.offer(startNode);
int minutes = -1;
while (!q.isEmpty()) {
minutes++;
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
for (TreeNode nb : new TreeNode[]{ cur.left, cur.right, parent.get(cur) }) {
if (nb != null && seen.add(nb)) q.offer(nb);
}
}
}
return minutes;
}
void dfs(TreeNode n, TreeNode p, int start) {
if (n == null) return;
parent.put(n, p);
if (n.val == start) startNode = n;
dfs(n.left, n, start); dfs(n.right, n, start);
}
}int amountOfTime(TreeNode* root, int start) {
unordered_map<TreeNode*, TreeNode*> parent;
TreeNode* startNode = nullptr;
function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* n, TreeNode* p) {
if (!n) return;
parent[n] = p;
if (n->val == start) startNode = n;
dfs(n->left, n); dfs(n->right, n);
};
dfs(root, nullptr);
unordered_set<TreeNode*> seen{startNode};
queue<TreeNode*> q; q.push(startNode);
int minutes = -1;
while (!q.empty()) {
minutes++;
int sz = (int)q.size();
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front(); q.pop();
for (TreeNode* nb : { cur->left, cur->right, parent[cur] }) {
if (nb && !seen.count(nb)) { seen.insert(nb); q.push(nb); }
}
}
}
return minutes;
}Explanation
An infection spreads in every direction — down to children but also up to the parent. A plain tree only lets you walk downward, so the first job is to turn the tree into an undirected graph where each node knows all three of its neighbors.
A single DFS builds a parent map: every node remembers who its parent is. Now from any node we can reach left, right, and parent — exactly the nodes the infection can jump to next.
The spread itself is a breadth-first search from the start node. BFS naturally moves outward one ring at a time, and one ring is exactly one minute of spreading. A seen set marks infected nodes so we never re-infect or loop back.
We count completed rings. Starting minutes at -1 handles the very first level (the start node itself, which costs no time): the loop bumps the counter to 0 while processing that level. When the queue finally empties, minutes equals the distance to the farthest node — the moment the last node is infected.
Example: start = 3. Minute 1 reaches 1, 10, 6. Minute 2 reaches 5 (and the rest below 3 are done). Minute 3 reaches 4. Minute 4 reaches 9 and 2, the deepest nodes — so the answer is 4.