Introduction

In this blog post, we will explore how to solve the LeetCode problem "2385" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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: The node is currently uninfected. The node is adjacent to an infected node. Return the number of minutes needed for the entire tree to be infected. Example 1: Input: root = [1,5,3,null,4,10,6,9,2], start = 3 Output: 4 Explanation: The following nodes are infected during: - Minute 0: Node 3 - Minute 1: Nodes 1, 10 and 6 - Minute 2: Node 5 - Minute 3: Node 4 - Minute 4: Nodes 9 and 2 It takes 4 minutes for the whole tree to be infected so we return 4. Example 2: Input: root = [1], start = 1 Output: 0 Explanation: At minute 0, the only node in the tree is infected so we return 0. Constraints: The number of nodes in the tree is in the range [1, 105]. 1 <= Node.val <= 105 Each node has a unique value. A node with a value of start exists in the tree.

Explanation

Here's a breakdown of the solution:

• Convert to Graph: The binary tree is converted into an undirected graph represented as an adjacency list. This allows easy traversal in both directions (parent to child and child to parent).
• Breadth-First Search (BFS): A BFS is performed starting from the start node. The BFS explores the graph layer by layer, representing each minute of infection spread.

• Track Time: The BFS keeps track of the time (minutes) elapsed as it explores the graph. The maximum time reached during the BFS represents the total time needed to infect the entire tree.

• Time & Space Complexity: O(N), where N is the number of nodes in the tree.

Code

    from collections import defaultdict, deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def amountOfTime(root: TreeNode, start: int) -> int:
    """
    Calculates the number of minutes needed to infect the entire tree.
    """

    graph = defaultdict(list)

    def build_graph(node: TreeNode):
        if not node:
            return

        if node.left:
            graph[node.val].append(node.left.val)
            graph[node.left.val].append(node.val)
            build_graph(node.left)

        if node.right:
            graph[node.val].append(node.right.val)
            graph[node.right.val].append(node.val)
            build_graph(node.right)

    build_graph(root)

    queue = deque([(start, 0)])  # (node, time)
    visited = {start}
    max_time = 0

    while queue:
        node, time = queue.popleft()
        max_time = max(max_time, time)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, time + 1))

    return max_time