Skip to main content
Talentd

Count Nodes With the Highest Score - Solution & Explanation

MediumArrayTreeDepth-First SearchBinary Tree24 min readAsked at: Amazon, Visa, DoorDash
Practice this problem

Problem Statement

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 
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 
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.

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

The C solution implements DFS to compute subtree sizes. We allocate memory to store the children of each node, perform DFS from the root to calculate sizes, and then evaluate scores by considering the remaining tree on node removal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) as each node and edge is visited once during DFS.
Space Complexity: O(n) for storing tree 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.

In this C solution, we add a dp array to cache the subtree sizes calculated by DFS. This avoids redundant subtree computations, enhancing efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) since each node and edge is considered only once.
Space Complexity: O(n) similar to the previous DFS approach but with an additional dp array.

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS to Calculate Subtree Sizes

Time Complexity: O(n) as each node and edge is visited once during DFS.
Space Complexity: O(n) for storing tree and subtree sizes.

Dynamic Programming Optimization

Time Complexity: O(n) since each node and edge is considered only once.
Space Complexity: O(n) similar to the previous DFS approach but with an additional dp array.

DFS—

Detailed Complexity Analysis

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

Video Solution

Count Nodes With the Highest Score | Leetcode 2049 | Live coding session ❤️❤️❤️ • Coding Decoded • 4,089 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Count Nodes With the Highest Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Delete Nodes And Return Forest

Next

Maximum Product of Splitted Binary Tree