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:
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:
[1, 105].1 <= Node.val <= 105start exists in the tree.In #2385 Amount of Time for Binary Tree to Be Infected, the infection spreads from a starting node to its adjacent nodes (parent and children) every minute. The key idea is to model the binary tree as an undirected graph, since infection can move both downward and upward. A common approach is to first traverse the tree using DFS to build a mapping between each node and its parent.
Once parent relationships are known, you can simulate the infection using Breadth-First Search (BFS) starting from the infected node. Each BFS level represents one minute, and the infection spreads to all unvisited neighbors (left child, right child, and parent). The total time equals the number of BFS levels required to visit all reachable nodes.
An alternative strategy uses DFS to compute distances from the start node while tracking subtree heights, but BFS is generally simpler to reason about. Both strategies traverse each node once, giving O(n) time complexity with additional structures for parent tracking and visited nodes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Parent Mapping + BFS Spread | O(n) | O(n) |
| Single/Two Pass DFS Distance Calculation | O(n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Convert the tree to an undirected graph to make it easier to handle.
Use BFS starting at the start node to find the distance between each node and the start node. The answer is the maximum distance.
Approach 1: Breadth-First Search (BFS)
This approach involves simulating the infection spread using BFS, starting from the infected node. Each level of the BFS traversal represents one minute of infection spreading.
The steps are as follows:
Time Complexity: O(N) where N is the number of nodes; we visit each node once.
Space Complexity: O(N) to store the adjacency list and manage the queue.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
The Java solution constructs the tree into a graph format using adjacency lists, leveraging BFS to spread the infection and compute the time required.
Approach 2: Depth-First Search with Backtracking
In this method, we perform a depth-first search (DFS) to calculate the maximum distance (time) required to infect every node from the start node, utilizing backtracking to manage node revisits.
Steps include:
Time Complexity: O(N)
Space Complexity: O(N) for the recursion stack if the tree is unbalanced.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In a binary tree, nodes only have direct access to their children. Since the infection can also spread to the parent, we store parent references in a hash map so the traversal can move in all directions like an undirected graph.
Yes, this problem reflects common interview themes such as tree traversal, BFS, and graph modeling. Variations of infection spread or distance-from-node problems are frequently asked in technical interviews at top tech companies.
A combination of a hash map and a queue works best. The hash map stores parent relationships for each node, allowing upward traversal, while the queue supports BFS to simulate infection spreading level by level.
The most common optimal approach converts the binary tree into an undirected structure by storing parent references, then performs a BFS starting from the infected node. Each BFS layer represents one minute of infection spread. This method visits every node once, resulting in O(n) time complexity.
1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <vector>
5using namespace std;
6
7struct TreeNode {
8 int val;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12};
13
14class Solution {
15public:
16 int amountOfTime(TreeNode* root, int start) {
17 unordered_map<int, TreeNode*> parentTrack;
18 TreeNode* startNode = nullptr;
19 findParent(root, parentTrack, startNode, start);
20 return dfs(startNode, NULL, parentTrack);
21 }
22
23 void findParent(TreeNode* node, unordered_map<int, TreeNode*>& parents, TreeNode*& target, int start) {
24 if (!node) return;
25 if (node->val == start) {
26 target = node;
27 }
28 if (node->left) {
29 parents[node->left->val] = node;
30 findParent(node->left, parents, target, start);
31 }
32 if (node->right) {
33 parents[node->right->val] = node;
34 findParent(node->right, parents, target, start);
35 }
36 }
37
38 int dfs(TreeNode* node, TreeNode* parent, unordered_map<int, TreeNode*>& parents) {
39 if (!node) return 0;
40 int left = node->left != parent ? dfs(node->left, node, parents) : 0;
41 int right = node->right != parent ? dfs(node->right, node, parents) : 0;
42 int par = parents.count(node->val) && parents[node->val] != parent ? dfs(parents[node->val], node, parents) : 0;
43 return max(left, max(right, par)) + 1;
44 }
45};This C++ implementation makes use of backtracking within DFS to evaluate various potential infection paths and calculate infection time swiftly and comprehensively.