JAVA | DFS | Map / List | Commented explanation ✅
Please Upvote :D\njava []\nclass Solution {\n    // globally declaring the adjacency map\n    private Map<Integer, List<Integer>> adj;\n    public int minTime(i
# Please Upvote :D\n``` java []\nclass Solution {\n    // globally declaring the adjacency map\n    private Map<Integer, List<Integer>> adj;\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        // if there is only 1 node, there will be no edges\n        // hence no travelling to collect apples and no consuming time\n        if (n == 1) {\n            return 0;\n        }\n\n        adj = new HashMap<>();  // initialising the adjacecny map\n        // populate the adjacency map\n        for (int[] e : edges) {\n            if (!adj.containsKey(e[0])) {\n                adj.put(e[0], new ArrayList<>());\n            }\n            if (!adj.containsKey(e[1])) {\n                adj.put(e[1], new ArrayList<>());\n            }\n            adj.get(e[0]).add(e[1]);\n            adj.get(e[1]).add(e[0]);\n        }\n\n        // call the dfs\n        return dfs(0, -1, hasApple);\n    }\n\n    public int dfs(int curr, int parent, List<Boolean> hasApple) {\n        // we basically call the dfs for every child connected to our current node\n        // then a particular child becomes the current node, and the previous current node becomes the parent for that child\n        // this goes on and from depth we keep getting the consumed time and come back to top\n\n        int timeAtCurrentNode = 0;   // variable to store the time consumed below our current node\n        // check for every child that are connected to the current node\n        for (int child : adj.get(curr)) {\n            if (child == parent) {  // we don\'t want to go back to the parent node, we want to go down below\n                continue;\n            }\n            // call the dfs for the child, current node becomes the new parent\n            // it will fetch us the time if there is an apple down below our child\n            int timeFromChild = dfs(child, curr, hasApple);\n            // timeFromChild > 0 means we found an apple below the child\n            // hasApple if true at current child means apple is present at current child as well\n            if (timeFromChild > 0 || hasApple.get(child)) {\n                // so we add 2 (1 (going down) + 1 (coming back)) and timeFromChild (time taken to collect apples below child)\n                // to the total time of our current node\n                timeAtCurrentNode += (2 + timeFromChild);\n            }\n        }\n\n        // return the time taken\n        return timeAtCurrentNode;\n    }\n}\n\n// TC: O(v + e), SC: O(v + e)\n```\n**NOTE:**\n*We don\'t necessarily need to have a visited array, because its a tree because instead we have put a check so that we don\'t visit the parent node again while calling dfs for the child nodes of a particular node.*\n\n---\n##### Using an adjacency List array instead of a map (Faster):\n\n``` java []\nclass Solution {\n    // globally declaring the adjacency list\n    private List<Integer>[] adj;\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        if (n == 1) {   // not necessary when using a list\n            return 0;\n        }\n\n        adj = new List[n];  // initialising the adjacency list\n        for (int i = 0; i < n; i++) {\n            adj[i] = new ArrayList<>();\n        }\n        // populating the adjacency list\n        for (int[] e : edges) {\n            adj[e[0]].add(e[1]);\n            adj[e[1]].add(e[0]);\n        }\n\n        return dfs(0, -1, hasApple);\n    }\n\n    public int dfs(int currNode, int parent, List<Boolean> hasApple) {\n        int timeAtCurrentNode = 0;\n        for (int child : adj[currNode]) {\n            if (child == parent) {\n                continue;\n            }\n\n            int timeFromChild = dfs(child, currNode, hasApple);\n            if (timeFromChild > 0 || hasApple.get(child)) {\n                timeAtCurrentNode += (2 + timeFromChild);\n            }\n        }\n\n        return timeAtCurrentNode;\n    }\n}\n\n// TC: O(v + e), SC: O(v + e)\n```
['Hash Table', 'Tree', 'Depth-First Search', 'Java']