Practice/Microsoft/Leetcode 2385. Amount of Time for Binary Tree to Be Infected

Leetcode 2385. Amount of Time for Binary Tree to Be Infected

CodingOptional

Problem

You are modeling the spread of a virus through a network represented as a binary tree. Each node in the tree represents a computer in the network. When a computer becomes infected, it spreads the virus to all directly connected computers (its parent and both children, if they exist) in exactly one minute.

Given the root of a binary tree and the value of the initially infected node (start), determine how many minutes it will take for every computer in the network to become infected.

Requirements

1. Calculate the minimum time required for the virus to spread to all nodes in the tree
2. The virus spreads simultaneously to all adjacent nodes (parent and children) each minute
3. Return the total number of minutes needed for complete infection
4. The tree is treated as an undirected graph where edges exist between parent-child pairs

Constraints

• The number of nodes in the tree is in the range [1, 10^5]
• Each node has a unique value in the range [1, 10^5]
• The start value is guaranteed to exist in the tree
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(n) for auxiliary data structures

Examples

Example 1:

Input: root = [1,2,3,4,5], start = 2 Output: 2 Explanation: Minute 0: Node 2 is infected Minute 1: Nodes 1, 4, and 5 become infected (adjacent to node 2) Minute 2: Node 3 becomes infected (adjacent to node 1) Total time: 2 minutes

Example 2:

Input: root = [1], start = 1 Output: 0 Explanation: The tree has only one node which is already infected at the start.

Example 3:

Input: root = [1,2,3,4,5,6,7], start = 7 Output: 3 Explanation: Minute 0: Node 7 is infected Minute 1: Node 3 becomes infected Minute 2: Nodes 1 and 6 become infected Minute 3: Nodes 2, 4, and 5 become infected Total time: 3 minutes