Get started

Count Nodes With the Highest Score — Medium Problem & Solution

A binary tree has n nodes numbered 0 to n - 1 and root 0. It is given by parents, where parents[i] is the parent of node i and parents[0] == -1.

Problem statement

A binary tree has n nodes numbered 0 to n - 1 and root 0. It is given by parents, where parents[i] is the parent of node i and parents[0] == -1.

The score of a node is found by deleting that node together with its edges: the tree falls apart into one or more non-empty subtrees, and the score is the product of their sizes (a node whose removal leaves nothing behind cannot occur, since n >= 2).

Return the number of nodes that share the highest score.

Example 1

Input: parents = [-1,0,0,1,1]
Output: 3
Explanation: Node 0 scores 3 × 1 = 3, node 1 scores 1 × 1 × 2 = 2, and nodes 2, 3 and 4 each score 4.

Example 2

Input: parents = [-1,0]
Output: 2
Explanation: Removing either node leaves a single node, so both score 1.

Constraints

  • n == parents.length
  • 2 <= n <= 10^5
  • parents[0] == -1
  • 0 <= parents[i] <= n - 1 for i != 0
  • parents represents a valid binary tree

How to solve Count Nodes With the Highest Score

A node's score is the product of its children's subtree sizes and the size of the rest of the tree, so one subtree-size pass is enough.

Approach

  1. Build child lists from parents and a BFS order from the root.
  2. Walk the order backwards to accumulate size[u] = 1 + Σ size(child).
  3. For each node, multiply the sizes of its children, and also n − size[u] unless u is the root.
  4. Track the maximum score and how many nodes reach it.

Why it works

Deleting u disconnects exactly its child subtrees from each other and from the part of the tree outside u's subtree; those pieces have sizes size(child) and n − size(u). Empty pieces are skipped, matching the definition, so the product is exactly the score.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The product can exceed 32 bits (around 3.7 · 10^13 for n = 10^5); use 64-bit integers.
  • Leave out the upper piece for the root rather than multiplying by 0.
  • parents[i] < i is not guaranteed, so compute sizes in a real traversal order.

Reference solution

Python

from typing import List

def countHighestScoreNodes(parents: List[int]) -> int:
    n = len(parents)
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parents[i]].append(i)
    order = [0]
    for u in order:
        order.extend(children[u])
    size = [1] * n
    for u in reversed(order):
        if u != 0:
            size[parents[u]] += size[u]
    best, cnt = -1, 0
    for u in range(n):
        score = 1
        for c in children[u]:
            score *= size[c]
        if u != 0:
            score *= n - size[u]
        if score > best:
            best, cnt = score, 1
        elif score == best:
            cnt += 1
    return cnt

JavaScript

var countHighestScoreNodes = function(parents) {
    var n = parents.length;
    var children = [], size = [];
    for (var i = 0; i < n; i++) { children.push([]); size.push(1); }
    for (var k = 1; k < n; k++) children[parents[k]].push(k);
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var kids = children[order[h]];
        for (var j = 0; j < kids.length; j++) order.push(kids[j]);
    }
    for (var t = n - 1; t > 0; t--) size[parents[order[t]]] += size[order[t]];
    var best = -1, cnt = 0;
    for (var u = 0; u < n; u++) {
        var score = 1;
        for (var c = 0; c < children[u].length; c++) score *= size[children[u][c]];
        if (u !== 0) score *= n - size[u];
        if (score > best) { best = score; cnt = 1; }
        else if (score === best) cnt++;
    }
    return cnt;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search