Find the last marked nodes in tree

Tree Depth-First Search

55.9% acceptance

Mar 31, 2026

There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree. Initially, all nodes are unmarked. After every second, you mark all unmarked nodes which have at least one marked node adjacent to them. Return an array nodes where nodes[i] is the last node to get marked in the tree, if you mark node i at time t = 0. If nodes[i] has multiple answers for any node i, you can choose any one answer.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn last_marked_nodes(edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = edges.len() + 1;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let u = e[0] as usize;
      let v = e[1] as usize;
      adj[u].push(v);
      adj[v].push(u);
    }

    let bfs = |start: usize| -> (Vec<i32>, usize) {
      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() {
        if dist[u] > dist[farthest] {
          farthest = u;
        }
        for &v in &adj[u] {
          if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
          }
        }
      }
      (dist, farthest)
    };

    let (_, a) = bfs(0);
    let (dist_a, b) = bfs(a);
    let (dist_b, _) = bfs(b);

    (0..n)
      .map(|i| {
        if dist_a[i] >= dist_b[i] {
          a as i32
        } else {
          b as i32
        }
      })
      .collect()
  }
}