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.

Description Hints 2 Solution Video 29:25

2385. Amount of Time for Binary Tree to Be Infected

Medium65.8% acceptance12 companies

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, 10⁵].
1 <= Node.val <= 10⁵
Each node has a unique value.
A node with a value of start exists in the tree.

Asked at 12 companies

Blinkit ShareChat Adobe Flipkart PhonePe ServiceNow Amazon Microsoft Uber Goldman Sachs

Google Bloomberg

Topics

Hints open one at a time

Hint 1

Convert the tree to an undirected graph to make it easier to handle.

Hint 2

Use BFS starting at the start node to find the distance between each node and the start node. The answer is the maximum distance.

29:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution