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

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.

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.