hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Minimum Time to Collect All Apples in a Tree


  • Approach:

    1. The intuition is - when I am in a node, I need to see the child if anyone has any apples or not.

    2. If any child has any apples then I mark the current node as a privileged one saying that I also have apples.

    3. Now for each node having apples contribute two 2 seconds. Similarly, each privileged node will also contribute 2 seconds each.

    4. We can solve this using DFS.

    5. Starting from 0, try to access all the child nodes. Flag nodes are visited when trying to access the child.

    6. If a child node is already not visited, then like we do in Post-Order traversal traverse the subtrees first.

    7. With the results achieved from the subtree, we will also add 2 seconds for each child having apples.

    8. Now when we complete traversing all the child nodes, if we have some seconds contributed by the child, we will mark the parent node having apples, that is, hasApple[parent]=true.

    9. We will keep doing this until we complete traversing the whole tree.

    10. At last, we will return the total seconds.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N) + Stack


Code [C++]

class Solution {

public:


int solve(int node, vector<vector<int>> & graph, vector<bool>&hasApple, vector<bool>&visited){

int cnt = 0;

visited[node] = true;

for(int i=0; i<graph[node].size(); i++){

int child = graph[node][i];

if(visited[child]) continue;

cnt += solve(child, graph, hasApple, visited);

if(hasApple[child]) cnt += 2;

}

if(cnt) hasApple[node] = true;

return cnt;

}


int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {

vector<vector<int>>graph(n);

vector<bool>visited(n, false);

for(int i=0; i<edges.size(); i++){

int u = edges[i][0], v = edges[i][1];

graph[u].push_back(v);

graph[v].push_back(u);

}

return solve(0, graph, hasApple, visited);

}

};