2049. Count Nodes With Highest Score Solution

The 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:

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:

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 <= 10⁵
parents[0] == -1
0 <= parents[i] <= n - 1 for i != 0
parents represents a valid binary tree.

Approach overview

Problem Overview: You are given a tree represented by a parents array where parents[i] is the parent of node i. Removing a node splits the tree into multiple components. The score of that node equals the product of the sizes of those components. The task is to count how many nodes produce the maximum score.

Approach 1: DFS to Calculate Subtree Sizes (O(n) time, O(n) space)

Build an adjacency list from the parents array and treat node 0 as the root. Run a postorder DFS to compute the size of every subtree. For a node u, each child contributes a component of size subtreeSize[child]. Another component may exist representing the remaining nodes outside the subtree: n - subtreeSize[u]. Multiply the sizes of all non‑zero components to compute the node's score. Track the maximum score and count how many nodes achieve it. This method performs a single traversal of the tree and works naturally with Depth-First Search on a tree.

Approach 2: Dynamic Programming on Tree (O(n) time, O(n) space)

Tree DP computes subtree sizes and scores in a structured postorder pass. Each node returns its subtree size to its parent while the algorithm calculates the product of its child component sizes. The remaining component (n - subtreeSize[node]) is incorporated during the same step, avoiding repeated calculations. Conceptually this is similar to the DFS solution but framed as dynamic programming where each node reuses results from its children. The approach is efficient for large trees and fits common interview patterns for problems involving subtree aggregation in binary tree or general tree structures.

Recommended for interviews: The DFS subtree size approach is what interviewers expect. It demonstrates understanding of tree traversal, component sizes after node removal, and careful handling of the remaining parent side of the tree. Explaining the brute reasoning (each removal splits the tree into parts) shows problem understanding, while implementing the O(n) DFS shows strong algorithmic skill.

Approach 1: DFS to Calculate Subtree Sizes

Use a DFS (depth-first search) to calculate the size of each subtree. After calculating the subtree sizes, find the score of each node by considering the sizes of its remaining subtrees. Specifically, if a node has children, calculate its score by multiplying the sizes of these children and the remaining nodes (total size minus current node subtree size).

Python

from typing import List

def dfs(node: int, children: List[List[int]], sizes: List[int]) -> None:
    sizes[node] = 1
    for child in children[node]:
        dfs(child, children, sizes)
        sizes[node] += sizes[child]

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        n = len(parents)
        children = [[] for _ in range(n)]
        for i in range(1, n):
            children[parents[i]].append(i)
        sizes = [0] * n
        dfs(0, children, sizes)
        max_score = 0
        count = 0
        for i in range(n):
            score = 1
            if n - sizes[i] > 0:
                score *= (n - sizes[i])
            for child in children[i]:
                score *= sizes[child]
            if score > max_score:
                max_score = score
                count = 1
            elif score == max_score:
                count += 1
        return count

parents = [-1, 2, 0, 2, 0]
solution = Solution()
print(solution.countHighestScoreNodes(parents))

Java

import java.util.ArrayList;
import java.util.List;

public class HighestScoreNodes {
    public static int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            children.get(parents[i]).add(i);
        }
        int[] sizes = new int[n];
        dfs(0, children, sizes, n);
        long maxScore = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            long score = 1;
            if (n - sizes[i] > 0) {
                score *= (n - sizes[i]);
            }
            for (int child : children.get(i)) {
                score *= sizes[child];
            }
            if (score > maxScore) {
                maxScore = score;
                count = 1;
            } else if (score == maxScore) {
                count++;
            }
        }
        return count;
    }

    private static void dfs(int node, List<List<Integer>> children, int[] sizes, int n) {
        sizes[node] = 1;
        for (int child : children.get(node)) {
            dfs(child, children, sizes, n);
            sizes[node] += sizes[child];
        }
    }

    public static void main(String[] args) {
        int[] parents = {-1, 2, 0, 2, 0};
        System.out.println(countHighestScoreNodes(parents));
    }
}

C++

#include <vector>
#include <climits>
using namespace std;

void dfs(int node, vector<vector<int>>& children, vector<int>& sizes, int& n) {
    sizes[node] = 1;
    for (int child : children[node]) {
        dfs(child, children, sizes, n);
        sizes[node] += sizes[child];
    }
}

