# Minimum Time to Collect All Apples in a Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-collect-all-apples-in-a-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree
**Companies:** [Myntra](https://scaleengineer.com/companies/myntra)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-time-to-collect-all-apples-in-a-tree/image0.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.glich.co/dsa/minimum-time-to-collect-all-apples-in-a-tree/image1.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 <= 105`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `0 <= ai < bi <= n - 1`
* `hasApple.length == n`

# Approaches
## Brute-Force by Finding Paths to Each Apple
This approach directly simulates the process of collecting apples. It first identifies all nodes with apples. Then, for each of these nodes, it determines the path from the root (vertex 0). By combining all such paths, it identifies the set of all unique edges that must be traversed. The total time is simply twice the number of these unique edges, accounting for the round trip.
**Time:** O(N + k * H), where N is the number of vertices, k is the number of apples, and H is the height of the tree. In the worst-case scenario (a skewed tree where k and H are both O(N)), the complexity becomes O(N^2). · **Space:** O(N), where N is the number of vertices. This is for storing the adjacency list, the `parent` array, the BFS queue, and the `HashSet` of required edges.
**Pros:** The logic is straightforward and easy to understand as it directly models the problem statement.; It correctly solves the problem for smaller inputs.
**Cons:** The time complexity is quadratic in the worst-case, which is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.; It's more complex to implement compared to the optimal DFS solution, requiring multiple data structures (adjacency list, parent array, queue for BFS, and a set for edges).
### Explanation
First, we need a way to represent the tree. An adjacency list is a suitable choice, built from the given `edges`. To find the path from the root to each apple, we can pre-compute the parent of each node in the path from the root. A Breadth-First Search (BFS) starting from vertex 0 is perfect for this. 

Once we have the `parent` array, we can iterate through all nodes. If a node `i` contains an apple, we trace its path back to the root by repeatedly moving to its parent (`curr = parent[curr]`) until we reach vertex 0. During this traversal, we add each edge to a `HashSet`. Using a `HashSet` automatically handles the counting of unique edges. 

Finally, the size of the `HashSet` gives us the number of unique edges on the required paths. Since every such edge must be traversed once to go away from the root and once to come back, the total time is `2 * set.size()`.

```java
import java.util.*;

class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    queue.offer(v);
                }
            }
        }

        Set<Long> requiredEdges = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (hasApple.get(i)) {
                int curr = i;
                while (curr != 0) {
                    int p = parent[curr];
                    long u = Math.min(p, curr);
                    long v = Math.max(p, curr);
                    requiredEdges.add(u * n + v);
                    curr = p;
                }
            }
        }

        return requiredEdges.size() * 2;
    }
}
```
### Algorithm
- Build an adjacency list representation of the tree from the `edges` array.
- Perform a Breadth-First Search (BFS) starting from vertex 0 to compute the parent of each node in the shortest path from the root. Store these in a `parent` array.
- Initialize an empty `HashSet` to store the unique edges that must be traversed.
- Iterate through all vertices. If a vertex `i` has an apple (`hasApple[i]` is true):
  - Trace the path from `i` back to the root (vertex 0) using the `parent` array.
  - For each edge on this path, add a canonical representation of the edge to the `HashSet` to ensure uniqueness.
- The total time is the number of unique edges in the set multiplied by 2, as each edge must be traversed down and back up.

## Optimal Single-Pass DFS
This optimal approach uses a single Depth-First Search (DFS) traversal to calculate the minimum time. The core idea is to think about the problem recursively. For any subtree, we only need to enter it if it contains an apple. The DFS function, when called on a node `u`, calculates the total time spent collecting apples within the subtrees of its children. It adds 2 seconds (for the round trip) for each edge leading to a child's subtree that must be visited.
**Time:** O(N), where N is the number of vertices. Both building the adjacency list and the DFS traversal take linear time, as each vertex and edge is visited once. · **Space:** O(N), where N is the number of vertices. O(N) is used for the adjacency list. The recursion stack for DFS can also go up to O(N) in the worst case of a skewed tree.
**Pros:** Extremely efficient, with a linear time complexity that passes all constraints.; Solves the problem in a single traversal of the tree.; The implementation is clean and concise.
**Cons:** The recursive nature of the solution might be slightly less intuitive at first glance compared to a more direct, iterative approach.
### Explanation
We can solve this problem efficiently in one pass using DFS. First, we represent the tree using an adjacency list. Then, we start a DFS from the root, vertex 0.

We define a recursive function `dfs(u, parent)` that returns the time needed to collect apples in the subtree rooted at `u` and come back to `u`. For each child `v` of `u`, we recursively call `dfs(v, u)`. Let's say this call returns `childTime`. If `childTime > 0`, it means there were apples in `v`'s subtree, and `childTime` is the time spent inside that subtree. If `hasApple.get(v)` is true, it means node `v` itself has an apple. In either of these cases, we must travel from `u` to `v`. This trip costs 2 seconds (1 to go, 1 to return), plus the `childTime` spent within `v`'s subtree. So, we add `childTime + 2` to the total time for `u`'s subtree.

If a child's subtree has no apples and the child itself doesn't have one (`childTime == 0` and `!hasApple.get(v)`), we don't need to visit it, and it contributes zero time. The final answer is the result of `dfs(0, -1)`.

```java
import java.util.*;

class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        return dfs(0, -1, adj, hasApple);
    }

    private int dfs(int u, int parent, List<List<Integer>> adj, List<Boolean> hasApple) {
        int totalTime = 0;
        for (int v : adj.get(u)) {
            if (v == parent) {
                continue;
            }
            int childTime = dfs(v, u, adj, hasApple);
            if (childTime > 0 || hasApple.get(v)) {
                totalTime += childTime + 2;
            }
        }
        return totalTime;
    }
}
```
### Algorithm
- Build an adjacency list representation of the tree from the `edges` array.
- Create a recursive Depth-First Search (DFS) function, say `dfs(currentNode, parentNode)`.
- This function will return the time required to collect all apples in the subtree of `currentNode` and return to `currentNode`.
- In the `dfs` function for node `u`:
  - Initialize a variable `subtreeTime = 0`.
  - Iterate through all neighbors `v` of `u` (excluding its parent).
  - Recursively call `childTime = dfs(v, u)`.
  - If the child's subtree contains any apples (`childTime > 0`) or if the child node `v` itself has an apple, it means we must traverse the edge `(u, v)`. Add `childTime + 2` to `subtreeTime`. The `+2` accounts for moving from `u` to `v` and back.
  - Return `subtreeTime`.
- The final answer is the result of the initial call `dfs(0, -1)`.