We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Amount of Time for Binary Tree to Be Infected

Difficulty: Medium

Problem Description

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start. Each minute, a node becomes infected if it is currently uninfected and adjacent to an infected node. Return the number of minutes needed for the entire tree to be infected.

Key Insights

  • The infection spreads from the starting node to its adjacent nodes (parent and children).
  • We can represent the binary tree as a graph to facilitate traversal and infection spread.
  • BFS (Breadth-First Search) is an effective way to simulate the minute-by-minute infection spread.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, since we may need to visit every node once. Space Complexity: O(N), for storing the graph representation of the tree and the queue used in BFS.

Solution

To solve this problem, we can use the following approach:

  1. Graph Representation: Convert the binary tree into an undirected graph where each node is connected to its parent and children (if they exist).
  2. BFS Traversal: Start BFS from the node with the value equal to start. Keep track of the nodes that are already infected to avoid recounting.
  3. Count Minutes: For each level of BFS, increment a minute counter until all nodes are infected.

The BFS ensures that we can explore all nodes level by level, which corresponds to the minutes that pass in the infection process.

Code Solutions

from collections import defaultdict, deque

class Solution:
    def amountOfTime(self, root: TreeNode, start: int) -> int:
        # Step 1: Build the graph from the binary tree
        graph = defaultdict(list)
        
        def build_graph(node, parent):
            if node:
                if parent:
                    graph[node.val].append(parent.val)
                    graph[parent.val].append(node.val)
                build_graph(node.left, node)
                build_graph(node.right, node)
        
        build_graph(root, None)
        
        # Step 2: Perform BFS from the start node
        queue = deque([start])
        visited = set([start])
        minutes = 0
        
        while queue:
            for _ in range(len(queue)):
                current = queue.popleft()
                for neighbor in graph[current]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            # Increment the minutes after processing all nodes at the current level
            if queue:
                minutes += 1
        
        return minutes
← Back to All Questions