Find diameter endpoints of a tree

Tree Breadth-First Search Graph Theory

68.9% acceptance

Mar 31, 2026

You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. A node is called special if it is an endpoint of any diameter path of the tree. Return a binary string s of length n, where s[i] = '1' if node i is special, and s[i] = '0' otherwise. A diameter path of a tree is the longest simple path between any two nodes. A tree may have multiple diameter paths. An endpoint of a path is the first or last node on that path.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_special_nodes(n: i32, edges: Vec<Vec<i32>>) -> String {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (a, b) = (e[0] as usize, e[1] as usize);
      adj[a].push(b);
      adj[b].push(a);
    }
    let bfs = |start: usize| -> Vec<i32> {
      let mut dist = vec![-1i32; n];
      dist[start] = 0;
      let mut q = std::collections::VecDeque::new();
      q.push_back(start);
      while let Some(u) = q.pop_front() {
        for &v in &adj[u] {
          if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            q.push_back(v);
          }
        }
      }
      dist
    };
    let d0 = bfs(0);
    let u = d0.iter().enumerate().max_by_key(|&(_, &d)| d).unwrap().0;
    let du = bfs(u);
    let v = du.iter().enumerate().max_by_key(|&(_, &d)| d).unwrap().0;
    let dv = bfs(v);
    let diameter = du[v];
    let mut result = vec![b'0'; n];
    for i in 0..n {
      if du[i].max(dv[i]) == diameter {
        result[i] = b'1';
      }
    }
    String::from_utf8(result).unwrap()
  }
}