int countHighestScoreNodes(vector<int>& parents) {
    int n = parents.size();
    vector<vector<int>> children(n);
    vector<int> sizes(n, 0);
    for (int i = 1; i < n; ++i) {
        children[parents[i]].push_back(i);
    }
    dfs(0, children, sizes, n);
    long maxScore = 0;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        long score = 1;
        if (n - sizes[i] > 0)
            score *= (n - sizes[i]);
        for (int child : children[i]) {
            score *= sizes[child];
        }
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score == maxScore) {
            ++count;
        }
    }
    return count;
}

int main() {
    vector<int> parents = {-1, 2, 0, 2, 0};
    printf("%d\n", countHighestScoreNodes(parents));
    return 0;
}

JavaScript

function dfs(node, children, sizes) {
    sizes[node] = 1;
    for (const child of children[node]) {
        dfs(child, children, sizes);
        sizes[node] += sizes[child];
    }
}

var countHighestScoreNodes = function(parents) {
    const n = parents.length;
    const children = Array.from({length: n}, () => []);
    for (let i = 1; i < n; i++) {
        children[parents[i]].push(i);
    }
    const sizes = Array(n).fill(0);
    dfs(0, children, sizes);
    let maxScore = 0;
    let count = 0;
    for (let i = 0; i < n; i++) {
        let score = 1;
        if (n - sizes[i] > 0) score *= (n - sizes[i]);
        for (const child of children[i]) {
            score *= sizes[child];
        }
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score === maxScore) {
            count++;
        }
    }
    return count;
};

const parents = [-1, 2, 0, 2, 0];
console.log(countHighestScoreNodes(parents));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void dfs(int node, int *tree[], int *sizes, int *n) {
    sizes[node] = 1;
    for (int i = 0; i < tree[node][0]; i++) {
        int child = tree[node][i+1];
        dfs(child, tree, sizes, n);
        sizes[node] += sizes[child];
    }
}

int countHighestScoreNodes(int* parents, int n) {
    int **tree = (int **)malloc(n * sizeof(int *));
    int *sizes = (int *)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        tree[i] = (int *)calloc(n + 1, sizeof(int));
    }
    for (int i = 1; i < n; i++) {
        tree[parents[i]][++tree[parents[i]][0]] = i;
    }
    dfs(0, tree, sizes, &n);
    long maxScore = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        long score = n - sizes[i] > 1 ? n - sizes[i] : 1;
        for (int j = 0; j < tree[i][0]; j++) {
            score *= sizes[tree[i][j+1]];
        }
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score == maxScore) {
            count++;
        }
    }
    for (int i = 0; i < n; i++) {
        free(tree[i]);
    }
    free(tree);
    free(sizes);
    return count;
}

int main() {
    int parents[] = {-1, 2, 0, 2, 0};
    int n = sizeof(parents) / sizeof(parents[0]);
    printf("%d\n", countHighestScoreNodes(parents, n));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountHighestScoreNodes(int[] parents) {
        int n = parents.Length;
        List<int>[] children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        for (int i = 1; i < n; i++) {
            children[parents[i]].Add(i);
        }
        int[] sizes = new int[n];
        Dfs(0, children, sizes);
        long maxScore = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            long score = 1;
            if (n - sizes[i] > 1)
                score *= (n - sizes[i]);
            foreach (int child in children[i]) {
                score *= sizes[child];
            }
            if (score > maxScore) {
                maxScore = score;
                count = 1;
            } else if (score == maxScore) {
                count++;
            }
        }
        return count;
    }

    private void Dfs(int node, List<int>[] children, int[] sizes) {
        sizes[node] = 1;
        foreach (int child in children[node]) {
            Dfs(child, children, sizes);
            sizes[node] += sizes[child];
        }
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] parents = {-1, 2, 0, 2, 0};
        Console.WriteLine(solution.CountHighestScoreNodes(parents));
    }
}

Python uses a list of lists for storing children nodes, and executes DFS to find sizes and score calculations.

Complexity

Time Complexity: O(n) as each node is processed once via DFS.
Space Complexity: O(n) to track children nodes and subtree sizes.

