Easy Understanding || C++ DFS Solution
Observation : \n\n1. Every time we use an edge we will also use same edge to go in backward direction so that edge will be usedtwice.\n2. If we are at current n
**Observation** : \n\n1. Every time we use an edge we will also use same edge to go in backward direction so that edge will be used` twice`.\n2. If we are at current node and if it is a leaf node and it has apple we will use that edge to collect apple.\n3. If current node is not a leaf node then there are two cases i) If it has apple, ii) If in that node\'s subtree someone is having apple. In either of these cases we are gonna use the edge to collect apple.\n\n**Approach** : \n* We can do DFS traversal and follow above observations to implement the logic.\n\n**T.C : O(n+m)\nS.C : O(n+m)**\n\n```\nclass Solution {\npublic:\n    int dfs(vector<int> adj[],int n,int node,int prev,vector<bool> &hasApple){\n        int tree = 0;\n        for(auto &ele:adj[node]){\n            if(ele!=prev){\n                int subtree = dfs(adj,n,ele,node,hasApple);\n                tree += subtree;\n            }\n        }\n        if(adj[node].size()==1 and node!=0){\n            tree += hasApple[node];\n        }\n        else if(node!=0){\n            if(tree!=0 or hasApple[node]) tree++; \n        }\n        return tree;\n    }\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple){\n        int sz = hasApple.size();\n        vector<int> adj[sz];\n        for(auto &ele:edges){\n            adj[ele[0]].push_back(ele[1]);\n            adj[ele[1]].push_back(ele[0]);\n        }\n        int req = dfs(adj,n,0,-1,hasApple);\n        return 2*req;\n    }\n};\n```\n\nPlease Upvote if you find it helpful !!
['Tree', 'Depth-First Search', 'Graph', 'C']