[Python] DFS Easy to Understand with Comments
Intuition\n\nMy idea was to find the lowest apple on each branch of the root and add the distance from the lowest apple to the root. \n\n\n\n\nFor example, imag
**Intuition**\n\nMy idea was to find the lowest apple on each branch of the root and add the distance from the lowest apple to the root. \n\n![image](https://assets.leetcode.com/users/smolarek9/image_1589083348.png)\n\n\nFor example, imagine you only have a tree that looks like this (image above) where there are only three nodes and only the left node of the root is an apple. You will have to check if an apple is found from the left branch and how far it is from the root. We would have to add the distance that we traveled eventually. \n\nFor the right branch, since the apple is not found, we won\'t have to add any distance since we won\'t even try to travel to that branch.\n\nWe can perform a postorder traversal to pass-up the information of the node in a bottom-up manner. If a node is a leaf and an apple, that is the base case; we return the information that the apple has been found. In the upper node, we get the information from the bottom and add the distance from the lowest apple to the child node (0 in the diagram since that is the lowest apple) plus 2 (since we have to travel to and from that node) and the information that the apple was found in this branch to the upper node.\n\nEventually, the root node will return the information of how many steps we need to travel to collect all apples in the tree.\n\n**Code**\n\n```\nInfo = collections.namedtuple(\'Info\', (\'found\', \'dist\'))\n\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        \n        # build an adjacency list to represent the tree using `edges`\n        tree = collections.defaultdict(list)\n\t\t\n\t\t# You don\'t need to make it undirected since the structure represents a tree\n        for u, v in edges:\n            tree[u].append(v)\n        \n        # A recursive helper function that find the lowest apple and passes\n        # the information (is apple found, distance from the lowest apple to the current node)\n        # to the upper node\n        \n        def traverse(node):\n            if node not in tree:\n                return Info(hasApple[node], 0)\n            curr_dist, apple_found = 0, hasApple[node]\n            for child in tree[node]:\n                info = traverse(child)\n                curr_dist += 2 + info.dist if info.found else 0\n                apple_found |= info.found\n            return Info(apple_found, curr_dist)\n        \n        # Get the information from the starting vertex 0\n        return traverse(0).dist\n```\n\nTime: `O(N)` where `N = num of nodes`\nSpace: `O(N)`\n
['Depth-First Search', 'Python3']