#2385

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Amount of Time for Binary Tree to Be Infected

The problem asks to calculate the number of minutes for an infection to spread across all nodes in a binary tree starting from a given node.

hash table tree depth first search breadth first search binary tree

Problem Statement

You are given a binary tree represented by its root node and an integer start, which denotes the initially infected node. The infection starts at minute 0 from the start node.

At each minute, an infected node will cause its directly connected neighbors to become infected. The task is to determine how many minutes it will take for all the nodes in the tree to be infected.

Examples

Example 1

Input: root = [1,5,3,null,4,10,6,9,2], start = 3

Output: 4

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

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.

Solution Approach

Convert the Tree to an Undirected Graph

To solve this problem efficiently, convert the binary tree into an undirected graph where each node is connected to its parent and children. This transformation allows easy traversal using BFS or DFS, making it simpler to track the infection spread.

Breadth-First Search (BFS) for Infection Spread

Use BFS to simulate the infection spread across the graph. Start from the start node and expand to adjacent nodes level by level. Each level corresponds to a minute in the infection process. BFS ensures the shortest time for the infection to reach every node.

Track Infection with a State

Keep track of the nodes' infection states using a set or dictionary to avoid re-visiting nodes. This state tracking ensures that each node is infected only once, preventing redundant operations and ensuring efficiency.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) where n is the number of nodes in the tree, since BFS or DFS will visit each node exactly once. The space complexity is also O(n) due to the storage of the adjacency list (graph representation) and the state tracking structures used during traversal.

What Interviewers Usually Probe

The problem tests the ability to convert a tree into an undirected graph.
The candidate demonstrates understanding of BFS/DFS and state management in tree-like structures.
The solution should involve careful handling of state to avoid redundant infections.

Common Pitfalls or Variants

Common pitfalls

Failing to convert the tree into an undirected graph before starting traversal can lead to incorrect infection spread handling.
Not keeping track of the visited nodes can cause infinite loops or re-infection of already infected nodes.
Misunderstanding the BFS/DFS approach can lead to inefficient or incorrect spread simulation.

Follow-up variants

The tree can be large with up to 105 nodes, requiring careful space and time optimization.
The infection might not be continuous; ensure each minute correctly tracks the new infections.
Edge cases where the tree consists of only one node or the infection starts at a leaf node should be handled.

FAQ

What is the core pattern used to solve the Amount of Time for Binary Tree to Be Infected problem?

The core pattern is converting the binary tree into an undirected graph, followed by BFS or DFS for efficient infection spread simulation.

How can I optimize the BFS approach in this problem?

Optimizing BFS involves using a state tracking system to avoid revisiting infected nodes and ensuring the graph representation is accurate and efficient.

What are some common pitfalls when solving this problem?

Common pitfalls include failing to convert the tree into an undirected graph, not tracking visited nodes, and inefficient traversal techniques.

How does GhostInterview help with tree-based traversal problems?

GhostInterview helps by providing step-by-step guidance on graph conversions, traversal methods, and performance optimization, ensuring a clear and efficient approach.

Is BFS or DFS better for the Amount of Time for Binary Tree to Be Infected problem?

Both BFS and DFS are valid approaches, but BFS is typically preferred for this problem as it efficiently handles level-by-level infection spread.

terminal

Solution

Solution 1: Two DFS

First, we build a graph through one DFS, and get an adjacency list $g$, where $g[node]$ represents all nodes connected to the node $node$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# 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
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        def dfs(node: Optional[TreeNode], fa: Optional[TreeNode]):
            if node is None:
                return
            if fa:
                g[node.val].append(fa.val)
                g[fa.val].append(node.val)
            dfs(node.left, node)
            dfs(node.right, node)

        def dfs2(node: int, fa: int) -> int:
            ans = 0
            for nxt in g[node]:
                if nxt != fa:
                    ans = max(ans, 1 + dfs2(nxt, node))
            return ans

        g = defaultdict(list)
        dfs(root, None)
        return dfs2(start, -1)

Continue Practicing

#2641 cousins in binary tree ii #2368 reachable nodes with restrictions #2458 height of binary tree after subtree removal queries