Java - O(N) space and time solution
A cut score is multiplication of no of leftChildren, no of rightChidren and remaning nodes (Total nodes-leftChildren-rightChildren-1).\nBelow is Java Code for t
A cut score is multiplication of no of leftChildren, no of rightChidren and remaning nodes (Total nodes-leftChildren-rightChildren-1).\nBelow is Java Code for the solution with comments.\n\n```\n//TreeNode \nclass TreeNode\n{\n    int val;\n    TreeNode left;\n    TreeNode right;\n    int leftChilds=0;\n    int rightChilds=0;\n    TreeNode(int val)\n    {\n        this.val=val;\n    }\n}\nclass Solution {\n    HashMap<Long,Integer> costs;\n    long max; //To store maximum cost value\n    int n;\n    public int countHighestScoreNodes(int[] parents) {\n        costs=new HashMap<Long,Integer>(); //To store frequency of each cost value\n        max=0;\n        n=parents.length;\n        HashMap<Integer,TreeNode> hm=new HashMap<Integer,TreeNode>();\n        TreeNode root=new TreeNode(0); //Initializing root node\n        hm.put(0,root);\n        for(int i=1;i<parents.length;i++)\n        {\n            int parent=parents[i];\n            TreeNode child=hm.getOrDefault(i,new TreeNode(i));\n            TreeNode parentNode=hm.getOrDefault(parent,new TreeNode(parent));\n            if(parentNode.left==null)\n            {\n                parentNode.left=child;\n            }\n            else\n            {\n                parentNode.right=child;\n            }\n            hm.put(i,child);\n            hm.put(parent,parentNode);\n        }//Loop to construct tree structure.\n        postOrderTraverse(root);  //postOrder traversal\n        return costs.get(max); // Returning maximum frequency\n    }\n    public int postOrderTraverse(TreeNode root)\n    {\n        if(root==null)\n            return 0;\n       \n        long one=1; \n        root.leftChilds=postOrderTraverse(root.left);  //Getting no of leftChilds\n        root.rightChilds=postOrderTraverse(root.right); //Getting no of rightChilds\n        long score=(one*Math.max(root.leftChilds,1)*(Math.max(root.rightChilds,1))*(Math.max(n-root.leftChilds-root.rightChilds-1,1))); // Calculating the score of the node\n        costs.put(score,costs.getOrDefault(score,0)+1);\n        max=Math.max(score,max);\n        return root.leftChilds+root.rightChilds+1; \n    }\n}\n```
['Depth-First Search', 'Binary Tree']