Minimum time to collect all apples in a tree

Hash Table Tree Depth-First Search Breadth-First Search

63.6% acceptance

Feb 25, 2026

3849

333

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex. The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_time(n: i32, edges: Vec<Vec<i32>>, has_apple: Vec<bool>) -> i32 {
    let n = n as usize;
    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);
    }
    fn dfs(node: usize, parent: usize, adj: &Vec<Vec<usize>>, has_apple: &Vec<bool>) -> i32 {
      let mut cost = 0;
      for &child in &adj[node] {
        if child != parent {
          let child_cost = dfs(child, node, adj, has_apple);
          if child_cost > 0 || has_apple[child] {
            cost += child_cost + 2;
          }
        }
      }
      cost
    }
    dfs(0, n, &adj, &has_apple)
  }
}