Count Nodes With the Highest Score

Count Nodes With the Highest Score

What is this problem about?

This tree problem involves "scoring" each node based on how the tree is split when that node is removed. Removing a node $u$ splits the tree into several components: the subtrees of its children and the rest of the tree (connected via its parent). The "score" of node $u$ is the product of the sizes of these components. You need to find the maximum score and count how many nodes achieve it.

Why is this asked in interviews?

Companies like Visa and Amazon ask this to test your understanding of tree structure and size calculation. It’s an exercise in transforming a directed tree (root to children) into an undirected graph conceptually. It tests whether you can calculate the "parent-side" component size using the formula TotalNodes - SubtreeSizeOfCurrentNode.

Algorithmic pattern used

The pattern is DFS for Subtree Size calculation.

1. First, build an adjacency list if not provided.
2. Perform a DFS to calculate the size of the subtree rooted at every node.
3. For each node, identify the components formed by its removal:
   • Each child's subtree size.
   • The size of the "upper" part: total_nodes - subtree_size[node].
4. Multiply these sizes (using 1 as a placeholder for non-existent components) to get the score.
5. Track the max score and its frequency.

Example explanation

Consider a tree with 5 nodes where 0 is root, 0 has children 1 and 2, and 1 has children 3 and 4.

• Total nodes = 5.
• Subtree sizes: size[3]=1, size[4]=1, size[1]=3, size[2]=1, size[0]=5.
• Score of node 1:
  • Child 3: size 1.
  • Child 4: size 1.
  • Parent side: $5 - 3 = 2$.
  • Score: $1 imes 1 imes 2 = 2$.
• Score of node 0:
  • Child 1: size 3.
  • Child 2: size 1.
  • Parent side: 0 (not used).
  • Score: $3 imes 1 = 3$.

Common mistakes candidates make

A major pitfall is integer overflow. Since we are multiplying subtree sizes, the product can easily exceed the capacity of a 32-bit integer for a tree with $10^5$ nodes. Another mistake is failing to handle the root correctly (it has no parent-side component). Using a 64-bit integer (long) for the score is mandatory.

Interview preparation tip

When a tree problem involves "removing a node" or "splitting the tree," remember that the size of the component containing the parent is always the total size minus the current subtree size. This trick avoids needing a complex multi-directional DFS.