Try this approach in the editor

Approach 2: Dynamic Programming Optimization

This approach optimizes the solution by utilizing dynamic programming principles to store and reuse subtree size calculations. It reduces redundant calculations and efficiently manages subtree data for score computation.

Python

from typing import List

def dfs(node: int, children: List[List[int]], sizes: List[int], dp: List[int]) -> None:
    sizes[node] = 1
    dp[node] = -1
    for child in children[node]:
        if dp[child] == -1:
            dfs(child, children, sizes, dp)
        sizes[node] += sizes[child]
    dp[node] = sizes[node]

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        n = len(parents)
        children = [[] for _ in range(n)]
        for i in range(1, n):
            children[parents[i]].append(i)
        sizes = [0] * n
        dp = [-1] * n
        dfs(0, children, sizes, dp)
        max_score = 0
        count = 0
        for i in range(n):
            score = 1
            if n - sizes[i] > 0:
                score *= (n - sizes[i])
            for child in children[i]:
                score *= sizes[child]
            if score > max_score:
                max_score = score
                count = 1
            elif score == max_score:
                count += 1
        return count

parents = [-1, 2, 0, 2, 0]
solution = Solution()
print(solution.countHighestScoreNodes(parents))

Java

import java.util.ArrayList;
import java.util.List;

public class HighestScoreNodesDP {
    public static int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            children.get(parents[i]).add(i);
        }
        int[] sizes = new int[n];
        int[] dp = new int[n];
        dfs(0, children, sizes, dp, n);
        long maxScore = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            long score = 1;
            if (n - sizes[i] > 0) {
                score *= (n - sizes[i]);
            }
            for (int child : children.get(i)) {
                score *= sizes[child];
            }
            if (score > maxScore) {
                maxScore = score;
                count = 1;
            } else if (score == maxScore) {
                count++;
            }
        }
        return count;
    }

    private static void dfs(int node, List<List<Integer>> children, int[] sizes, int[] dp, int n) {
        sizes[node] = 1;
        dp[node] = -1;
        for (int child : children.get(node)) {
            if (dp[child] == -1) dfs(child, children, sizes, dp, n);
            sizes[node] += sizes[child];
        }
        dp[node] = sizes[node];
    }

    public static void main(String[] args) {
        int[] parents = {-1, 2, 0, 2, 0};
        System.out.println(countHighestScoreNodes(parents));
    }
}

C++

#include <vector>
#include <climits>
using namespace std;

void dfs(int node, vector<vector<int>>& children, vector<int>& sizes, vector<int>& dp, int& n) {
    sizes[node] = 1;
    for (int child : children[node]) {
        if (dp[child] == -1) dfs(child, children, sizes, dp, n);
        sizes[node] += sizes[child];
    }
    dp[node] = sizes[node];
}

int countHighestScoreNodes(vector<int>& parents) {
    int n = parents.size();
    vector<vector<int>> children(n);
    vector<int> sizes(n, 0);
    vector<int> dp(n, -1);
    for (int i = 1; i < n; ++i) {
        children[parents[i]].push_back(i);
    }
    dfs(0, children, sizes, dp, n);
    long maxScore = 0;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        long score = 1;
        if (n - sizes[i] > 0)
            score *= (n - sizes[i]);
        for (int child : children[i]) {
            score *= sizes[child];
        }
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score == maxScore) {
            ++count;
        }
    }
    return count;
}

int main() {
    vector<int> parents = {-1, 2, 0, 2, 0};
    printf("%d\n", countHighestScoreNodes(parents));
    return 0;
}

JavaScript

function dfs(node, children, sizes, dp) {
    sizes[node] = 1;
    dp[node] = -1;
    for (const child of children[node]) {
        if (dp[child] === -1) {
            dfs(child, children, sizes, dp);
        }
        sizes[node] += sizes[child];
    }
    dp[node] = sizes[node];
}

