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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Amount of Time for Binary Tree to Be Infected

Number: 2461

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, ServiceNow, Adobe, Flipkart, Bloomberg, PayPal, PhonePe, Uber, Apple, ShareChat

Problem Description

Given the root of a binary tree with unique node values and a starting value start, the infection begins at the node having value start at minute 0. Each minute, every uninfected node that is adjacent (either as a parent or a child) to an infected node becomes infected. The goal is to determine the total number of minutes required for the infection to spread to every node in the tree.

Key Insights

  • Convert the tree structure into an undirected graph. Each node is connected to its left child, right child, and parent.
  • Use depth-first search (DFS) to build the graph by traversing the tree.
  • Use breadth-first search (BFS) starting from the infected node (start) to compute the number of minutes (levels) needed to infect every node.
  • The maximum distance (in terms of levels in BFS) reached from the starting node equals the number of minutes required.

Space and Time Complexity

Time Complexity: O(n) – We traverse each node to build the graph and then each node is processed in the BFS. Space Complexity: O(n) – The graph and the auxiliary data structures (queue and visited set) store information for all nodes.

Solution

We first traverse the binary tree using DFS to build an adjacency list that represents the undirected graph. In this graph, each node's value points to a list of its adjacent node values (its parent and its children). After constructing the graph, we perform a BFS starting from the node corresponding to start. The BFS is performed level by level; each level represents one minute of infection spread. The maximum level encountered gives the number of minutes required to infect the entire tree.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import defaultdict, deque

class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        # Build an undirected graph from the binary tree.
        graph = defaultdict(list)
        
        # DFS function to populate the graph.
        def dfs(node, parent):
            if not node:
                return
            if parent:
                # Connect node with its parent.
                graph[node.val].append(parent.val)
                graph[parent.val].append(node.val)
            # Traverse left and right children.
            dfs(node.left, node)
            dfs(node.right, node)
        
        dfs(root, None)
        
        # BFS to simulate infection spread.
        visited = set()
        queue = deque([(start, 0)])  # (current_node_value, minutes)
        visited.add(start)
        max_time = 0
        
        while queue:
            current, minutes = queue.popleft()
            max_time = max(max_time, minutes)
            # Check all connected nodes.
            for neighbor in graph[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, minutes + 1))
                    
        return max_time
← Back to All Questions