# Amount of Time for Binary Tree to Be Infected
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected)
Canonical: https://scaleengineer.com/dsa/problems/amount-of-time-for-binary-tree-to-be-infected
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Nutanix](https://scaleengineer.com/companies/nutanix), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [ShareChat](https://scaleengineer.com/companies/sharechat)
---
## Problem
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:**

![](https://assets.glich.co/dsa/amount-of-time-for-binary-tree-to-be-infected/image0.png) 

**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:**

![](https://assets.glich.co/dsa/amount-of-time-for-binary-tree-to-be-infected/image1.png) 

**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.

# Approaches
## Convert to Graph and Perform BFS
This approach treats the binary tree as an undirected graph. Since the infection spreads to adjacent nodes (parent, left child, right child), we can model this problem as finding the longest shortest path from the `start` node to any other node in the graph. The time taken is equal to this maximum distance. The algorithm first converts the tree into a more general graph data structure, like an adjacency list, and then performs a Breadth-First Search (BFS) starting from the infected node to find this maximum distance.
**Time:** O(N), where N is the number of nodes. Building the graph requires visiting each node once, which is O(N). The subsequent BFS also visits each node and edge once, which is O(V + E) = O(N + N-1) = O(N). · **Space:** O(N), where N is the number of nodes in the tree. The adjacency list stores 2*(N-1) edges, leading to O(N) space. The `visited` set and the BFS `queue` can also grow up to O(N) in the worst case.
**Pros:** The logic is straightforward and follows a standard pattern for graph traversal problems.; It correctly models the problem by allowing traversal in any direction (up to parent, down to children).; Relatively easy to debug as the graph construction and BFS traversal are separate, well-understood algorithms.
**Cons:** Requires O(N) auxiliary space to store the adjacency list, which can be substantial for a large number of nodes.; Involves two distinct phases: building the graph and then traversing it, which might be slightly less performant in practice than a single-pass solution due to data structure overhead.
### Explanation
The core idea is to abstract away the tree structure into a graph, which simplifies reasoning about traversal in all directions (up, down, left, right). 

First, we build the graph. We can traverse the tree with any method (like DFS). For each node, we establish connections to its neighbors. For any node `u` and its child `v`, we add an edge from `u` to `v` and another from `v` to `u` in our adjacency list. This ensures we can traverse both downwards and upwards.

```java
private void buildGraph(TreeNode node, Map<Integer, List<Integer>> adj) {
    if (node == null) return;

    if (node.left != null) {
        adj.computeIfAbsent(node.val, k -> new ArrayList<>()).add(node.left.val);
        adj.computeIfAbsent(node.left.val, k -> new ArrayList<>()).add(node.val);
    }
    if (node.right != null) {
        adj.computeIfAbsent(node.val, k -> new ArrayList<>()).add(node.right.val);
        adj.computeIfAbsent(node.right.val, k -> new ArrayList<>()).add(node.val);
    }
    buildGraph(node.left, adj);
    buildGraph(node.right, adj);
}
```

Once the graph is constructed, we perform a standard level-order BFS starting from the `start` node. BFS is ideal here because it explores the graph layer by layer, which directly corresponds to the spread of infection minute by minute. We keep track of the number of levels traversed; this count will be our final answer.

```java
public int amountOfTime(TreeNode root, int start) {
    Map<Integer, List<Integer>> adj = new HashMap<>();
    buildGraph(root, adj);

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    Set<Integer> visited = new HashSet<>();
    visited.add(start);
    int minutes = -1;

    while (!queue.isEmpty()) {
        minutes++;
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            int currentNode = queue.poll();
            if (adj.containsKey(currentNode)) {
                for (int neighbor : adj.get(currentNode)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
        }
    }
    return minutes;
}
```
### Algorithm
*   **Step 1: Build Graph Representation.**
    1.  Create an adjacency list, for example, a `Map<Integer, List<Integer>>`, to store the graph structure.
    2.  Traverse the binary tree using a recursive helper function (e.g., DFS).
    3.  For each node, if it has a parent, add an undirected edge between the node and its parent in the adjacency list.
    4.  Similarly, for each node, add undirected edges to its left and right children if they exist. A simpler way is to just traverse downwards and for each `node` with a `child`, add `(node.val, child.val)` and `(child.val, node.val)` to the map.

*   **Step 2: Perform Breadth-First Search (BFS).**
    1.  Initialize a queue and add the `start` node's value.
    2.  Create a `visited` set to keep track of infected nodes, and add the `start` value to it.
    3.  Initialize a variable `minutes` to -1.
    4.  Begin a loop that continues as long as the queue is not empty. In each iteration, this loop processes one level of the graph (one minute of infection spread).
    5.  Increment `minutes`.
    6.  Get the number of nodes at the current level (`levelSize`).
    7.  Loop `levelSize` times to process each node at the current level.
    8.  Dequeue a node. For this node, iterate through its neighbors in the adjacency list.
    9.  If a neighbor has not been visited, add it to the `visited` set and enqueue it.
    10. Once the main loop finishes, `minutes` will hold the maximum time required, which is the answer.

## Optimized Single-Pass DFS
This optimized approach solves the problem in a single pass using Depth-First Search (DFS), thereby avoiding the O(N) space overhead of building an explicit graph. The key idea is to use the return value of the recursive DFS function to pass information up the tree. This information includes either the distance to the `start` node if it's in the current subtree, or the height of the current subtree if it's not. A global variable tracks the maximum infection time discovered.
**Time:** O(N), as the DFS traversal visits each node in the tree exactly once. · **Space:** O(H), where H is the height of the tree. This space is consumed by the recursion stack. For a balanced tree, this is O(log N), which is a significant improvement over O(N). In the worst case of a skewed tree, it becomes O(N).
**Pros:** Highly efficient in terms of space, using only O(H) space for the recursion stack.; Solves the problem in a single pass over the tree.; Generally faster in practice due to less overhead from auxiliary data structures.
**Cons:** The logic is more complex and less intuitive than the graph-based approach.; Overloading the meaning of the return value (positive for distance, negative for height) can be subtle and error-prone.
### Explanation
We perform a post-order traversal. For any given node, after visiting its children, we have two key pieces of information: the result from the left subtree and the result from the right subtree. Based on these results and the current node's value, we can determine the maximum infection time involving this node and its subtrees.

The recursive function `traverse(node, start)` cleverly encodes its findings in its return value:
-   **Positive value `d`**: The `start` node is in this subtree, `d` edges away from the current node.
-   **Negative value `-h`**: The `start` node is not in this subtree, and its height is `h`.

Let's analyze the logic at a `node` after recursive calls to its children:
1.  **If `node` is the `start` node**: The infection spreads downwards. The time is the height of the taller child subtree. We update our global `maxTime` with this value. We then return `1` to the parent, signaling that the `start` node is its immediate child.
2.  **If `start` is in a subtree (e.g., left)**: We know the distance from `start` to the current `node` (which is `leftResult`). The longest path from `start` could be one that goes up to `node` and then all the way down the right subtree. The time for this path is `leftResult + height_of_right_subtree`. We update `maxTime` with this potential maximum. We then return `leftResult + 1` to the parent, continuing to propagate the distance to `start`.
3.  **If `start` is not in the subtree**: The node is just part of a regular branch. We calculate its height based on its children's heights and return it as a negative number to the parent.

This allows us to calculate both downward infection times (from `start` into its own subtree) and upward-then-downward infection times in a single traversal.

```java
class Solution {
    private int maxTime = 0;

    public int amountOfTime(TreeNode root, int start) {
        traverse(root, start);
        return maxTime;
    }

    /**
     * Returns the distance from node to start if start is in the subtree.
     * Otherwise, returns the negative height of the subtree.
     */
    private int traverse(TreeNode node, int start) {
        if (node == null) {
            return 0;
        }

        int leftResult = traverse(node.left, start);
        int rightResult = traverse(node.right, start);

        if (node.val == start) {
            // Infection starts here. Max time to infect its own subtrees.
            // The heights are the absolute values of the results from children.
            maxTime = Math.max(Math.abs(leftResult), Math.abs(rightResult));
            // Return 1 to parent, indicating distance to start.
            return 1;
        }

        if (leftResult > 0 || rightResult > 0) {
            // Start node is in one of the subtrees.
            // The infection has to travel up to the current node and then down the other subtree.
            maxTime = Math.max(maxTime, Math.abs(leftResult) + Math.abs(rightResult));
            // Propagate the distance to the start node upwards.
            return (leftResult > 0 ? leftResult : rightResult) + 1;
        } else {
            // Start node is not in this subtree. Return the height of this subtree as a negative value.
            return Math.min(leftResult, rightResult) - 1;
        }
    }
}
```
### Algorithm
*   Define a global or class-level variable `maxTime` and initialize it to 0.
*   Create a recursive DFS function, say `traverse(node, start)`, that returns an integer with special meaning:
    *   A positive return value `d` signifies that the `start` node was found in the current `node`'s subtree, and its distance from `node` is `d`.
    *   A negative return value `-h` signifies that the `start` node was *not* found, and the height of the subtree rooted at `node` is `h`.
    *   A return value of `0` corresponds to a `null` node.
*   **Base Case:** If `traverse` is called on a `null` node, return `0`.
*   **Recursive Step (Post-order Traversal):**
    1.  Recursively call `traverse` on the left and right children to get their results: `leftResult` and `rightResult`.
    2.  Check if the current `node` is the `start` node. If `node.val == start`:
        *   The infection starts here. The time to infect its own subtrees is the maximum of their heights. Update `maxTime = max(maxTime, abs(leftResult), abs(rightResult))`. 
        *   Return `1` to its parent, indicating the `start` node is at distance 1.
    3.  If the `start` node was found in a child's subtree (e.g., `leftResult > 0`):
        *   The infection path to the other subtree (right) goes up to the current node and then down. The time for this path is `leftResult` (up) + `abs(rightResult)` (down).
        *   Update `maxTime = max(maxTime, leftResult + abs(rightResult))`. 
        *   Return `leftResult + 1` to propagate the distance to `start` upwards.
        *   Handle the symmetric case for the right subtree.
    4.  If the `start` node is not in the current node's subtree (`leftResult <= 0` and `rightResult <= 0`):
        *   The function's job is to report the height of this subtree. Return `-(1 + max(abs(leftResult), abs(rightResult)))`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Integer , List < Integer >> g = new HashMap <>(); public int amountOfTime ( TreeNode root , int start ) { dfs ( root ); Deque < Integer > q = new ArrayDeque <>(); Set < Integer > vis = new HashSet <>(); q . offer ( start ); int ans = - 1 ; while (! q . isEmpty ()) { ++ ans ; for ( int n = q . size (); n > 0 ; -- n ) { int i = q . pollFirst (); vis . add ( i ); if ( g . containsKey ( i )) { for ( int j : g . get ( i )) { if (! vis . contains ( j )) { q . offer ( j ); } } } } } return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } if ( root . left != null ) { g . computeIfAbsent ( root . val , k -> new ArrayList <>()). add ( root . left . val ); g . computeIfAbsent ( root . left . val , k -> new ArrayList <>()). add ( root . val ); } if ( root . right != null ) { g . computeIfAbsent ( root . val , k -> new ArrayList <>()). add ( root . right . val ); g . computeIfAbsent ( root . right . val , k -> new ArrayList <>()). add ( root . val ); } dfs ( root . left ); dfs ( root . right ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map < int , vector < int >> g ; int amountOfTime ( TreeNode * root , int start ) { dfs ( root ); queue < int > q { { start } }; unordered_set < int > vis ; int ans = - 1 ; while ( q . size ()) { ++ ans ; for ( int n = q . size (); n ; -- n ) { int i = q . front (); q . pop (); vis . insert ( i ); for ( int j : g [ i ]) { if ( ! vis . count ( j )) { q . push ( j ); } } } } return ans ; } void dfs ( TreeNode * root ) { if ( ! root ) return ; if ( root -> left ) { g [ root -> val ]. push_back ( root -> left -> val ); g [ root -> left -> val ]. push_back ( root -> val ); } if ( root -> right ) { g [ root -> val ]. push_back ( root -> right -> val ); g [ root -> right -> val ]. push_back ( root -> val ); } dfs ( root -> left ); dfs ( root -> right ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def amountOfTime ( self , root : Optional [ TreeNode ], start : int ) -> int : def dfs ( root ): if root is None : return if root . left : g [ root . val ]. append ( root . left . val ) g [ root . left . val ]. append ( root . val ) if root . right : g [ root . val ]. append ( root . right . val ) g [ root . right . val ]. append ( root . val ) dfs ( root . left ) dfs ( root . right ) g = defaultdict ( list ) dfs ( root ) vis = set () q = deque ([ start ]) ans = - 1 while q : ans += 1 for _ in range ( len ( q )): i = q . popleft () vis . add ( i ) for j in g [ i ]: if j not in vis : q . append ( j ) return ans
```