2385. Amount of Time for Binary Tree to Be Infected
Problem Description
In this problem, we are given the root of a binary tree where each node has a unique value, and an integer start
which represents the value of the node from where an infection begins. At minute 0, the infection starts at the start
node.
The infection spreads every minute to adjacent nodes that are not yet infected. A node is considered adjacent if it is directly connected to an infected node by an edge. The task is to calculate the number of minutes it will take for the infection to spread to the entire tree.
Flowchart Walkthrough
Let's analyze LeetCode problem 2385. Amount of Time for Binary Tree to Be Infected using the provided algorithm flowchart. We'll step through the flowchart to determine the appropriate algorithm:
Is it a graph?
- Yes: Although the problem is about a binary tree, a tree is a special case of a graph.
Is it a tree?
- Yes: The structure discussed in the problem is specifically a binary tree.
The flowchart leads us directly to choose DFS as the recommended approach since the next step after identifying the structure as a tree suggests using DFS.
Conclusion: The flowchart directly suggests using Depth-First Search (DFS) for this problem since we are dealing with a tree structure where DFS is highly suitable for traversing and manipulating tree data.
Intuition
The key to solving this problem is to consider the binary tree as an undirected graph, where an edge exists between parent and child nodes. We can then perform a breadth-first search (BFS) starting from the start
node since BFS processes nodes level by level, which naturally aligns with the passage of minutes as the infection spreads.
The solution involves these steps:
-
Convert the tree structure into a graph representation. This is necessary because a tree does not provide a straightforward way to move to siblings or the parent from a child node. In a graph representation, however, we can navigate to any adjacent node with ease.
-
Once we have our graph, we begin a BFS from the
start
node. We keep a queue to keep track of nodes to process, and a set to remember which nodes we've already visited (to prevent reinfection). -
We process the nodes in the current queue, which represents all nodes that got infected in the current minute. For each of those nodes, we add their uninfected adjacent nodes to the queue to be processed in the next minute.
-
The process continues until there are no more nodes to infect, which is when our queue is empty. We keep track of the time with a variable that increments at the end of processing all nodes at a current minute.
-
The loop continues until the queue is empty, and the time variable at this point represents the total number of minutes taken to infect the entire tree.
The provided Python code follows this approach to arrive at the solution.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Solution Approach
The given solution uses the Breadth-First Search (BFS) algorithm to simulate the spread of the infection across the tree. Here's a detailed breakdown of the implementation:
-
Graph Construction:
The solution begins by creating a graph representation of the tree using a default dictionary
g
of lists. This is done in thedfs
(Depth-First Search) function.def dfs(root): if root is None: return if root.left: g[root.val].append(root.left.val) g[root.left.val].append(root.val) if root.right: g[root.val].append(root.right.val) g[root.right.val].append(root.val) dfs(root.left) dfs(root.right)
The
dfs
function is a recursive function that traverses the entire binary tree and adds each node's children to its list of adjacent nodes in the graph. -
Initialization:
Initialize an empty set
vis
to keep track of visited nodes (infected nodes) and a queueq
to maintain the BFS's order of node processing, with thestart
node as the initial node to be processed.vis = set() q = deque([start])
-
BFS Algorithm:
The solution sets up a while loop that continues until the queue
q
is empty, signifying that there are no more nodes to be infected.ans = -1 while q: ans += 1 for _ in range(len(q)): i = q.popleft() vis.add(i) for j in g[i]: if j not in vis: q.append(j)
Inside the loop,
ans
is incremented to count the minutes. For each iteration of the while loop, it processes all nodes currently in the queue, which are the nodes that got infected in the previous minute. It pops each node from the queue, adds it to thevis
set, and then iterates over its adjacent nodes. If any adjacent node has not been visited (infected), it is added to the queue to be processed in the next minute.
By the end of the BFS loop, ans
holds the number of minutes it took to infect the entire tree since each loop iteration represents one minute of infection time passing.
The return value ans
represents the required number of minutes for the infection to spread through the entire tree, as determined by our BFS algorithm.
return ans
This solution efficiently converts the tree into a graph and then uses the BFS algorithm to simulate the spread of infection in discrete minute intervals.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Assume we have the following binary tree and the infection starts at the node with value 3.
1 / \ 2 3 / \ 4 5
Step 1: Convert the tree into a graph representation.
Following the DFS traversal, we get:
- Node 1 is connected to nodes 2 and 3.
- Node 2 is connected to node 1.
- Node 3 is connected to nodes 1, 4, and 5.
- Node 4 is connected to node 3.
- Node 5 is connected to node 3.
Our graph g
representation will be:
{ 1: [2, 3], 2: [1], 3: [1, 4, 5], 4: [3], 5: [3] }
Step 2: Initialize the visited set vis
to {}
and the queue q
to [3]
since infection starts at node 3.
Step 3: Begin BFS algorithm.
-
At minute 0,
ans = -1
. We incrementans
to 0. The queueq
has just one node, which is 3. Node 3 is popped from the queue and added to the visited set:vis = {3}
. Nodes 1, 4, and 5 are adjacent to 3 and are added to the queue:q = [1, 4, 5]
. -
At minute 1,
ans
is incremented to 1. Three nodes (1, 4, and 5) are in the queue. We visit each node, add it to the visited set, and add their unvisited (uninfected) adjacent nodes to the queue. However, node 1 has no unvisited adjacent nodes, and both nodes 4 and 5 have only node 3 as their adjacent node, which is already visited. So the queue remains empty after this:vis = {1, 3, 4, 5}
andq = []
.
There are no more nodes to infect and the queue is empty.
By the end of the process, ans = 1
, which means that it took 1 minute for the infection to spread through the entire tree.
This small example illustrates how the BFS algorithm spreads the infection across the tree level by level, minutely fitting the problem's requirement to calculate the time it takes to infect the whole tree.
Solution Implementation
1# Importing the required modules.
2from collections import defaultdict, deque
3
4# Definition for a binary tree node.
5class TreeNode:
6 def __init__(self, val=0, left=None, right=None):
7 self.val = val
8 self.left = left
9 self.right = right
10
11class Solution:
12 def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
13 # Depth-First Search to build the graph from the binary tree.
14 def dfs(node):
15 if node is None:
16 return
17 # Connect current node with left child if it exists.
18 if node.left:
19 graph[node.val].append(node.left.val)
20 graph[node.left.val].append(node.val)
21 # Connect current node with right child if it exists.
22 if node.right:
23 graph[node.val].append(node.right.val)
24 graph[node.right.val].append(node.val)
25 # Recursive call for left and right children.
26 dfs(node.left)
27 dfs(node.right)
28
29 # Initialize a default dictionary for the graph representation.
30 graph = defaultdict(list)
31 # Start DFS traversal to build graph.
32 dfs(root)
33 # Initialize a set to keep track of visited nodes.
34 visited = set()
35 # Initialize a queue with the starting node.
36 queue = deque([start])
37 # Initialize time counter.
38 time = -1
39 # Execute until the queue is empty.
40 while queue:
41 # Increase time each level we go deeper in the graph.
42 time += 1
43 # Traverse nodes at the current level.
44 for _ in range(len(queue)):
45 current_node = queue.popleft()
46 visited.add(current_node)
47 # Explore all the neighbors of the current node.
48 for neighbor in graph[current_node]:
49 if neighbor not in visited:
50 queue.append(neighbor)
51 # Return the total amount of time.
52 return time
53
1class Solution {
2 // To store the adjacency list representation of the binary tree
3 private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
4
5 // Calculates the amount of time needed to infect all nodes starting from 'start' node
6 public int amountOfTime(TreeNode root, int start) {
7 // Convert tree to graph (adjacency list)
8 convertToGraph(root);
9 // Queue for the Breadth First Search (BFS)
10 Deque<Integer> queue = new ArrayDeque<>();
11 // Set to track visited nodes
12 Set<Integer> visited = new HashSet<>();
13
14 // Offer the starting node into the queue
15 queue.offer(start);
16 int time = -1; // Initialize time to -1 because we increase time before processing the nodes
17
18 while (!queue.isEmpty()) {
19 time++; // Increase time as we are moving to the next level of nodes
20
21 // Loop through the nodes at the current level
22 for (int i = queue.size(); i > 0; i--) {
23 int currentNode = queue.pollFirst();
24 visited.add(currentNode);
25
26 // Get the neighbors of the current node
27 if (adjacencyList.containsKey(currentNode)) {
28 for (int neighbor : adjacencyList.get(currentNode)) {
29 if (!visited.contains(neighbor)) {
30 queue.offer(neighbor);
31 }
32 }
33 }
34 }
35 }
36 return time; // Return the total time taken to infect all nodes
37 }
38
39 // Helper method to convert the binary tree to a graph represented as an adjacency list
40 private void convertToGraph(TreeNode node) {
41 if (node == null) {
42 return;
43 }
44
45 // Connect the current node with its left child
46 if (node.left != null) {
47 adjacencyList.computeIfAbsent(node.val, k -> new ArrayList<>()).add(node.left.val);
48 adjacencyList.computeIfAbsent(node.left.val, k -> new ArrayList<>()).add(node.val);
49 }
50
51 // Connect the current node with its right child
52 if (node.right != null) {
53 adjacencyList.computeIfAbsent(node.val, k -> new ArrayList<>()).add(node.right.val);
54 adjacencyList.computeIfAbsent(node.right.val, k -> new ArrayList<>()).add(node.val);
55 }
56
57 // Recursively convert the left and right subtrees to the graph
58 convertToGraph(node.left);
59 convertToGraph(node.right);
60 }
61}
62
1#include <unordered_map>
2#include <vector>
3#include <queue>
4#include <unordered_set>
5
6// Definition for a binary tree node
7struct TreeNode {
8 int val;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode() : val(0), left(nullptr), right(nullptr) {}
12 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18 // Graph representation of the tree
19 unordered_map<int, vector<int>> graph;
20
21 // Find the amount of time needed to infect all nodes starting from the start node
22 int amountOfTime(TreeNode* root, int start) {
23 // Build graph representation of the tree using DFS
24 constructGraph(root);
25
26 // Queue for BFS traversal
27 queue<int> q;
28 q.push(start);
29
30 // Set to keep track of visited nodes
31 unordered_set<int> visited;
32
33 // Variable to track the number of minutes passed
34 int minutesPassed = -1;
35
36 // Perform BFS on the graph
37 while (!q.empty()) {
38 // Increment time for each level
39 ++minutesPassed;
40 // Iterate over all nodes in the current level
41 for (int levelSize = q.size(); levelSize > 0; --levelSize) {
42 int currentNode = q.front();
43 q.pop();
44 visited.insert(currentNode);
45 // Add all unvisited adjacent nodes to the queue
46 for (int adjacentNode : graph[currentNode]) {
47 if (!visited.count(adjacentNode)) {
48 q.push(adjacentNode);
49 }
50 }
51 }
52 }
53
54 // Return the total time passed to infect all nodes
55 return minutesPassed;
56 }
57
58 // Helper function to build graph from the binary tree using DFS
59 void constructGraph(TreeNode* root) {
60 if (!root) return;
61
62 // Connect current node with its left child (if exists)
63 if (root->left) {
64 graph[root->val].push_back(root->left->val);
65 graph[root->left->val].push_back(root->val);
66 }
67
68 // Connect current node with its right child (if exists)
69 if (root->right) {
70 graph[root->val].push_back(root->right->val);
71 graph[root->right->val].push_back(root->val);
72 }
73
74 // Continue DFS with the children
75 constructGraph(root->left);
76 constructGraph(root->right);
77 }
78};
79
1/**
2 * Given the root of a binary tree and an integer `start` representing the value of the node where an
3 * infection starts, the function `amountOfTime` returns the minimum number of minutes needed to infect all nodes in the tree.
4 * Here, each minute, any infected node in the tree can spread the infection to its children and its parent.
5 *
6 * @param {TreeNode | null} root - The root node of the binary tree.
7 * @param {number} start - The value of the node where the infection starts.
8 * @returns The minimum number of minutes needed to infect all nodes.
9 */
10
11// Auxiliary function to perform Depth First Search (DFS) starting from a node while avoiding the parent node
12// to compute the time taken to spread the infection throughout the tree.
13function depthFirstSearch(start: number, parent: number): number {
14 let maxTime = 0;
15 // Retrieve adjacent nodes (children and parent) for the current node.
16 const adjacentNodes = adjacencyList.get(start) ?? [];
17 for (const nextNode of adjacentNodes) {
18 // Avoid returning to the parent node.
19 if (nextNode !== parent) {
20 // Recur on the adjacent node, incrementing the time by 1.
21 const time = depthFirstSearch(nextNode, start) + 1;
22 // Keep track of the maximum time found so far.
23 maxTime = Math.max(maxTime, time);
24 }
25 }
26 return maxTime;
27}
28
29// Function to convert the binary tree into an adjacency list, which will allow easy traversal of
30// the nodes in no particular order to help simulate the spread of the infection.
31function createAdjacencyList(node: TreeNode) {
32 if (node.left != null) {
33 // If there is a left child, connect parent to left and vice versa.
34 adjacencyList.set(node.val, [...(adjacencyList.get(node.val) ?? []), node.left.val]);
35 adjacencyList.set(node.left.val, [...(adjacencyList.get(node.left.val) ?? []), node.val]);
36 // Recur on the left child.
37 createAdjacencyList(node.left);
38 }
39 if (node.right != null) {
40 // If there is a right child, connect parent to right and vice versa.
41 adjacencyList.set(node.val, [...(adjacencyList.get(node.val) ?? []), node.right.val]);
42 adjacencyList.set(node.right.val, [...(adjacencyList.get(node.right.val) ?? []), node.val]);
43 // Recur on the right child.
44 createAdjacencyList(node.right);
45 }
46}
47
48// This map will store the adjacency list of the tree where the key is the node value
49// and the value is an array of adjacent node values.
50const adjacencyList = new Map<number, number[]>();
51
52// This is our main function which will first construct an adjacency list from the given tree
53// and then use DFS to find out the time taken to spread the infection from the 'start' node to all other nodes.
54function amountOfTime(root: TreeNode | null, start: number): number {
55 // Prepare the adjacency list from the binary tree.
56 if (root) createAdjacencyList(root);
57 // Perform DFS starting at the start node, using -1 to indicate that there's no parent for the start node.
58 return depthFirstSearch(start, -1);
59}
60
Time and Space Complexity
Time Complexity:
The time complexity of the provided code is O(N)
where N
is the number of nodes in the tree. The reason for this is as follows:
- The
dfs
function is called once for each node in the tree during the construction of the graphg
.dfs
visits each node exactly once. - The BFS loop, which uses the queue
q
, runs while there are nodes to be visited. In the worst case, each node is inserted into and removed from the queue exactly once, which leads toO(N)
operations.
Therefore, because both the DFS and the BFS visit each node exactly once, the overall time complexity is O(N)
.
Space Complexity:
The space complexity of the code is also O(N)
for the following reasons:
- The graph
g
, which is adefaultdict(list)
, stores an adjacency list representation of the tree. This requires space for each edge in the undirected graph representation of the tree. Since a tree withN
nodes hasN-1
edges and each edge is stored twice (once for each direction), the space required is2*(N-1)
, which isO(N)
. - The set
vis
, which keeps track of visited nodes, stores up toN
node values in the worst case. - The queue
q
may store up toN
node values in the worst case when nodes are waiting to be visited. - The recursive stack space for
dfs
will have a maximum depth of the height of the tree, which isO(N)
in the worst case for a skewed tree.
Summing these up, the space used is O(N)
due to the storage of nodes in the graph representation, the visited set, the queue, and the call stack.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Want a Structured Path to Master System Design Too? Don’t Miss This!