Java simple solution beats 90%. With Explanations
IntuitionThe intuition is if we have a size aware binary tree then we can calculate the score of each node in constant time(linear overall). Once we remove a no
# Intuition
The intuition is if we have a size aware binary tree then we can calculate the score of each node in constant time(linear overall). Once we remove a node then the size of the tree with remaining nodes is root.size - node.size. The left and right nodes of the node that are removed will have sizes left.size and right.size. The score is the product of left.size, right.size and root.size - node.size. Make sure that your floor is 1.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Define a TreeNode class that as left, right and parent pointers and also a field called size which is the size of the sub tree rooted at the node.
2. Convert the array to a binary tree by iterating through it.
3. Store reference to each node in an array too. (This is needed to buld the tree anyways).
4. Use DFS to calculate and set the size of each node.
5. Loop through the array of nodes and calculate the score. Score = left.size * right.size * (root.size-current.size). Make sure you use the floor value 1 for null children and when current is root.

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public TreeNode parent;
    public int val;
    public long size;
    public TreeNode(int val) {
        this.val = val;
        this.size = 1;
    }
}

class Solution {
    TreeNode[] nodes;
    int count = 0;
    long max = 0;
    public int countHighestScoreNodes(int[] parents) {
        nodes = new TreeNode[parents.length];
        TreeNode root = new TreeNode(0);
        nodes[0] = root;
        for (int i = 1; i < parents.length; i++) {
            if (nodes[i] == null) nodes[i] = new TreeNode(i);
            if (nodes[parents[i]] == null) nodes[parents[i]] = new TreeNode(parents[i]);
            TreeNode parent = nodes[parents[i]];
            if (parent.left == null) parent.left = nodes[i];
            else parent.right = nodes[i];
            nodes[i].parent = parent;
        }
        updatesize(root);
        for (int i = 0; i < parents.length; i++) {
            TreeNode current = nodes[i];
            TreeNode left = current.left, right = current.right, parent = current.parent;
            long lsize = left != null ? left.size : 1;
            long rsize = right != null ? right.size : 1;
            long psize = Math.max(root.size - current.size, 1);
            long score = lsize*rsize*psize;
            if (score > max) {
                count = 1;
                max = score;
            }
            else if (score == max) count++;
        }
        return count;

    }

    private long updatesize(TreeNode node) {
        if (node != null) {
            node.size += updatesize(node.left);
            node.size += updatesize(node.right);
            return node.size;
        }
        return 0;
    }


}
```
['Java']