Watch 10 video solutions for Amount of Time for Binary Tree to Be Infected, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 12,619 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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. |