> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/minimum-time-to-collect-all-apples-in-a-tree.md).

# Minimum Time to Collect All Apples in a Tree

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 in order 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] = [fromi, toi]` means that exists an edge connecting the vertices `fromi` and `toi`. 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.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_1.png)

```
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8 
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.  
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_2.png)

```
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.  
```

**Example 3:**

```
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0
```

**Constraints:**

* `1 <= n <= 10^5`
* `edges.length == n-1`
* `edges[i].length == 2`
* `0 <= fromi, toi <= n-1`
* `fromi < toi`
* `hasApple.length == n`

```java
class Solution {
    public int count(HashMap<Integer, ArrayList<Integer>> tree, HashMap<Integer, Boolean> map, int root) {
        if (tree.get(root) == null) {
            if (map.get(root))
                return 0;
            return -1;
        }
        int ans = 0;
        for (int x : tree.get(root)) {
            int temp = count(tree, map, x);
            if (temp != -1)
                ans += 2 + temp;
        }
        if (ans == 0 && !map.get(root))
            return -1;
        return ans;
    }

    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < hasApple.size(); i++)
            map.put(i, hasApple.get(i));
        HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            if (tree.containsKey(edges[i][0]))
                tree.get(edges[i][0]).add(edges[i][1]);
            else {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(edges[i][1]);
                tree.put(edges[i][0], arr);
            }
        }
        int ans = count(tree, map, 0);
        return ans == -1 ? 0 : ans;
    }
}
```