Watch 10 video solutions for Count Nodes With the Highest Score, a medium level problem involving Array, Tree, Depth-First Search. This walkthrough by Coding Decoded has 3,982 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |