Amount Of Time For Binary Tree To Be Infected - Leetcode Solution

Problem Statement:

Given a binary tree, with a root node, and two leaf nodes infected with a virus. The virus spreads from an infected node to its parent node and all of its children nodes. Return the amount of time it takes for the entire binary tree to be infected.

Example:

Input:

     1
    / \
   2   3
  / \   \
 4   5   6

Infected nodes: 4, 6

Output: 3

Explanation:

At time 1, nodes 4 and 6 infect their parent nodes 2 and 3 respectively.

At time 2, nodes 2 and 3 infect their parent node 1.

At time 3, node 1 infects the remaining nodes 4, 5 and 6.

Solution:

We can solve this problem using a BFS (Breadth-First-Search) approach. We start by infecting the initial infected nodes (leaf nodes) and mark them as infected. We add these nodes to a queue and continue the BFS until the entire tree is infected.

At each level of the BFS, we mark the parent nodes of infected nodes as infected and add them to the queue. We continue this process until all the nodes in the tree are infected. We keep track of the level or time at each iteration, and return the final level as the amount of time taken for the entire tree to be infected.

Algorithm:

1. Create a queue and add the initial infected nodes to it.

2. Create a boolean array to mark infected nodes.

3. Initialize the time/level to 0.

4. While the queue is not empty, do the following:

   i. Increment the time/level.

   ii. Get the size of the queue.

   iii. Iterate through each node in the queue and do the following:

   a. Mark the node as infected in the boolean array.
   
   b. If the node has a parent node, mark the parent node as infected.
   
   c. If the node has children nodes, add them to the queue.
   

   iv. Clear the queue.

5. Return the time/level.

Time Complexity:

The time complexity of BFS is O(V+E), where V is the number of nodes in the tree and E is the number of edges. In the worst-case scenario, all the nodes in the tree need to be infected, so the time complexity is O(N), where N is the number of nodes in the tree.

Space Complexity:

The space complexity of BFS is O(V), where V is the number of nodes in the tree. In the worst-case scenario, all the nodes in the tree are in the queue, so the space complexity is O(N), where N is the number of nodes in the tree.

Implementation:

Here is the sample implementation code in Python:

from collections import deque

def minTimeToInfectTree(root, infected):
    if not root or not infected:
        return 0
    
    queue = deque(infected)
    infected_set = set(infected)
    time = 0
    
    while queue:
        time += 1
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            parent = node.parent
            
            if parent and parent not in infected_set:
                queue.append(parent)
                infected_set.add(parent)
                
            for child in node.children:
                if child not in infected_set:
                    queue.append(child)
                    infected_set.add(child)
                    
        queue.clear()
        
    return time

Here, root is the root node of the binary tree, and infected is the list of initial infected nodes. We use deque from collections module to implement the queue. We add infected nodes to the queue and mark them as infected in a set called infected_set. We also initialize the time/level to 0.

Using a while loop, we continue the BFS until the queue is empty. At each level, we iterate through all the nodes in the queue, marking them as infected, and adding their parent and children nodes to the queue if they are not already infected. We keep track of the level or time and return the final value.

Conclusion:

In this article, we have discussed the problem of finding the amount of time it takes for an entire binary tree to be infected by a virus. We have explained the BFS approach to solve this problem along with its time and space complexity. We have also provided the sample implementation code in Python.

1