# Count Nodes With the Highest Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-nodes-with-the-highest-score)
Canonical: https://scaleengineer.com/dsa/problems/count-nodes-with-the-highest-score
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree, Binary Tree
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Visa](https://scaleengineer.com/companies/visa)
---
## Problem
There is a **binary** tree rooted at `0` consisting of `n` nodes. The nodes are labeled from `0` to `n - 1`. You are given a **0-indexed** integer array `parents` representing the tree, where `parents[i]` is the parent of node `i`. Since node `0` is the root, `parents[0] == -1`.

Each node has a **score**. To find the score of a node, consider if the node and the edges connected to it were **removed**. The tree would become one or more **non-empty** subtrees. The **size** of a subtree is the number of the nodes in it. The **score** of the node is the **product of the sizes** of all those subtrees.

Return _the **number** of nodes that have the **highest score**_.

**Example 1:**

![example-1](https://assets.glich.co/dsa/count-nodes-with-the-highest-score/image0.png) 

**Input:** parents = [-1,2,0,2,0]
**Output:** 3
**Explanation:**
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

**Example 2:**

![example-2](https://assets.glich.co/dsa/count-nodes-with-the-highest-score/image1.png) 

**Input:** parents = [-1,2,0]
**Output:** 2
**Explanation:**
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

**Constraints:**

* `n == parents.length`
* `2 <= n <= 105`
* `parents[0] == -1`
* `0 <= parents[i] <= n - 1` for `i != 0`
* `parents` represents a valid binary tree.

# Approaches
## Brute Force with Repeated Traversals
This approach iterates through each node of the tree. For each node, it simulates its removal and then performs a graph traversal (like DFS or BFS) on the remaining parts to identify the resulting subtrees. The sizes of these components are multiplied to get the score for the current node. This process is repeated for all nodes, keeping track of the highest score and the count of nodes achieving it.
**Time:** O(N^2). The main loop runs N times. Inside the loop, for each child of the current node, we call `getSubtreeSize`. In the worst case (a skewed tree), `getSubtreeSize` can take O(N) time. Since this is inside a loop that runs N times, the total time complexity is O(N^2). · **Space:** O(N) to store the adjacency list and for the queue/stack used in the traversal within the loop.
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Highly inefficient due to redundant calculations. The size of the same subtree is computed multiple times.; The time complexity of O(N^2) can be too slow for the given constraints (N up to 10^5), likely resulting in a 'Time Limit Exceeded' error.
### Explanation
The brute-force method directly implements the score calculation for each node one by one. First, we convert the `parents` array into a more usable tree structure, like an adjacency list. Then, we loop through every node `i` from `0` to `n-1`. For each `i`, we need to find the sizes of the components that would form if `i` were removed. These components are the subtrees of `i`'s children and the rest of the tree (containing `i`'s parent).

To find the size of each child's subtree, we can perform a separate traversal (like BFS or DFS) starting from that child. After calculating the sizes of all children's subtrees, we sum them up. The size of the parent component is then `n` minus 1 (for node `i` itself) minus the sum of its children's subtree sizes. The score is the product of these component sizes. We use a `long` to store the score to avoid overflow. We keep track of the maximum score seen so far and how many nodes achieve it.

```java
import java.util.*;

class Solution {
    public int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            adj[parents[i]].add(i);
        }

        long maxScore = -1;
        int count = 0;

        for (int i = 0; i < n; i++) {
            long currentScore = 1;
            int nodesBelow = 0;

            for (int child : adj[i]) {
                int childSubtreeSize = getSubtreeSize(child, adj);
                currentScore *= childSubtreeSize;
                nodesBelow += childSubtreeSize;
            }

            int parentComponentSize = n - 1 - nodesBelow;
            if (parentComponentSize > 0) {
                currentScore *= parentComponentSize;
            }

            if (currentScore > maxScore) {
                maxScore = currentScore;
                count = 1;
            } else if (currentScore == maxScore) {
                count++;
            }
        }
        return count;
    }

    private int getSubtreeSize(int startNode, List<Integer>[] adj) {
        int size = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startNode);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            size++;
            for (int v : adj[u]) {
                queue.offer(v);
            }
        }
        return size;
    }
}
```
### Algorithm
- Build an adjacency list `adj` from the `parents` array to represent the tree structure, where `adj[i]` contains the children of node `i`.
- Define a helper function, `getSubtreeSize(startNode, adj)`, which performs a traversal (like DFS or BFS) starting from `startNode` to count all nodes in its subtree. This function takes O(N) time in the worst case.
- Initialize `maxScore = -1L` and `count = 0`.
- Iterate through each node `i` from `0` to `n-1`.
- For each node `i`, calculate its score:
  - Initialize `currentScore = 1L` and `nodesBelow = 0`.
  - For each `child` of node `i` in `adj[i]`:
    - Call `getSubtreeSize(child, adj)` to get the size of the child's subtree.
    - Multiply `currentScore` by this size.
    - Add this size to `nodesBelow`.
  - Calculate the size of the component 'above' node `i`. This is `parentComponentSize = n - 1 - nodesBelow`.
  - If `parentComponentSize` is greater than 0, multiply `currentScore` by it.
- Compare `currentScore` with `maxScore`.
  - If `currentScore > maxScore`, update `maxScore = currentScore` and set `count = 1`.
  - If `currentScore == maxScore`, increment `count`.
- After the loop, return `count`.

## Optimal Single DFS Traversal
This optimal approach avoids redundant computations by using a single Depth First Search (DFS) traversal. It calculates the size of each node's subtree in a post-order manner. Once the sizes of a node's children subtrees are known (after the recursive calls for its children return), we can immediately calculate the size of the parent component and thus the node's score. This combines subtree size calculation and score evaluation into one efficient pass.
**Time:** O(N). The DFS-based approach visits each node and edge of the tree exactly once. All operations performed at each node are constant time (excluding the recursive calls). · **Space:** O(N). This space is used for the adjacency list and the recursion call stack. In the worst-case scenario of a skewed tree, the recursion depth can be O(N).
**Pros:** Extremely efficient with optimal time complexity.; Solves the problem in a single pass over the tree, avoiding any redundant work.; Elegant and concise implementation using recursion.
**Cons:** The recursive implementation might lead to a `StackOverflowError` for extremely deep, skewed trees, although this is unlikely given the problem constraints and typical system stack sizes.
### Explanation
The key to an efficient solution is to avoid re-calculating subtree sizes. A single post-order traversal of the tree can achieve this. We define a recursive function, let's call it `dfs(node)`, which will compute and return the size of the subtree rooted at `node`.

During the traversal, after visiting all of a node's children and getting their subtree sizes from the recursive calls, we are at the 'post-order' step for the current node. At this point, we have all the information needed to calculate its score:
1. The sizes of the subtrees for each of its children.
2. The size of the current node's own subtree, which is 1 (for itself) plus the sum of its children's subtree sizes.
3. The size of the parent component, which is the total number of nodes `n` minus the size of the current node's subtree.

The score is the product of these component sizes. We must handle cases where a component might be empty (e.g., a leaf has no children, the root has no parent). A simple way is to multiply by a component's size only if it's greater than zero. We use a `long` for the score to prevent overflow. As we compute the score for each node during the traversal, we update a global maximum score and the count of nodes achieving it.

```java
import java.util.*;

class Solution {
    private long maxScore;
    private int count;
    private int n;
    private List<Integer>[] adj;

    public int countHighestScoreNodes(int[] parents) {
        this.n = parents.length;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            adj[parents[i]].add(i);
        }

        this.maxScore = -1;
        this.count = 0;

        dfs(0);

        return count;
    }

    private int dfs(int node) {
        long score = 1;
        int subtreeSize = 1;

        for (int child : adj[node]) {
            int childSubtreeSize = dfs(child);
            score *= childSubtreeSize;
            subtreeSize += childSubtreeSize;
        }

        int parentComponentSize = n - subtreeSize;
        if (parentComponentSize > 0) {
            score *= parentComponentSize;
        }

        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score == maxScore) {
            count++;
        }

        return subtreeSize;
    }
}
```
### Algorithm
- Build an adjacency list `adj` from the `parents` array.
- Initialize global variables `maxScore = -1L` and `count = 0`.
- Create a recursive DFS function, `dfs(node)`, that returns the size of the subtree rooted at `node`.
- Inside `dfs(node)`:
  - Initialize `mySize = 1` (for the node itself) and `score = 1L`.
  - For each `child` of `node`:
    - Recursively call `childSize = dfs(child)`.
    - Multiply `score` by `childSize`.
    - Add `childSize` to `mySize`.
  - Calculate the size of the parent component: `parentSize = n - mySize`.
  - If `parentSize > 0`, multiply `score` by `parentSize`.
  - Compare the calculated `score` with the global `maxScore`. Update `maxScore` and `count` accordingly.
  - Return `mySize`.
- Start the process by calling `dfs(0)` on the root node.
- After the traversal is complete, return the final `count`.

# Solutions
### CSharp

```csharp
public class Solution {
    private List < int > [] g;
    private int ans;
    private long mx;
    private int n;
    public int CountHighestScoreNodes(int[] parents) {
        n = parents.Length;
        g = new List < int > [n];
        for (int i = 0; i < n; ++i) {
            g[i] = new List < int > ();
        }
        for (int i = 1; i < n; ++i) {
            g[parents[i]].Add(i);
        }
        Dfs(0, -1);
        return ans;
    }
    private int Dfs(int i, int fa) {
        int cnt = 1;
        long score = 1;
        foreach(int j in g[i]) {
            if (j != fa) {
                int t = Dfs(j, i);
                cnt += t;
                score *= t;
            }
        }
        if (n - cnt > 0) {
            score *= n - cnt;
        }
        if (mx < score) {
            mx = score;
            ans = 1;
        } else if (mx == score) {
            ++ans;
        }
        return cnt;
    }
}
```

### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  int ans;
private
  long mx;
private
  int n;
public
  int countHighestScoreNodes(int[] parents) {
    n = parents.length;
    g = new List[n];
    Arrays.setAll(g, i->new ArrayList<>());
    for (int i = 1; i < n; ++i) {
      g[parents[i]].add(i);
    }
    dfs(0, -1);
    return ans;
  }
private
  int dfs(int i, int fa) {
    int cnt = 1;
    long score = 1;
    for (int j : g[i]) {
      if (j != fa) {
        int t = dfs(j, i);
        cnt += t;
        score *= t;
      }
    }
    if (n - cnt > 0) {
      score *= n - cnt;
    }
    if (mx < score) {
      mx = score;
      ans = 1;
    } else if (mx == score) {
      ++ans;
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countHighestScoreNodes(vector<int> &parents) {
    int n = parents.size();
    vector<int> g[n];
    for (int i = 1; i < n; ++i) {
      g[parents[i]].push_back(i);
    }
    int ans = 0;
    long long mx = 0;
    function<int(int, int)> dfs = [&](int i, int fa) {
      long long score = 1;
      int cnt = 1;
      for (int j : g[i]) {
        if (j != fa) {
          int t = dfs(j, i);
          cnt += t;
          score *= t;
        }
      }
      if (n - cnt) {
        score *= n - cnt;
      }
      if (mx < score) {
        mx = score;
        ans = 1;
      } else if (mx == score) {
        ++ans;
      }
      return cnt;
    };
    dfs(0, -1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int: def dfs(i: int, fa: int): cnt = score = 1 for j in g[i]: if j != fa: t = dfs(j, i) score *= t cnt += t if n - cnt: score *= n - cnt nonlocal ans, mx if mx < score: mx = score ans = 1 elif mx == score: ans += 1 return cnt n = len(parents) g = [[] for _ in range(n)] for i in range(1, n): g[parents[i]]. append(i) ans = mx = 0 dfs(0, - 1) return ans

```