😯 Intuitive & Readable: Recursive, OO + Functional, Depth-First Tree Traversal Edge Count [Python]
Please upvote if you find this post useful. \uD83D\uDE4F\n\n---\n\n# Intuition\n\nThe essence of this problem can be simply stated as:\n\n> Count the number of 
<i><span style="color:dodgerblue">Please upvote if you find this post useful.</span> \uD83D\uDE4F</i>\n\n---\n\n# Intuition\n\nThe essence of this problem can be simply stated as:\n\n> Count the number of edges that need to be traversed to reach all apples.\n\nThe requirement to count the "time" including "coming back" simply requires doubling the number of edges found.\n\n# Approach\n\nThe problem can easily be broken down such that the solution for any node / subtree is a function of the results for its child nodes / subtrees.\n\nWhen looking at the root of any subtree, any immediate child which has an apple itself *or* any edges beneath it leading to apples, adds 1 to the total (counting the edge to the child), *as well as* the count of edges leading to apples in *the child\'s* subtree. Using this recursive definition of the count makes it relatively simple to write a recursive function defining the count for a subtree. I\'ve expressed this as a functional one-liner in Python using `for` comprehensions and `sum()`.\n\n(Note: At first the `Node` class had `children` instead of `neighbours`, and `count_edges_leading_to_apples()` was simpler due to not having the `from_node` parameter. However, one of the test cases connected a child in a non-child fashion from the perspective of the root (which is fine because, as the problem definition says, the tree is non-directional). That resulted in the need to store bi-directional edges, which then leads to needing the `from_node` parameter to avoid walking back up the tree.)\n\n# Complexity\n- Time complexity: $$O(n)$$ ~ I don\'t believe there\'s any way to avoid traversing the whole tree with this problem, as we need to know whether any leaf has an apple.\n\n- Space complexity: $$O(n)$$ ~ From the creation of `Node` objects with their `neighbours` lists.\n\n# Code\n```\n\nclass Node:\n    has_apple: bool\n    neighbours: List[\'Node\']\n\n    def __init__(self, has_apple: bool):\n        self.has_apple = has_apple\n        self.neighbours = []\n\n    def count_edges_leading_to_apples(self, from_node: Optional[\'Node\'] = None) -> int:\n        return sum(\n            (subtree_count + 1) if subtree_count != 0 or child.has_apple else 0\n            for child, subtree_count in ((n, n.count_edges_leading_to_apples(self))\n                                         for n in self.neighbours if n is not from_node)\n        )\n\n\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        # Create a tree of bi-directionally connected Nodes:\n        nodes = [Node(ha) for ha in hasApple]\n        for a, b in edges:\n            na, nb = nodes[a], nodes[b]\n            na.neighbours.append(nb)\n            nb.neighbours.append(na)\n\n        # Calculate the count of edges from the root, x by 2 for "coming back"\n        return nodes[0].count_edges_leading_to_apples() * 2\n\n```\n\nIf you find that functional implementation of `count_edges_leading_to_apples()` a little hard to read, here\'s the equivalent procedural version:\n```\n    def count_edges_leading_to_apples(self, from_node: Optional[\'Node\'] = None) -> int:\n        result = 0\n        for child_node in self.neighbours:\n            if child_node is not from_node:\n                subtree_count = child_node.count_edges_leading_to_apples(from_node=self)\n                if subtree_count != 0 or child_node.has_apple:\n                    result += subtree_count + 1\n        return result\n```
['Tree', 'Depth-First Search', 'Recursion', 'Python3']