2385. Amount of Time for Binary Tree to Be Infected LeetCode Solution

In this guide, you will get 2385. Amount of Time for Binary Tree to Be Infected LeetCode Solution with the best time and space complexity. The solution to Amount of Time for Binary Tree to Be Infected problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Amount of Time for Binary Tree to Be Infected solution in C++
4. Amount of Time for Binary Tree to Be Infected solution in Java
5. Amount of Time for Binary Tree to Be Infected solution in Python
6. Additional Resources

Problem Statement of Amount of Time for Binary Tree to Be Infected

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2385. Amount of Time for Binary Tree to Be Infected LeetCode Solution in C++

class Solution {
 public:
  int amountOfTime(TreeNode* root, int start) {
    int ans = -1;
    const unordered_map<int, vector<int>> graph = getGraph(root);
    queue<int> q{{start}};
    unordered_set<int> seen{start};

    for (; !q.empty(); ++ans) {
      for (int sz = q.size(); sz > 0; --sz) {
        const int u = q.front();
        q.pop();
        if (!graph.contains(u))
          continue;
        for (const int v : graph.at(u)) {
          if (seen.contains(v))
            continue;
          q.push(v);
          seen.insert(v);
        }
      }
    }

    return ans;
  }

 private:
  unordered_map<int, vector<int>> getGraph(TreeNode* root) {
    unordered_map<int, vector<int>> graph;
    queue<pair<TreeNode*, int>> q{{{root, -1}}};  // (node, parent)

    while (!q.empty()) {
      const auto [node, parent] = q.front();
      q.pop();
      if (parent != -1) {
        graph[parent].push_back(node->val);
        graph[node->val].push_back(parent);
      }
      if (node->left)
        q.emplace(node->left, node->val);
      if (node->right)
        q.emplace(node->right, node->val);
    }

    return graph;
  }
};
/* code provided by PROGIEZ */

2385. Amount of Time for Binary Tree to Be Infected LeetCode Solution in Java

class Solution {
  public int amountOfTime(TreeNode root, int start) {
    int ans = -1;
    Map<Integer, List<Integer>> graph = getGraph(root);
    Queue<Integer> q = new ArrayDeque<>(List.of(start));
    Set<Integer> seen = new HashSet<>(Arrays.asList(start));

    for (; !q.isEmpty(); ++ans) {
      for (int sz = q.size(); sz > 0; --sz) {
        final int u = q.poll();
        if (!graph.containsKey(u))
          continue;
        for (final int v : graph.get(u)) {
          if (seen.contains(v))
            continue;
          q.offer(v);
          seen.add(v);
        }
      }
    }

    return ans;
  }

  private Map<Integer, List<Integer>> getGraph(TreeNode root) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    // (node, parent)
    Queue<Pair<TreeNode, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(root, -1)));

    while (!q.isEmpty()) {
      Pair<TreeNode, Integer> pair = q.poll();
      TreeNode node = pair.getKey();
      final int parent = pair.getValue();
      if (parent != -1) {
        graph.putIfAbsent(parent, new ArrayList<>());
        graph.putIfAbsent(node.val, new ArrayList<>());
        graph.get(parent).add(node.val);
        graph.get(node.val).add(parent);
      }
      if (node.left != null)
        q.add(new Pair<>(node.left, node.val));
      if (node.right != null)
        q.add(new Pair<>(node.right, node.val));
    }

    return graph;
  }
}
// code provided by PROGIEZ

2385. Amount of Time for Binary Tree to Be Infected LeetCode Solution in Python

class Solution:
  def amountOfTime(self, root: TreeNode | None, start: int) -> int:
    ans = -1
    graph = self._getGraph(root)
    q = collections.deque([start])
    seen = {start}

    while q:
      ans += 1
      for _ in range(len(q)):
        u = q.popleft()
        if u not in graph:
          continue
        for v in graph[u]:
          if v in seen:
            continue
          q.append(v)
          seen.add(v)

    return ans

  def _getGraph(self, root: TreeNode | None) -> dict[int, list[int]]:
    graph = collections.defaultdict(list)
    q = collections.deque([(root, -1)])  # (node, parent)

    while q:
      node, parent = q.popleft()
      if parent != -1:
        graph[parent].append(node.val)
        graph[node.val].append(parent)
      if node.left:
        q.append((node.left, node.val))
      if node.right:
        q.append((node.right, node.val))

    return graph
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.