Amount of Time for Binary Tree to Be Infected
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Hash Table · Binary Tree
Problem
You are given the root of a binary tree with unique values and an integer start. At minute 0, the node whose value is start becomes infected.
Every minute, each uninfected node that is adjacent to an infected node (its parent or one of its children) becomes infected.
Return the number of minutes until the whole tree is infected.
Examples
Input: root = [1,2,3,4,5,None,6,None,None,7], start = 5 Output: 4
The farthest node from 5 is 6, reached through 2, 1 and 3 at minute 4.
Input: root = [9], start = 9 Output: 0
The only node is infected at minute 0.
Input: root = [1,2,3,None,4], start = 1 Output: 2
From the root, node 4 is two edges down, so the last node is infected at minute 2.
Constraints
- The number of nodes is in the range [1, 10^5]
- 1 <= Node.val <= 10^5
- All values are unique
- A node with value start exists in the tree
Approaches
- Simulate minute by minute — time O(n · T), space O(n)
Follow-up
Can you do it in one pass without a parent map? A post-order DFS can return each subtree’s depth and whether it holds the start node (and how far down). At the node where the path to the start meets another branch, the answer candidate is the distance to the start plus the depth of the other branch; the start’s own subtree depth is the other candidate. It uses O(h) space for the recursion instead of O(n) for the map.
Related problems
Start free on Cariara · Coding problems · System design studio
