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

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.