Tree diameter

Tree Depth-First Search Breadth-First Search Graph Theory Topological Sort

61.3% acceptance

Mar 31, 2026

904

No description available.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn tree_diameter(edges: Vec<Vec<i32>>) -> i32 {
    if edges.is_empty() { return 0; }
    let n = edges.len() + 1;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      adj[e[0] as usize].push(e[1] as usize);
      adj[e[1] as usize].push(e[0] as usize);
    }
    // BFS from any node, find farthest, BFS from farthest
    let bfs = |start: usize| -> (usize, i32) {
      let mut dist = vec![-1i32; n];
      dist[start] = 0;
      let mut queue = std::collections::VecDeque::new();
      queue.push_back(start);
      let mut farthest = start;
      while let Some(u) = queue.pop_front() {
        for &v in &adj[u] {
          if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            if dist[v] > dist[farthest] { farthest = v; }
            queue.push_back(v);
          }
        }
      }
      (farthest, dist[farthest])
    };
    let (far, _) = bfs(0);
    let (_, diameter) = bfs(far);
    diameter
  }
}