var countHighestScoreNodes = function(parents) {
    const n = parents.length;
    const children = Array.from({length: n}, () => []);
    for (let i = 1; i < n; i++) {
        children[parents[i]].push(i);
    }
    const sizes = Array(n).fill(0);
    const dp = Array(n).fill(-1);
    dfs(0, children, sizes, dp);
    let maxScore = 0;
    let count = 0;
    for (let i = 0; i < n; i++) {
        let score = 1;
        if (n - sizes[i] > 0) score *= (n - sizes[i]);
        for (const child of children[i]) {
            score *= sizes[child];
        }
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score === maxScore) {
            count++;
        }
    }
    return count;
};

const parents = [-1, 2, 0, 2, 0];
console.log(countHighestScoreNodes(parents));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void dfs(int node, int *tree[], int *sizes, int *dp, int *n) {
    sizes[node] = 1;
    for (int i = 0; i < tree[node][0]; i++) {
        int child = tree[node][i+1];
        if (dp[child] == -1) {
            dfs(child, tree, sizes, dp, n);
        }
        sizes[node] += sizes[child];
    }
    dp[node] = sizes[node];
}

int countHighestScoreNodes(int* parents, int n) {
    int **tree = (int **)malloc(n * sizeof(int *));
    int *sizes = (int *)calloc(n, sizeof(int));
    int *dp = (int *)malloc(n * sizeof(int));
    memset(dp, -1, n * sizeof(int));
    for (int i = 0; i < n; i++) {
        tree[i] = (int *)calloc(n + 1, sizeof(int));
    }
    for (int i = 1; i < n; i++) {
        tree[parents[i]][++tree[parents[i]][0]] = i;
    }
    dfs(0, tree, sizes, dp, &n);
    long maxScore = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        long score = n - sizes[i] > 1 ? n - sizes[i] : 1;
        for (int j = 0; j < tree[i][0]; j++) {
            score *= sizes[tree[i][j+1]];
        }
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score == maxScore) {
            count++;
        }
    }
    for (int i = 0; i < n; i++) {
        free(tree[i]);
    }
    free(tree);
    free(sizes);
    free(dp);
    return count;
}

int main() {
    int parents[] = {-1, 2, 0, 2, 0};
    int n = sizeof(parents) / sizeof(parents[0]);
    printf("%d\n", countHighestScoreNodes(parents, n));
    return 0;
}

using System;
using System.Collections.Generic;

public class SolutionDP {
    public int CountHighestScoreNodes(int[] parents) {
        int n = parents.Length;
        List<int>[] children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        for (int i = 1; i < n; i++) {
            children[parents[i]].Add(i);
        }
        int[] sizes = new int[n];
        int[] dp = new int[n];
        Array.Fill(dp, -1);
        Dfs(0, children, sizes, dp);
        long maxScore = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            long score = 1;
            if (n - sizes[i] > 1)
                score *= (n - sizes[i]);
            foreach (int child in children[i]) {
                score *= sizes[child];
            }
            if (score > maxScore) {
                maxScore = score;
                count = 1;
            } else if (score == maxScore) {
                count++;
            }
        }
        return count;
    }

    private void Dfs(int node, List<int>[] children, int[] sizes, int[] dp) {
        sizes[node] = 1;
        foreach (int child in children[node]) {
            if (dp[child] == -1) Dfs(child, children, sizes, dp);
            sizes[node] += sizes[child];
        }
        dp[node] = sizes[node];
    }

    public static void Main(string[] args) {
        SolutionDP solution = new SolutionDP();
        int[] parents = {-1, 2, 0, 2, 0};
        Console.WriteLine(solution.CountHighestScoreNodes(parents));
    }
}

The Python solution utilizes a dp list to store subtree sizes and minimizes recomputation for efficiency.

Complexity

Time Complexity: O(n) as every node is examined the same way once.
Space Complexity: O(n) for storing the tree structure and subtree data.

Try this approach in the editor

Approach 3: DFS

First, we construct a graph g based on the given parent array parents, where g[i] represents all child nodes of node i. We define a variable ans to represent the number of nodes with the highest score, and a variable mx to represent the highest score.

Then, we design a function dfs(i, fa) to calculate the score of node i and return the number of nodes in the subtree rooted at node i.

The calculation process of the function dfs(i, fa) is as follows:

We first initialize a variable cnt = 1, representing the number of nodes in the subtree rooted at node i; a variable score = 1, representing the initial score of node i.

