Python - Recursive Post Order Traversal (DFS) Solution ✅
The idea is to first count how many nodes each node has on its left and right. This information will be helpful when we have to get the score of a node.\n\n\n\n
The idea is to first count how many nodes each node has on its left and right. This information will be helpful when we have to get the score of a node.\n\n![image](https://assets.leetcode.com/users/images/a86378d4-465d-4924-b240-db3026555930_1718258635.5966825.png)\n\nIf you look at the above example, whenever we remove any node from the tree, its score is simply the product of \n\n\tnodesOnLeft * nodesOnRight * nodesOnTop\n\t\nTo get the nodes on left and nodes on right, we can simply traverse the tree in DFS (Post Order) and then get the count and save it somewhere.\n\nFor the top, it is pretty simple. If we know how many nodes are on the left and right, we can say that the nodes on top will be - \n\n\tTotal Nodes - (nodesOnLeft + 1 + nodesOnRight)\n\nAnd well, the last thing remaining will be to find the highest score and the count of nodes with that score.\n\n```\nclass Solution:\n    \n    # Recursive DFS function\n    def dfs(self, i, parentNodes, nodeCount):\n        \n        # Base Case  (It is a leaf node)\n        if i not in parentNodes: \n            nodeCount[i] = [0,0]\n            return 1\n        \n        leftCount, rightCount = 0,0\n        \n        if len(parentNodes[i]) > 1:\n            \n            # Count of nodes in the left subtree\n            leftCount = self.dfs(parentNodes[i][0], parentNodes, nodeCount)\n\n            # Count of nodes in the right subtree\n            rightCount = self.dfs(parentNodes[i][1], parentNodes, nodeCount)\n            \n        else:\n            \n            # Count of nodes in the left subtree\n            leftCount = self.dfs(parentNodes[i][0], parentNodes, nodeCount)\n            \n        \n        # Update the dictionary\n        nodeCount[i] = [leftCount, rightCount]\n        \n        # Return the count for the previous recursive calls\n        return leftCount + 1 + rightCount\n    \n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n        \n        # Total Number of nodes\n        n = len(parents)\n        \n        # A dictionary to keep track of the parent and the children of that parent node\n        parentNodes = defaultdict(list)\n        for i in range(n): parentNodes[parents[i]].append(i)\n        \n        # First, for each node, we need to find the count of nodes in each of the subtrees rooted at children nodes\n        # A dictionary where key will be the node value and value will be a pair [leftCount, rightCount]\n        nodeCount = {}\n        \n        # Call the recursive DFS function to count the nodes\n        self.dfs(0, parentNodes, nodeCount)\n        \n        # Now, we have to find the highest score and the number of nodes with that highest score\n        highestScore = 0\n        count = 0\n        \n        # For each node\n        for i in range(n):\n            \n            # What if this node is removed along with its edges?\n            # We now have to find product of sizes of all the subtrees that are left\n            # If current node is removed, we will get at most three different subtrees\n            # One that is on the top of the node that we just removed\n            # One will be the subtree rooted at the left child of the current node\n            # One will be the subtree rooted at the right child of the current node\n            \n            # First, we check for the topCount\n            # If we know how many nodes the left and right subtrees have\n            # We can say the tree on top will have nodes = totalNodes - (leftCount + 1 + rightCount)\n            topCount = n - (nodeCount[i][0] + 1 + nodeCount[i][1])\n            \n            # Now, we check for left and right children\n            leftCount, rightCount = nodeCount[i][0], nodeCount[i][1]\n            \n            # To avoid issues due to multiplication with 0\n            if leftCount == 0: leftCount = 1\n            if rightCount == 0: rightCount = 1\n            if topCount == 0: topCount = 1\n                \n            # What is the score of the node\n            score = leftCount * rightCount * topCount\n            \n            # Check if the current score is greater than the highest score so far\n            if score > highestScore:\n                \n                # Update the highest score\n                highestScore = score\n                \n                # Rest the count\n                count = 1\n                \n            # If it is equal to the highest score, update the node count\n            elif score == highestScore: count += 1\n        \n        # Return the count of nodes with the highest score\n        return count\n        \n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'Python3']