Detailed Explanation - You don't need HashMaps || BEATS 100% || DFS
Intuition with HashMaps\nThe intuition behind this problem is to find the minimum distance between the tree\'s root and all the nodes that have apples.\n\nThe p
# Intuition with HashMaps\nThe intuition behind this problem is to find the minimum distance between the tree\'s root and all the nodes that have apples.\n\nThe problem can be solved by traversing the tree and keeping track of the distance of all the nodes with apples from the root.\n\nThe tree is represented by edges and the direction is from parent to child.\n\nWe have to traverse the tree and add the distance of each node with apple to the root node.\n\nWe can use a hashmap ***childToParent*** to create a parent-child relationship among nodes, which will be used to traverse the tree in a depth-first search fashion. By using this hashmap, we can trace the path from any node to the root node.\n\nAdditionaly, use a set to keep track of the visited nodes. Then, for each node that has an apple, the distance from the current node to the root node is calculated. It is done by iteratively traversing the tree by following the parent-child relationships and incrementing the distance for each step.\n\nTo calculate the minimum time required, the distance can be multiplied by 2, because for each apple we need to move from root node to that apple and then again from apple to root node.\n\nOverall, the algorithm works by traversing the tree and keeping track of the distance to the root node for all nodes with apples, and returning the sum of these distances as the minimum time needed to collect all the apples in the tree.\n\n# Approach\n1. Create a hashmap ***childToParent*** to store the parent-child relationship for all nodes in the tree using the edges array.\n\n> **Here its not a tree(since my first attempt failed the test case where edges = [[0,2],[0,3].[1,2]] and hasApples = [false, true, false, false]), consider it as a graph construction, that is why I had to put the condition where a child has multiple parents? So, its a graph not a tree.**\n\n2. Initialize a variable ***time*** to keep track of the minimum time needed to collect all apples.\n\n3. Create a set ***visited*** to keep track of the nodes that have been visited.\n\n4. Iterate through all the nodes in the "tree" and for each node with an apple, call the ***findPathLength*** helper function.\n\n5. In the ***findPathLength*** function, initialize a variable ***length*** to keep track of the path length from the current node to the root.\n\n6. Traverse the "tree" from the current node to the root by following the parent-child relationships stored in the ***childToParent*** hashmap. For each step, add the current node to the set of visited nodes, update the current node to its parent node, and increment the length of the path.\n\n7. Return the length of the path.\n\n8. In the main function, add the result of the findPathLength function to the time variable, multiplied by 2 to account for the movement to and from the node.\n\n9. Return the time as the final result, which represents the minimum time needed to collect all the apples in the tree.\n\n\n\n\n\n# Complexity\n- Time complexity:\nThe time complexity of the algorithm is O(n), where n is the number of nodes in the tree.\n\n- Space complexity:\nSpace complexity is O(n) as we are using hashmap and set data structure which have n nodes, it may be useful to keep in mind the trade-off between time and space complexity.\n\n# Code\n```\nclass Solution {\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        int time = 0;\n        Set<Integer> visited = new HashSet<>();\n        HashMap<Integer, Integer> childToParent = new HashMap<>();\n        for(int[] edge : edges){\n            if(childToParent.containsKey(edge[1])){\n                childToParent.put(edge[0], edge[1]);\n            }else{\n                childToParent.put(edge[1], edge[0]);\n            }\n        }\n        for(int i = 0; i < n; i++){\n            if(hasApple.get(i)){\n                time += 2*findPathLength(childToParent, visited, i);\n            }\n        }\n        return time;\n    }\n    private int findPathLength(HashMap<Integer, Integer> goUp, Set<Integer> visited, int node){\n        int length = 0;\n        while(node != 0 && !visited.contains(node)){\n            visited.add(node);\n            node = goUp.get(node);\n            length += 1;\n        }\n        return length;\n    }\n}\n\n```\n# UPDATE without using HashMaps:\nInstead of using a hash set for the ***visited*** set, we can use a boolean array. This will not only decrease the time required for lookups, but also decrease the amount of space needed to store the visited set. The rest of the code will remain the same. Please refer to the following code:\n```\nclass Solution {\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        HashMap<Integer, Integer> graph = new HashMap<>();\n        boolean[] visited = new boolean[n];\n        int time = 0;\n        for(int[] edge : edges){\n            if(graph.containsKey(edge[1])){\n                graph.put(edge[0], edge[1]);\n            }else{\n                graph.put(edge[1], edge[0]);\n            }\n        }\n        for(int i = 0; i < n; i++){\n            if(hasApple.get(i)){\n                time += 2*distanceFromRoot(i, graph, visited);\n            }\n        }\n        return time;\n    }\n    private int distanceFromRoot(int node, HashMap<Integer, Integer> graph, boolean[] visited){\n        int distance = 0;\n        while(node != 0 && !visited[node]){\n            visited[node] = true;\n            node = graph.get(node);\n            distance++;\n        }\n        return distance;\n    }\n}\n\n```\n# UPDATE 2:\n## Borrowed approach from a different LeetCode user I don\'t know, but here\'s the explanation and code for the same.\n\nUse an array to store the parent-child relationships in a **"tree-like"** structure. Create an array called ***parentOf*** of size ***n***, which represents the number of nodes in the tree. The initial value of each element in the array is set to -2, which indicates that the node has no parent assigned yet.\n\nThe code then sets the parent of the first node (index 0) to -1, which is a special value indicating that it is the root of the tree. \n\nThe code then iterates over a list of edges, which represent the connections between the nodes in the tree. For each edge, it checks if the starting node (edge[0]) has a parent assigned yet. If it does not have a parent assigned, it sets the parent of that node to be the end node (edge[1]). If it does have a parent assigned, it sets the parent of the end node (edge[1]) to be the starting node (edge[0]).\n\napproach is efficient in terms of space complexity as it uses only array of fixed size n where n is the number of nodes. It has O(n) time complexity where n is the number of edges, as it iterates over all the edges and assigns parent to each node.\n\nThis approach is very simple and easy to understand and also efficient as it reduces the space complexity. \n```\nclass Solution {\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        int[] parentOf = new int[n];\n        for(int i = 0; i < n; i++){\n            parentOf[i] = -2;\n        }\n        parentOf[0] = -1;\n        boolean[] visited = new boolean[n];\n        int time = 0;\n        for(int[] edge : edges){   \n            if(parentOf[edge[0]] == -2){\n                parentOf[edge[0]] = edge[1];\n                \n            }else{\n                parentOf[edge[1]] = edge[0];\n            }\n        }\n        for(int i = 0; i < n; i++){\n            int node = i;\n            if(hasApple.get(i)){\n                while(node != 0 && !visited[node]){\n                    visited[node] = true;\n                    node = parentOf[node];\n                    time += 2;\n                }\n            }\n        }\n        return time;\n    }\n}\n\n```
['Hash Table', 'Java']