Amount of Time for Binary Tree to Be Infected solution and explanation
Google
9 more videos on this problem
Amount of Time for Binary Tree to Be Infected | Using BFS | Leetcode 2385codestorywithMIK · 29:25 · 13K views
2385. Amount of Time for Binary Tree to Be Infected | Graph | Tree | BFS | DFSAryan Mittal · 35:09 · 4K views
2385. Amount of Time for Binary Tree to Be Infected (Leetcode Medium)Programming Live with Larry · 5:39 · 2K views
Leetcode 2385: Amount of Time for Binary Tree to Be InfectedAlgorithms Casts · 8:55 · 1K views
LeetCode 2385 - Amount of Time for Binary Tree to Be Infected - PythonAlpha-Code · 10:58 · 384 views
Amount of Time for Binary Tree to Be Infected | 2385 Leetcode | Python3CodeMeThere · 13:12 · 293 views
Solving LeetCode 2385 Amount of Time for Binary Tree to Be Infected | BFS | DFS | MicrosoftCode Harmony · 34:13 · 245 views
2385. Amount of Time for Binary Tree to Be Infected - BFS TraversalCode-Yao · 12:34 · 191 views
Amount of Time for Binary Tree to Be Infected | Leetcode #2385 | C++ | Lost _CodeLost_Code · 9:53 · 90 views
2385. Amount of Time for Binary Tree to Be Infected ! Leetcode Java SolutionShantanu_Jod · 10:02 · 61 views
The problem
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
startexists in the tree.
Approach overview
Problem Overview: A virus starts spreading from a specific node in a binary tree. Each minute, the infection spreads to the node’s parent and children. The task is to compute how many minutes it takes until every node in the tree becomes infected.
Approach 1: Breadth-First Search (Graph Conversion) (Time: O(n), Space: O(n))
The tree structure only gives you child pointers. Infection spreads in three directions: left child, right child, and parent. Because parent references are missing, first convert the tree into an undirected graph using a hash table (adjacency list). Traverse the tree once and connect each node with its parent and children.
After building the graph, start a breadth-first search from the start node. BFS naturally models the infection process because each level of traversal represents one minute. Push the start node into a queue, expand to all unvisited neighbors, and count how many layers are processed. The final BFS depth equals the total infection time. This approach is straightforward and mirrors multi-source spreading problems such as rotting oranges.
Approach 2: Depth-First Search with Backtracking (Time: O(n), Space: O(n))
This approach avoids explicitly building a graph. Instead, perform a recursive depth-first search on the binary tree. The idea is to locate the start node and then propagate distances upward while simultaneously computing the farthest infection distance in subtrees.
During DFS, return the distance from the current node to the start node. When the start node is found, compute the height of its left and right subtrees to determine infection spread downward. When recursion unwinds, use the returned distance to infect the opposite subtree through the parent path. Each step updates the global maximum infection time.
This technique effectively simulates infection traveling both downward and upward in the tree. The recursion carries two pieces of information: distance to the start node and subtree heights. Although slightly harder to reason about than BFS, it avoids building an explicit adjacency structure.
Recommended for interviews: The BFS graph approach is usually the expected answer. Converting the tree into an undirected graph and running BFS clearly models the infection spreading minute by minute. It demonstrates strong understanding of tree traversal and graph traversal patterns. The DFS backtracking solution is elegant and optimal as well, but interviewers often prefer the BFS reasoning because it is easier to explain and debug.
Approach 1: Approach 1: Breadth-First Search
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:
- Convert the binary tree into a graph represented using an adjacency list. Since each node can infect its parent, left child, and right child, we need to treat the tree as a graph to easily find adjacent nodes.
- Use a BFS to traverse and track the infection spread, starting from the node with the 'start' value. Each time we move to the next level in our BFS, it represents the infection spreading to more nodes, thus increasing the time by one minute.
- Keep track of visited nodes to avoid processing the same node multiple times.
- The depth or number of levels needed to reach all nodes will be the time required to infect the entire tree.
from collections import defaultdict, deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def amountOfTime(self, root: TreeNode, start: int) -> int:
graph = defaultdict(list)
def build_graph(node, parent):
if node:
if parent is not None:
graph[node.val].append(parent)
graph[parent].append(node.val)
build_graph(node.left, node.val)
build_graph(node.right, node.val)
build_graph(root, None)
visited = set()
queue = deque([start])
visited.add(start)
time = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
if queue:
time += 1
return timeimport java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private void buildGraph(TreeNode node, Map<Integer, List<Integer>> graph, int parent) {
if (node == null) return;
if (parent != -1) {
graph.computeIfAbsent(node.val, k -> new ArrayList<>()).add(parent);
graph.computeIfAbsent(parent, k -> new ArrayList<>()).add(node.val);
}
buildGraph(node.left, graph, node.val);
buildGraph(node.right, graph, node.val);
}
public int amountOfTime(TreeNode root, int start) {
Map<Integer, List<Integer>> graph = new HashMap<>();
buildGraph(root, graph, -1);
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(start);
visited.add(start);
int time = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
int node = queue.poll();
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
if (visited.add(neighbor)) {
queue.add(neighbor);
}
}
}
if (!queue.isEmpty()) {
time++;
}
}
return time;
}
}#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
void buildGraph(TreeNode* node, unordered_map<int, vector<int>>& graph, int parent) {
if (!node) return;
if (parent > 0) {
graph[node->val].push_back(parent);
graph[parent].push_back(node->val);
}
buildGraph(node->left, graph, node->val);
buildGraph(node->right, graph, node->val);
}
int amountOfTime(TreeNode* root, int start) {
unordered_map<int, vector<int>> graph;
buildGraph(root, graph, -1);
unordered_set<int> visited;
queue<int> q;
q.push(start);
visited.insert(start);
int time = 0;
while (!q.empty()) {
for (int i = 0, n = q.size(); i < n; ++i) {
int node = q.front(); q.pop();
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
if (!q.empty()) ++time;
}
return time;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var amountOfTime = function(root, start) {
const graph = new Map();
const buildGraph = (node, parent) => {
if (!node) return;
if (parent !== null) {
if (!graph.has(node.val)) graph.set(node.val, []);
if (!graph.has(parent)) graph.set(parent, []);
graph.get(node.val).push(parent);
graph.get(parent).push(node.val);
}
buildGraph(node.left, node.val);
buildGraph(node.right, node.val);
};
buildGraph(root, null);
const visited = new Set();
const queue = [start];
visited.add(start);
let time = 0;
while (queue.length > 0) {
let size = queue.length;
while (size > 0) {
const current = queue.shift();
size--;
for (let neighbor of graph.get(current)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
if (queue.length > 0) time++;
}
return time;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 100000
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int treeInfectionTime(TreeNode* root, int start) {
// Implementation logic goes here
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int AmountOfTime(TreeNode root, int start) {
var graph = new Dictionary<int, List<int>>();
BuildGraph(root, -1, graph);
var visited = new HashSet<int>();
var queue = new Queue<int>();
queue.Enqueue(start);
visited.Add(start);
int time = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
int node = queue.Dequeue();
foreach (var neighbor in graph[node]) {
if (!visited.Contains(neighbor)) {
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
if (queue.Count > 0) time++;
}
return time;
}
private void BuildGraph(TreeNode node, int parent, Dictionary<int, List<int>> graph) {
if (node == null) return;
if (parent != -1) {
if (!graph.ContainsKey(node.val)) graph[node.val] = new List<int>();
if (!graph.ContainsKey(parent)) graph[parent] = new List<int>();
graph[node.val].Add(parent);
graph[parent].Add(node.val);
}
BuildGraph(node.left, node.val, graph);
BuildGraph(node.right, node.val, graph);
}
}The Python solution uses a graph to represent the binary tree and a BFS to simulate the infection spread across the tree structure, counting the minutes needed to infect all nodes.
Time Complexity: O(N)
Space Complexity: O(N)
Approach 2: Approach 2: Depth-First Search with Backtracking
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:
- Use DFS to traverse and mark nodes as visited, calculating the time taken to spread infection to each node recursively.
- Track maximum infection time encountered as we explore different paths.
- This approach is especially useful in trees where we may want to calculate distribution paths directly instead of simulating BFS.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def amountOfTime(self, root: TreeNode, start: int) -> int:
def dfs(node, parent):
if not node:
return 0
max_time = 0
for child in [node.left, node.right, parent_map.get(node.val)]:
if child and child != parent:
max_time = max(max_time, dfs(child, node))
return max_time + 1
parent_map = {}
start_node = None
def find_parent_and_start(node, parent):
nonlocal start_node
if node:
if node.val == start:
start_node = node
parent_map[node.val] = parent
find_parent_and_start(node.left, node)
find_parent_and_start(node.right, node)
find_parent_and_start(root, None)
return dfs(start_node, None) - 1import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private Map<Integer, TreeNode> parentMap = new HashMap<>();
private TreeNode targetNode = null;
public int amountOfTime(TreeNode root, int start) {
findParents(root, null, start);
return dfs(targetNode, null);
}
private void findParents(TreeNode node, TreeNode parent, int start) {
if (node == null) return;
if (node.val == start) {
targetNode = node;
}
if (parent != null) {
parentMap.put(node.val, parent);
}
findParents(node.left, node, start);
findParents(node.right, node, start);
}
private int dfs(TreeNode node, TreeNode parent) {
if (node == null) return 0;
int left = (node.left != parent) ? dfs(node.left, node) : 0;
int right = (node.right != parent) ? dfs(node.right, node) : 0;
int par = (parentMap.containsKey(node.val) && parentMap.get(node.val) != parent) ? dfs(parentMap.get(node.val), node) : 0;
return Math.max(left, Math.max(right, par)) + 1;
}
}#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int amountOfTime(TreeNode* root, int start) {
unordered_map<int, TreeNode*> parentTrack;
TreeNode* startNode = nullptr;
findParent(root, parentTrack, startNode, start);
return dfs(startNode, NULL, parentTrack);
}
void findParent(TreeNode* node, unordered_map<int, TreeNode*>& parents, TreeNode*& target, int start) {
if (!node) return;
if (node->val == start) {
target = node;
}
if (node->left) {
parents[node->left->val] = node;
findParent(node->left, parents, target, start);
}
if (node->right) {
parents[node->right->val] = node;
findParent(node->right, parents, target, start);
}
}
int dfs(TreeNode* node, TreeNode* parent, unordered_map<int, TreeNode*>& parents) {
if (!node) return 0;
int left = node->left != parent ? dfs(node->left, node, parents) : 0;
int right = node->right != parent ? dfs(node->right, node, parents) : 0;
int par = parents.count(node->val) && parents[node->val] != parent ? dfs(parents[node->val], node, parents) : 0;
return max(left, max(right, par)) + 1;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var amountOfTime = function(root, start) {
let parentMap = new Map();
let startNode = null;
function findParents(node, parent) {
if (!node) return;
if (node.val === start) startNode = node;
if (parent) parentMap.set(node.val, parent);
findParents(node.left, node);
findParents(node.right, node);
}
function dfs(node, parent) {
if (!node) return 0;
let left = (node.left !== parent) ? dfs(node.left, node) : 0;
let right = (node.right !== parent) ? dfs(node.right, node) : 0;
let par = (parentMap.has(node.val) && parentMap.get(node.val) !== parent) ? dfs(parentMap.get(node.val), node) : 0;
return Math.max(left, Math.max(right, par)) + 1;
}
findParents(root, null);
return dfs(startNode, null) - 1;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 100000
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int treeInfectionTimeDFS(TreeNode* root, int start) {
// Implementation logic goes here
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode targetNode;
private Dictionary<int, TreeNode> parents = new Dictionary<int, TreeNode>();
public int AmountOfTime(TreeNode root, int start) {
FindStartAndParents(root, null, start);
return DFS(targetNode, null) - 1;
}
private void FindStartAndParents(TreeNode node, TreeNode parent, int start) {
if (node == null) return;
if (node.val == start) targetNode = node;
if (parent != null) parents[node.val] = parent;
FindStartAndParents(node.left, node, start);
FindStartAndParents(node.right, node, start);
}
private int DFS(TreeNode node, TreeNode parent) {
if (node == null) return 0;
int left = node.left != parent ? DFS(node.left, node) : 0;
int right = node.right != parent ? DFS(node.right, node) : 0;
int par = parents.ContainsKey(node.val) && parents[node.val] != parent ? DFS(parents[node.val], node) : 0;
return Math.Max(left, Math.Max(right, par)) + 1;
}
}The Python implementation uses DFS with backtracking methodically, leveraging a dictionary for parent tracking to deduce infection propagation timelines from the starting node.
Time Complexity: O(N)
Space Complexity: O(N)
Approach 3: 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.
Then, we use start as the starting point, and search the entire tree through DFS to find the farthest distance, which is the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function amountOfTime(root: TreeNode | null, start: number): number {
const g: Map<number, number[]> = new Map();
const dfs = (node: TreeNode | null, fa: TreeNode | null) => {
if (!node) {
return;
}
if (fa) {
if (!g.has(node.val)) {
g.set(node.val, []);
}
g.get(node.val)!.push(fa.val);
if (!g.has(fa.val)) {
g.set(fa.val, []);
}
g.get(fa.val)!.push(node.val);
}
dfs(node.left, node);
dfs(node.right, node);
};
const dfs2 = (node: number, fa: number): number => {
let ans = 0;
for (const nxt of g.get(node) || []) {
if (nxt !== fa) {
ans = Math.max(ans, 1 + dfs2(nxt, node));
}
}
return ans;
};
dfs(root, null);
return dfs2(start, -1);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func amountOfTime(root *TreeNode, start int) int {
g := map[int][]int{}
var dfs func(*TreeNode, *TreeNode)
dfs = func(node, fa *TreeNode) {
if node == nil {
return
}
if fa != nil {
g[node.Val] = append(g[node.Val], fa.Val)
g[fa.Val] = append(g[fa.Val], node.Val)
}
dfs(node.Left, node)
dfs(node.Right, node)
}
var dfs2 func(int, int) int
dfs2 = func(node, fa int) (ans int) {
for _, nxt := range g[node] {
if nxt != fa {
ans = max(ans, 1+dfs2(nxt, node))
}
}
return
}
dfs(root, nil)
return dfs2(start, -1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search | Time Complexity: O(N) |
| Approach 2: Depth-First Search with Backtracking | Time Complexity: O(N) |
| Two DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Graph Conversion) | O(n) | O(n) | Best general solution. Easy to reason about infection spread level by level. |
| Depth-First Search with Backtracking | O(n) | O(n) | Useful when you want to avoid building an explicit graph and compute distances during recursion. |
Frequently asked questions
Is Amount of Time for Binary Tree to Be Infected easy or hard?
The problem is rated Medium because it combines multiple concepts: tree traversal, graph modeling, and BFS level processing. The logic becomes simple once you recognize that infection spreads like a graph traversal from the start node.
Amount of Time for Binary Tree to Be Infected Python/Java solution
In Python or Java, the standard implementation first performs a DFS to build a map of node connections. Then a BFS queue starts from the given node value and spreads to neighbors while counting levels. The implementation runs in O(n) time and O(n) space in both languages.
How to solve Amount of Time for Binary Tree to Be Infected in O(n)?
First map each node to its neighbors by linking parent and child nodes using a hash map. Then start a BFS from the infected node and expand to all neighbors each minute while tracking visited nodes. The number of BFS layers processed before the queue becomes empty represents the total infection time.
What is the best approach for Amount of Time for Binary Tree to Be Infected?
The most practical approach is converting the binary tree into an undirected graph and running Breadth-First Search from the start node. BFS processes nodes level by level, which naturally represents infection spreading each minute. The algorithm visits each node once, giving O(n) time complexity and O(n) space for the adjacency list and queue.
Is Amount of Time for Binary Tree to Be Infected asked at Google/Amazon/Meta?
Problems involving infection spread or graph traversal in trees frequently appear in interviews at companies like Amazon, Google, and Meta. The pattern of converting a tree to a graph and running BFS is commonly tested because it checks understanding of traversal strategies and graph modeling.
What data structure is used in Amount of Time for Binary Tree to Be Infected?
The typical solution uses a hash map to build an adjacency list representing the tree as an undirected graph. A queue is used for BFS traversal, and a visited set prevents revisiting nodes. In the DFS variant, recursion and subtree height calculations replace the explicit graph.
What is the time complexity of Amount of Time for Binary Tree to Be Infected?
Both common solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited once while building parent relationships and once during traversal (BFS or DFS). Space complexity is also O(n) due to recursion stack, adjacency lists, or visited sets.