Amount of time for binary tree to be infected

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

65.1% acceptance

Feb 25, 2026

3217

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }


use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn amount_of_time(root: Option<Rc<RefCell<TreeNode>>>, start: i32) -> i32 {
    use std::collections::{HashMap, VecDeque, HashSet};
    let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, parent: i32, adj: &mut HashMap<i32, Vec<i32>>) {
      if let Some(n) = node {
        let n = n.borrow();
        adj.entry(n.val).or_default();
        if parent != -1 {
          adj.entry(n.val).or_default().push(parent);
          adj.entry(parent).or_default().push(n.val);
        }
        dfs(&n.left, n.val, adj);
        dfs(&n.right, n.val, adj);
      }
    }
    dfs(&root, -1, &mut adj);
    let mut visited: HashSet<i32> = HashSet::new();
    let mut queue = VecDeque::new();
    queue.push_back((start, 0i32));
    visited.insert(start);
    let mut ans = 0;
    while let Some((u, t)) = queue.pop_front() {
      ans = t;
      for &v in adj.get(&u).unwrap_or(&vec![]) {
        if !visited.contains(&v) {
          visited.insert(v);
          queue.push_back((v, t + 1));
        }
      }
    }
    ans
  }
}