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.length2 <= n <= 105parents[0] == -10 <= parents[i] <= n - 1 for i != 0parents represents a valid binary tree.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.
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.
Time Complexity: O(n) as each node and edge is visited once during DFS.
Space Complexity: O(n) for storing tree and subtree sizes.
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.
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.
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.
| Approach | Complexity |
|---|---|
| DFS to Calculate Subtree Sizes | Time Complexity: O(n) as each node and edge is visited once during DFS. |
| Dynamic Programming Optimization | Time Complexity: O(n) since each node and edge is considered only once. |
| DFS | — |
| 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 |
Count Nodes With the Highest Score | Leetcode 2049 | Live coding session ❤️❤️❤️ • Coding Decoded • 3,982 views views
Watch 9 more video solutions →Practice Count Nodes With the Highest Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor