Count Nodes With the Highest Score
Count Nodes With the Highest Score is a medium trees & bst problem solved with the postorder + multiple return values pattern.
The best approach, optimal (subtree sizes in one pass), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count each part separately) up.
Problem
A binary tree has n nodes labelled 0 to n - 1, rooted at node 0. It is given as an array parents, where parents[i] is the parent of node i and parents[0] == -1.
If you delete one node together with all edges touching it, the tree falls apart into one or more non-empty pieces. The score of that node is the product of the sizes of those pieces.
Return how many nodes have the highest score.
Examples
Example 1
- Input
parents = [-1, 0, 0, 1, 1]- Output
3- Why
- Removing node 0 leaves parts of sizes 3 and 1 (score 3), removing node 1 leaves 1, 1 and 2 (score 2), and removing node 2, 3 or 4 leaves one part of size 4 (score 4). Three nodes share the top score 4.
Example 2
- Input
parents = [-1, 0, 1, 2]- Output
2- Why
- In a chain of 4 nodes, removing node 1 or node 2 leaves parts of sizes 1 and 2 (score 2), while removing an end node leaves a single part of size 3 (score 3). The two end nodes share the top score.
Constraints
n == parents.length,2 <= n <= 10^5parents[0] == -1; fori != 0,0 <= parents[i] <= n - 1.parentsdescribes a valid binary tree rooted at node 0.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count each part separately) | O(n²) | O(n) |
| Optimal (subtree sizes in one pass) | O(n) | O(n) |
1Brute force (count each part separately)
O(n²)Each removal may traverse almost the whole tree again.O(n)Children lists and the traversal stack.For every node, imagine removing it. Each child starts a separate part, so count the nodes under each child with a fresh traversal. Whatever is left (n - 1 minus those counts) is the part above. Multiply the non-empty part sizes and track how many nodes reach the best score.
- Build the children lists from parents.
- For each node r: score = 1, below = 0.
- For each child c of r: count the nodes in c's subtree with a DFS, multiply score by it and add it to below.
- If n - 1 - below > 0, multiply score by it.
- Update the best score and its count.
class Solution {
public int countHighestScoreNodes(int[] parents) {
int n = parents.length;
List<List<Integer>> kids = new ArrayList<>();
for (int i = 0; i < n; i++) kids.add(new ArrayList<>());
for (int i = 1; i < n; i++) kids.get(parents[i]).add(i);
long best = -1;
int count = 0;
for (int r = 0; r < n; r++) {
long score = 1;
int below = 0;
for (int c : kids.get(r)) {
int cnt = 0;
ArrayDeque<Integer> st = new ArrayDeque<>();
st.push(c);
while (!st.isEmpty()) {
int u = st.pop();
cnt++;
for (int v : kids.get(u)) st.push(v);
}
score *= cnt;
below += cnt;
}
int rest = n - 1 - below;
if (rest > 0) score *= rest;
if (score > best) {
best = score;
count = 1;
} else if (score == best) {
count++;
}
}
return count;
}
}class Solution:
def countHighestScoreNodes(self, parents: List[int]) -> int:
n = len(parents)
kids = [[] for _ in range(n)]
for i in range(1, n):
kids[parents[i]].append(i)
best, count = -1, 0
for r in range(n):
score, below = 1, 0
for c in kids[r]:
cnt = 0
st = [c]
while st:
u = st.pop()
cnt += 1
st.extend(kids[u])
score *= cnt
below += cnt
rest = n - 1 - below
if rest > 0:
score *= rest
if score > best:
best, count = score, 1
elif score == best:
count += 1
return countclass Solution {
public:
int countHighestScoreNodes(vector<int>& parents) {
int n = parents.size();
vector<vector<int>> kids(n);
for (int i = 1; i < n; i++) kids[parents[i]].push_back(i);
long long best = -1;
int count = 0;
for (int r = 0; r < n; r++) {
long long score = 1;
int below = 0;
for (int c : kids[r]) {
int cnt = 0;
vector<int> st = {c};
while (!st.empty()) {
int u = st.back();
st.pop_back();
cnt++;
for (int v : kids[u]) st.push_back(v);
}
score *= cnt;
below += cnt;
}
int rest = n - 1 - below;
if (rest > 0) score *= rest;
if (score > best) {
best = score;
count = 1;
} else if (score == best) {
count++;
}
}
return count;
}
};function countHighestScoreNodes(parents) {
const n = parents.length;
const kids = Array.from({ length: n }, () => []);
for (let i = 1; i < n; i++) kids[parents[i]].push(i);
let best = -1, count = 0;
for (let r = 0; r < n; r++) {
let score = 1, below = 0;
for (const c of kids[r]) {
let cnt = 0;
const st = [c];
while (st.length) {
const u = st.pop();
cnt++;
for (const v of kids[u]) st.push(v);
}
score *= cnt;
below += cnt;
}
const rest = n - 1 - below;
if (rest > 0) score *= rest;
if (score > best) {
best = score;
count = 1;
} else if (score === best) {
count++;
}
}
return count;
}2Optimal (subtree sizes in one pass)
O(n)BFS, the size pass and the scoring pass each touch every node and edge once.O(n)Children lists, the BFS order and the size array.Compute the size of every subtree once. Visit nodes in BFS order from the root; walking that order backwards guarantees every child is finished before its parent, so size[parent] += size[child] builds all sizes without recursion. Then a node's score is the product of its children's sizes and, if non-empty, n - size[node] for the part above it.
- Build the children lists and a BFS order starting at node 0.
- Set every size to 1; walk the order backwards adding each node's size to its parent.
- For each node: score = product of size[child] over its children, times (n - size[node]) if that is positive.
- Count how many nodes reach the maximum score (use 64-bit arithmetic).
class Solution {
public int countHighestScoreNodes(int[] parents) {
int n = parents.length;
List<List<Integer>> kids = new ArrayList<>();
for (int i = 0; i < n; i++) kids.add(new ArrayList<>());
for (int i = 1; i < n; i++) kids.get(parents[i]).add(i);
int[] order = new int[n];
int head = 0, tail = 0;
order[tail++] = 0;
while (head < tail) {
int u = order[head++];
for (int v : kids.get(u)) order[tail++] = v;
}
int[] size = new int[n];
Arrays.fill(size, 1);
for (int i = n - 1; i > 0; i--) size[parents[order[i]]] += size[order[i]];
long best = -1;
int count = 0;
for (int u = 0; u < n; u++) {
long score = 1;
for (int v : kids.get(u)) score *= size[v];
int rest = n - size[u];
if (rest > 0) score *= rest;
if (score > best) {
best = score;
count = 1;
} else if (score == best) {
count++;
}
}
return count;
}
}class Solution:
def countHighestScoreNodes(self, parents: List[int]) -> int:
n = len(parents)
kids = [[] for _ in range(n)]
for i in range(1, n):
kids[parents[i]].append(i)
order = [0]
for u in order:
order.extend(kids[u])
size = [1] * n
for i in range(n - 1, 0, -1):
v = order[i]
size[parents[v]] += size[v]
best, count = -1, 0
for u in range(n):
score = 1
for v in kids[u]:
score *= size[v]
rest = n - size[u]
if rest > 0:
score *= rest
if score > best:
best, count = score, 1
elif score == best:
count += 1
return countclass Solution {
public:
int countHighestScoreNodes(vector<int>& parents) {
int n = parents.size();
vector<vector<int>> kids(n);
for (int i = 1; i < n; i++) kids[parents[i]].push_back(i);
vector<int> order;
order.reserve(n);
order.push_back(0);
for (int h = 0; h < (int)order.size(); h++)
for (int v : kids[order[h]]) order.push_back(v);
vector<int> size(n, 1);
for (int i = n - 1; i > 0; i--) size[parents[order[i]]] += size[order[i]];
long long best = -1;
int count = 0;
for (int u = 0; u < n; u++) {
long long score = 1;
for (int v : kids[u]) score *= size[v];
int rest = n - size[u];
if (rest > 0) score *= rest;
if (score > best) {
best = score;
count = 1;
} else if (score == best) {
count++;
}
}
return count;
}
};function countHighestScoreNodes(parents) {
const n = parents.length;
const kids = Array.from({ length: n }, () => []);
for (let i = 1; i < n; i++) kids[parents[i]].push(i);
const order = [0];
for (let h = 0; h < order.length; h++)
for (const v of kids[order[h]]) order.push(v);
const size = new Array(n).fill(1);
for (let i = n - 1; i > 0; i--) size[parents[order[i]]] += size[order[i]];
let best = -1, count = 0;
for (let u = 0; u < n; u++) {
let score = 1; // at most about 3.7e13, safe in a double
for (const v of kids[u]) score *= size[v];
const rest = n - size[u];
if (rest > 0) score *= rest;
if (score > best) {
best = score;
count = 1;
} else if (score === best) {
count++;
}
}
return count;
}Edge cases to test
- A tree with two nodes (both score 1)
- A long chain, where recursion depth can reach n
- Scores that overflow a 32-bit integer
- Removing the root, which leaves no component above it
Hints
Hint 1
Removing a node splits the tree into at most three parts: its left subtree, its right subtree, and everything outside its subtree.
Hint 2
If you know the size of every subtree, the part above a node has size n - size(node).
Hint 3
Compute all subtree sizes in one post-order pass, then score each node in O(1). Use 64-bit integers for the product.
FAQ
What is the best time complexity for Count Nodes With the Highest Score?
Optimal (subtree sizes in one pass) runs in O(n) time and O(n) extra space. BFS, the size pass and the scoring pass each touch every node and edge once.
Which pattern does Count Nodes With the Highest Score use?
It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.
Is there a brute force solution for Count Nodes With the Highest Score?
Yes. Brute force (count each part separately) takes O(n²) time and O(n) space. For every node, imagine removing it.
Which edge cases should I test for Count Nodes With the Highest Score?
A tree with two nodes (both score 1); A long chain, where recursion depth can reach n; Scores that overflow a 32-bit integer; Removing the root, which leaves no component above it.