How long until the whole tree is infected
Every value in the binary tree is different. At minute 0 only the node holding start is infected. Each minute, every infected node infects its neighbours: its left child, its right child and its parent.
Return how many minutes pass until every node is infected.
- Input
root = [7,2,9,4,null,null,1,8]
start = 9- Output
4
Minute 1: 7 and 1. Minute 2: 2. Minute 3: 4. Minute 4: 8, the last one, reached through the root.
- Input
root = [6]
start = 6- Output
0
The only node is infected at the start.
Limits
1 <= number of nodes <= 200001 <= Node.val <= 100000all values are differentstart is the value of a node in the treethe tree is at most 3000 levels deep
Hints
Hint 1
The infection also moves up to parents, so treat the tree as a graph with edges both ways.
Hint 2
Record each node's parent in one pass, then search breadth-first from the starting node. The answer is the distance to the farthest node.
Where this was reported
- Amazon, SDE-1 fresher video interview, 2025 (LeetCode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