Next, we traverse all child nodes j of node i. If j is not the parent node fa of node i, then we recursively call dfs(j, i), and multiply the return value into score, and add the return value to cnt.

After traversing the child nodes, if n - cnt > 0, then we multiply n - cnt into score.

Then, we check whether mx is less than score. If it is less, then we update mx to score, and update ans to 1; if it is equal, then we update ans to ans + 1.

Finally, we return cnt.

In the end, we call dfs(0, -1) and return ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

TypeScript

function countHighestScoreNodes(parents: number[]): number {
    const n = parents.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; i++) {
        g[parents[i]].push(i);
    }
    let [ans, mx] = [0, 0];
    const dfs = (i: number, fa: number): number => {
        let [cnt, score] = [1, 1];
        for (const j of g[i]) {
            if (j !== fa) {
                const 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;
}

func countHighestScoreNodes(parents []int) (ans int) {
	n := len(parents)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		g[parents[i]] = append(g[parents[i]], i)
	}
	mx := 0
	var dfs func(i, fa int) int
	dfs = func(i, fa int) int {
		cnt, score := 1, 1
		for _, j := range g[i] {
			if j != fa {
				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
	}
	dfs(0, -1)
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
DFS to Calculate Subtree Sizes	Time Complexity: O(n) as each node is processed once via DFS. Space Complexity: O(n) to track children nodes and subtree sizes.
Dynamic Programming Optimization	Time Complexity: O(n) as every node is examined the same way once. Space Complexity: O(n) for storing the tree structure and subtree data.
DFS	–

Complexity analysis

Approach	Time	Space	When to Use
DFS to Calculate Subtree Sizes	O(n)	O(n)	General solution for tree problems where subtree sizes determine results
Dynamic Programming on Tree	O(n)	O(n)	When structuring the solution as postorder tree DP for reuse in similar subtree aggregation problems

Frequently asked questions

Is Count Nodes With the Highest Score easy or hard?

Count Nodes With the Highest Score is typically classified as a medium difficulty problem. The challenge comes from recognizing how removing a node splits the tree and computing the product of resulting component sizes efficiently. Once subtree sizes are available, the rest of the calculation becomes straightforward.

Count Nodes With the Highest Score Python/Java solution

Both Python and Java implementations follow the same logic: build a children adjacency list, run a DFS to compute subtree sizes, and calculate the score at each node. The algorithm maintains the current maximum score and the number of nodes achieving it. Time complexity remains O(n) across languages.

How to solve Count Nodes With the Highest Score in O(n)?

Convert the parents array into an adjacency list, then run a postorder DFS starting from the root. Each DFS call returns the size of the node's subtree. Use these sizes to compute the score by multiplying the sizes of child components and the remaining nodes outside the subtree. Maintain the maximum score and a counter while traversing.

What is the best approach for Count Nodes With the Highest Score?

The most effective approach uses a DFS traversal to compute subtree sizes for every node. After calculating the size of each child subtree, multiply those sizes with the remaining part of the tree (n - subtreeSize[node]) to get the score. Track the maximum score during traversal and count how many nodes reach it. This runs in O(n) time and O(n) space.

Is Count Nodes With the Highest Score asked at Google/Amazon/Meta?

Tree DFS and subtree-size problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. Variants often involve removing nodes, computing component sizes, or aggregating values across subtrees. Understanding DFS and tree DP patterns is valuable for these interviews.

What data structure is used in Count Nodes With the Highest Score?

The core data structure is a tree represented using an adjacency list derived from the parents array. The algorithm relies on depth-first search recursion and an array to store subtree sizes. Multiplication of component sizes determines each node's score.

What is the time complexity of Count Nodes With the Highest Score?

The optimal solution runs in O(n) time because each node is visited exactly once during a DFS traversal. Subtree sizes and scores are computed during the same pass. Space complexity is O(n) due to the adjacency list representation of the tree and recursion stack.

Count Nodes With the Highest Score solution and explanation

The problem

Approach overview

Approach 1: DFS to Calculate Subtree Sizes

Approach 2: Dynamic Programming Optimization

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Nodes With the Highest Score solution and explanation

The problem

Approach overview

Approach 1: DFS to Calculate Subtree Sizes

Approach 2: Dynamic Programming Optimization

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems