Closest node to path in tree

Array Tree Depth-First Search Breadth-First Search

62.3% acceptance

Mar 31, 2026

139

You are given a positive integer n representing the number of nodes in a tree, numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges of length n - 1, where edges[i] = [node1i, node2i] denotes that there is a bidirectional edge connecting node1i and node2i in the tree. You are given a 0-indexed integer array query of length m where query[i] = [starti, endi, nodei] means that for the ith query, you are tasked with finding the node on the path from starti to endi that is closest to nodei. Return an integer array answer of length m, where answer[i] is the answer to the ith query.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn closest_node(n: i32, edges: Vec<Vec<i32>>, query: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
    }
    let mut dist = vec![vec![0i32; n]; n];
    for src in 0..n {
      let mut visited = vec![false; n];
      let mut queue = std::collections::VecDeque::new();
      visited[src] = true;
      queue.push_back(src);
      while let Some(u) = queue.pop_front() {
        for &v in &adj[u] {
          if !visited[v] {
            visited[v] = true;
            dist[src][v] = dist[src][u] + 1;
            queue.push_back(v);
          }
        }
      }
    }
    query.iter().map(|q| {
      let (start, end, node) = (q[0] as usize, q[1] as usize, q[2] as usize);
      let mut parent = vec![usize::MAX; n];
      let mut visited = vec![false; n];
      let mut queue = std::collections::VecDeque::new();
      visited[start] = true;
      queue.push_back(start);
      while let Some(u) = queue.pop_front() {
        if u == end { break; }
        for &v in &adj[u] {
          if !visited[v] {
            visited[v] = true;
            parent[v] = u;
            queue.push_back(v);
          }
        }
      }
      let mut path = vec![];
      let mut cur = end;
      loop {
        path.push(cur);
        if cur == start { break; }
        cur = parent[cur];
      }
      let mut best = path[0];
      let mut best_dist = dist[node][path[0]];
      for &p in &path {
        if dist[node][p] < best_dist {
          best_dist = dist[node][p];
          best = p;
        }
      }
      best as i32
    }).collect()
  }
}