Count Nodes With the Highest Score

Medium Trees & BST Postorder + Multiple Return Values Original on LeetCode

Reported atDoorDashVisa

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^5
  • parents[0] == -1; for i != 0, 0 <= parents[i] <= n - 1.
  • parents describes 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n²)Each removal may traverse almost the whole tree again.
SpaceO(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.

  1. Build the children lists from parents.
  2. For each node r: score = 1, below = 0.
  3. 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.
  4. If n - 1 - below > 0, multiply score by it.
  5. 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;
    }
}

2Optimal (subtree sizes in one pass)

TimeO(n)BFS, the size pass and the scoring pass each touch every node and edge once.
SpaceO(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.

  1. Build the children lists and a BFS order starting at node 0.
  2. Set every size to 1; walk the order backwards adding each node's size to its parent.
  3. For each node: score = product of size[child] over its children, times (n - size[node]) if that is positive.
  4. 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;
    }
}

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.