#2385
Amount of Time for Binary Tree to Be Infected
MediumHash TableTreeDepth-First SearchBreadth-First SearchBinary TreeGraph Traversal (BFS)Tree RepresentationAdjacency List
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
The optimal solution leverages a graph representation of the tree and uses BFS to efficiently spread the infection. By tracking the distance from the start node, we can determine the time needed for the entire tree to be infected.
⚙️
Algorithm
3 steps- 1Step 1: Convert the binary tree into an undirected graph using an adjacency list.
- 2Step 2: Perform a BFS starting from the 'start' node to explore all connected nodes.
- 3Step 3: Count the number of minutes taken to infect all nodes by tracking the maximum level reached during BFS.
solution.py41 lines
1# Full working Python code
2class TreeNode:
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.left = left
6 self.right = right
7
8from collections import deque
9
10def amountOfTime(root, start):
11 if not root:
12 return 0
13
14 # Create a graph representation of the tree
15 graph = {}
16 def build_graph(node, parent):
17 if node:
18 if node.val not in graph:
19 graph[node.val] = []
20 if parent:
21 graph[node.val].append(parent.val)
22 build_graph(node.left, node)
23 build_graph(node.right, node)
24
25 build_graph(root, None)
26
27 # BFS to spread the infection
28 queue = deque([start])
29 visited = set([start])
30 minutes = -1
31
32 while queue:
33 for _ in range(len(queue)):
34 current = queue.popleft()
35 for neighbor in graph[current]:
36 if neighbor not in visited:
37 visited.add(neighbor)
38 queue.append(neighbor)
39 minutes += 1
40
41 return minutesℹ
Complexity note: The complexity is O(n) because we traverse each node once to build the graph and once more during BFS, leading to a linear relationship.
- 1Converting the tree to a graph simplifies the problem of tracking infections.
- 2Using BFS allows for efficient exploration of nodes in layers, which is ideal for spreading processes like infections.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.