Amount of Time for Binary Tree to Be Infected
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, Python, C++ and JavaScript, 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
1to10^5nodes, unique values; start exists. - Infection spreads to parent and children each minute.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Parent map + BFS | O(n) | O(n) |
| One DFS (depth to start + max depth) | O(n) | O(h) |
1Parent map + BFS
O(n)O(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.
- DFS to build parent[child] = node and find the start node.
- BFS from start over left, right and parent, skipping visited nodes.
- Count the minutes (levels).
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;
}
}class Solution:
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
parent: Dict[TreeNode, TreeNode] = {}
src = None
st = [root]
while st:
n = st.pop()
if n.val == start:
src = n
if n.left is not None:
parent[n.left] = n; st.append(n.left)
if n.right is not None:
parent[n.right] = n; st.append(n.right)
seen = {src}
q = deque([src])
minutes = -1
while q:
minutes += 1
for _ in range(len(q)):
n = q.popleft()
for nb in (n.left, n.right, parent.get(n)):
if nb is not None and nb not in seen:
seen.add(nb)
q.append(nb)
return minutesclass Solution {
public:
int amountOfTime(TreeNode* root, int start) {
unordered_map<TreeNode*, TreeNode*> parent;
TreeNode* src = nullptr;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* n = st.top(); st.pop();
if (n->val == start) src = n;
if (n->left != nullptr) { parent[n->left] = n; st.push(n->left); }
if (n->right != nullptr) { parent[n->right] = n; st.push(n->right); }
}
unordered_set<TreeNode*> seen;
queue<TreeNode*> q;
q.push(src);
seen.insert(src);
int minutes = -1;
while (!q.empty()) {
minutes++;
for (int i = q.size(); i > 0; i--) {
TreeNode* n = q.front(); q.pop();
TreeNode* par = parent.count(n) ? parent[n] : nullptr;
for (TreeNode* nb : { n->left, n->right, par })
if (nb != nullptr && seen.insert(nb).second) q.push(nb);
}
}
return minutes;
}
};function amountOfTime(root, start) {
const parent = new Map();
let src = null;
const st = [root];
while (st.length > 0) {
const n = st.pop();
if (n.val === start) src = n;
if (n.left !== null) { parent.set(n.left, n); st.push(n.left); }
if (n.right !== null) { parent.set(n.right, n); st.push(n.right); }
}
const seen = new Set();
let q = [src];
seen.add(src);
let minutes = -1;
while (q.length > 0) {
minutes++;
const next = [];
for (const n of q) {
for (const nb of [n.left, n.right, parent.get(n)])
if (nb != null && !seen.has(nb)) { seen.add(nb); next.push(nb); }
}
q = next;
}
return minutes;
}2One DFS (depth to start + max depth)
O(n)O(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.
- At start: record the max depth below it; return -1.
- If one side returned negative d: answer = max(answer, |d| + depth of the other side); return d - 1.
- Otherwise return 1 + max(left, right).
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);
}
}class Solution:
def __init__(self):
self.best = 0
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
self.dfs(root, start)
return self.best
# returns the subtree height if it does not contain start,
# otherwise -(distance from this node to start)
def dfs(self, n: Optional[TreeNode], start: int) -> int:
if n is None:
return 0
l, r = self.dfs(n.left, start), self.dfs(n.right, start)
if n.val == start:
self.best = max(self.best, max(l, r))
return -1
if l >= 0 and r >= 0:
return 1 + max(l, r)
dist = -min(l, r) # distance from n to start
other = l if l >= 0 else r # height of the side without start
self.best = max(self.best, dist + other)
return -(dist + 1)class Solution {
private:
int best = 0;
public:
int amountOfTime(TreeNode* root, int start) {
dfs(root, start);
return best;
}
private:
// returns the subtree height if it does not contain start,
// otherwise -(distance from this node to start)
int dfs(TreeNode* n, int start) {
if (n == nullptr) return 0;
int l = dfs(n->left, start), r = dfs(n->right, start);
if (n->val == start) {
best = max(best, max(l, r));
return -1;
}
if (l >= 0 && r >= 0) return 1 + max(l, r);
int dist = -min(l, r); // distance from n to start
int other = l >= 0 ? l : r; // height of the side without start
best = max(best, dist + other);
return -(dist + 1);
}
};function amountOfTime(root, start) {
let best = 0;
// returns the subtree height if it does not contain start,
// otherwise -(distance from this node to start)
function dfs(n) {
if (n === null) return 0;
const l = dfs(n.left), r = dfs(n.right);
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);
const dist = -Math.min(l, r); // distance from n to start
const other = l >= 0 ? l : r; // height of the side without start
best = Math.max(best, dist + other);
return -(dist + 1);
}
dfs(root);
return best;
}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, Count Good Nodes 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.