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 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] = [a<sub>i</sub>, b<sub>i</sub>] means that exists an edge connecting the vertices a<sub>i</sub> and b<sub>i</sub>. 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.

For example:

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.

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.

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
    vector<vector<int>> adj(n);
    for (auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }

    vector<bool> visited(n, false);
    
    function<int(int)> dfs = [&](int node) {
        visited[node] = true;
        int cost = 0;

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                int neighborCost = dfs(neighbor);
                if (neighborCost > 0 || hasApple[neighbor]) {
                    cost += neighborCost + 2;
                }
            }
        }
        return cost;
    };

    return dfs(0);
}

int main() {
    int n1 = 7;
    vector<vector<int>> edges1 = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
    vector<bool> hasApple1 = {false,false,true,false,true,true,false};
    cout << "Example 1: " << minTime(n1, edges1, hasApple1) << endl; // Output: 8

    int n2 = 7;
    vector<vector<int>> edges2 = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
    vector<bool> hasApple2 = {false,false,true,false,false,true,false};
    cout << "Example 2: " << minTime(n2, edges2, hasApple2) << endl; // Output: 6

    int n3 = 7;
    vector<vector<int>> edges3 = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
    vector<bool> hasApple3 = {false,false,false,false,false,false,false};
    cout << "Example 3: " << minTime(n3, edges3, hasApple3) << endl; // Output: 0

    return 0;
}

Explanation:

1. Build Adjacency List:

   • The edges vector is used to construct an adjacency list adj representing the tree. Each index in adj corresponds to a node, and the vector at that index stores the node's neighbors.

2. Depth-First Search (DFS):

   • A recursive DFS function is defined to traverse the tree.
   • The visited vector is used to keep track of visited nodes to avoid cycles.
   • The DFS function returns the cost (time) to collect apples from the current node's subtree and return to the current node.

3. Base Case and Recursive Step:

   • The DFS marks the current node as visited.
   • It iterates through each neighbor of the current node. If a neighbor hasn't been visited, it recursively calls DFS on that neighbor.
   • If the recursive call returns a cost greater than 0 (meaning there are apples in the neighbor's subtree) or if the neighbor itself has an apple, it adds the neighbor's cost plus 2 (for the cost of going to the neighbor and returning) to the total cost.

4. Starting the DFS:

   • The DFS is initiated from vertex 0.

5. Returning the Result:

   • The function returns the total cost calculated by the DFS.

Big(O) Run-time Analysis:

The run-time complexity is O(N), where N is the number of nodes in the tree. This is because the DFS visits each node once, and for each node, it iterates through its neighbors. The adjacency list allows us to find the neighbors of each node in O(1) time on average. Therefore, the overall complexity is proportional to the number of nodes and edges in the tree, which is O(N) since it's a tree.

Big(O) Space Usage Analysis:

The space complexity is O(N), where N is the number of nodes in the tree. This is due to the following:

• Adjacency List: The adjacency list adj takes O(N) space to store the graph.
• Visited Vector: The visited vector takes O(N) space to keep track of visited nodes.
• Recursion Stack: In the worst case (a skewed tree), the recursion stack can grow to a depth of N, taking O(N) space.

Edge Cases:

1. Empty Tree (n = 0): The code should handle an empty tree gracefully, ideally returning 0.
2. Single Node Tree (n = 1): If there's only one node, the code should return 0 if the node doesn't have an apple, and it's already at the starting node.
3. No Apples: If no nodes have apples, the code should return 0.
4. Disconnected Graph: The problem states it's a tree, so this shouldn't occur. But if the graph is disconnected, the DFS will only explore the connected component containing node 0, potentially missing apples in other components.
5. Large Tree: For very large trees (n close to 10^5), it's important to ensure that the recursion depth doesn't exceed the stack size limit. While C++ usually handles reasonably deep recursion, languages with stricter limits might require iterative approaches.

This code provides an efficient solution to collect apples in a tree, considering the time to travel and ensuring all apples are collected while starting and ending at vertex 0.