Skip to main content
Talentd

Amount of Time for Binary Tree to Be Infected - Solution & Explanation

MediumHash TableTreeDepth-First SearchBreadth-First Search23 min readAsked at: Amazon, Microsoft, Goldman Sachs +9
Practice this problem

Problem Statement

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 start exists 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.

This C solution creates a graph-like structure from the binary tree and performs a breadth-first search from the start node to determine the infection spread time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

This C solution deploys a DFS strategy to recursively compute time taken to infect each node, storing the maximum time found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N)
Space Complexity: O(N) for the recursion stack if the tree is unbalanced.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Breadth-First Search

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.

Approach 2: Depth-First Search with Backtracking

Time Complexity: O(N)
Space Complexity: O(N) for the recursion stack if the tree is unbalanced.

Two DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 BacktrackingO(n)O(n)Useful when you want to avoid building an explicit graph and compute distances during recursion.

Video Solution

Amount of Time for Binary Tree to Be Infected | Using BFS | Leetcode 2385 • codestorywithMIK • 13,767 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Amount of Time for Binary Tree to Be Infected with our built-in code editor and test cases.

Practice on FleetCode
Previous

All Nodes Distance K in Binary Tree

Next

Count the Number of Infection Sequences