Easy Solution, simulation of recursion using queue
Intuition\n Describe your first thoughts on how to solve this problem. \nIf the input was given in the form of TreeNode then the obvious way is to use postorder
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf the input was given in the form of TreeNode then the obvious way is to use postorder traversal. That is, a node receives number of left nodes from left child node and similary from right, then we can just multiply them with the remaining node to get the answer. \nIn postorder traversal, things to node:\n1. Start from leaf node\n2. return the value to parent\n3. parent operates when it receives data from all its child\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. vector<pair<int, int>> to track left and right child of each node values with default value 0. This is similar to the values returned by them in case of recursion.\n2. vector<int> - isleaf, given the tree is binary, n(children) can be 2,1,0. push this value on to the queue when it is 0, that is either the node is leaf node (in the beginning) or the node\'s all children have finshed with it calculation.\n3. queue<int> to simulate the backtracking of recursion\n4. left * right * (n-v[node].first-v[node].second-1) is the formula to calculate the score\n5. map to store the number of occurences\n6. Since we dont have pointers which explicitly tell whether the value is returned from left/right child, or are both of them present? \n    - we will use isleaf to keep track of number of children.\n    - parent receives value from either left or right, so once left is returned it is obvious that next return value will be right or vice-versa. So assign the first with the value(assuming left) and then fill second value. Simultaneously we will reduce the number in isleaf saying that a child has returned the value.\n    - when the isleaf is 0, i.e., the node has received the values from both the child then the particular node is ready to return the value.\n\nwe are just multiplying values from left and right subtrees so its fair to assume first in pair holds left subtree value.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int countHighestScoreNodes(vector<int>& parents) {\n        int n=parents.size();\n        vector<pair<int, int>>v(n, {0,0}); //store returned values from left and right subtree \n\n        vector<int>isleaf(n, 0);\n        for (int i=1;i<n;i++) isleaf[parents[i]]++;//store n(children)\n\n        queue<int>q;\n        for (int i=1;i<n;i++) if (isleaf[i]==0) q.push(i);\n\n        map<long, long>mp;\n        while (!q.empty() && q.front()) {\n            int node=q.front();\n            q.pop();\n\n            long left=v[node].first ? v[node].first : 1, right=v[node].second ? v[node].second : 1;\n            long val = (long) (left * right * (n-v[node].first-v[node].second-1)); //calulare the score\n            mp[val]++;\n\n            int parent=parents[node];\n            if (v[parent].first==0) {v[parent].first = v[node].first+v[node].second+1;isleaf[parent]--;} // fill .first first, if isleaf[parent] is 1, then it all its child has finished the job so push the parent to the queue\n            else {v[parent].second = v[node].first+v[node].second+1;isleaf[parent]--;} //if parent has second child, it comes down to else and then isleaf becomes 0, then push this parent on to stack\n\n            if (isleaf[parent]==0) q.push(parent);\n     \n        }\n        \n        int left=v[0].first ? v[0].first : 1, right=v[0].second ? v[0].second : 1;\n        mp[(long)left*right]++; // parent==0; all nodes will be in left or right sub tree, the part value is 0, so explicit calculation\n\n        return mp.rbegin()->second;\n    }\n};\n```
['Depth-First Search', 'Queue', 'Binary Tree', 'C++']