Scale Engineer

Count Nodes With the Highest Score

Med
#1866Time: O(N^2). The main loop runs N times. Inside the loop, for each child of the current node, we call `getSubtreeSize`. In the worst case (a skewed tree), `getSubtreeSize` can take O(N) time. Since this is inside a loop that runs N times, the total time complexity is O(N^2).Space: O(N) to store the adjacency list and for the queue/stack used in the traversal within the loop.2 companies
Algorithms
Depth-First Search
Data structures
ArrayTreeBinary Tree
Companies
DoorDashVisa

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each node of the tree. For each node, it simulates its removal and then performs a graph traversal (like DFS or BFS) on the remaining parts to identify the resulting subtrees. The sizes of these components are multiplied to get the score for the current node. This process is repeated for all nodes, keeping track of the highest score and the count of nodes achieving it.

Algorithm

  • Build an adjacency list adj from the parents array to represent the tree structure, where adj[i] contains the children of node i.
  • Define a helper function, getSubtreeSize(startNode, adj), which performs a traversal (like DFS or BFS) starting from startNode to count all nodes in its subtree. This function takes O(N) time in the worst case.
  • Initialize maxScore = -1L and count = 0.
  • Iterate through each node i from 0 to n-1.
  • For each node i, calculate its score:
    • Initialize currentScore = 1L and nodesBelow = 0.
    • For each child of node i in adj[i]:
      • Call getSubtreeSize(child, adj) to get the size of the child's subtree.
      • Multiply currentScore by this size.
      • Add this size to nodesBelow.
    • Calculate the size of the component 'above' node i. This is parentComponentSize = n - 1 - nodesBelow.
    • If parentComponentSize is greater than 0, multiply currentScore by it.
  • Compare currentScore with maxScore.
    • If currentScore > maxScore, update maxScore = currentScore and set count = 1.
    • If currentScore == maxScore, increment count.
  • After the loop, return count.

Walkthrough

The brute-force method directly implements the score calculation for each node one by one. First, we convert the parents array into a more usable tree structure, like an adjacency list. Then, we loop through every node i from 0 to n-1. For each i, we need to find the sizes of the components that would form if i were removed. These components are the subtrees of i's children and the rest of the tree (containing i's parent).

To find the size of each child's subtree, we can perform a separate traversal (like BFS or DFS) starting from that child. After calculating the sizes of all children's subtrees, we sum them up. The size of the parent component is then n minus 1 (for node i itself) minus the sum of its children's subtree sizes. The score is the product of these component sizes. We use a long to store the score to avoid overflow. We keep track of the maximum score seen so far and how many nodes achieve it.

import java.util.*; class Solution {    public int countHighestScoreNodes(int[] parents) {        int n = parents.length;        List<Integer>[] adj = new ArrayList[n];        for (int i = 0; i < n; i++) {            adj[i] = new ArrayList<>();        }        for (int i = 1; i < n; i++) {            adj[parents[i]].add(i);        }         long maxScore = -1;        int count = 0;         for (int i = 0; i < n; i++) {            long currentScore = 1;            int nodesBelow = 0;             for (int child : adj[i]) {                int childSubtreeSize = getSubtreeSize(child, adj);                currentScore *= childSubtreeSize;                nodesBelow += childSubtreeSize;            }             int parentComponentSize = n - 1 - nodesBelow;            if (parentComponentSize > 0) {                currentScore *= parentComponentSize;            }             if (currentScore > maxScore) {                maxScore = currentScore;                count = 1;            } else if (currentScore == maxScore) {                count++;            }        }        return count;    }     private int getSubtreeSize(int startNode, List<Integer>[] adj) {        int size = 0;        Queue<Integer> queue = new LinkedList<>();        queue.offer(startNode);                while (!queue.isEmpty()) {            int u = queue.poll();            size++;            for (int v : adj[u]) {                queue.offer(v);            }        }        return size;    }}

Complexity

Time

O(N^2). The main loop runs N times. Inside the loop, for each child of the current node, we call `getSubtreeSize`. In the worst case (a skewed tree), `getSubtreeSize` can take O(N) time. Since this is inside a loop that runs N times, the total time complexity is O(N^2).

Space

O(N) to store the adjacency list and for the queue/stack used in the traversal within the loop.

Trade-offs

Pros

  • Conceptually simple and directly follows the problem definition.

Cons

  • Highly inefficient due to redundant calculations. The size of the same subtree is computed multiple times.

  • The time complexity of O(N^2) can be too slow for the given constraints (N up to 10^5), likely resulting in a 'Time Limit Exceeded' error.

Solutions

public class Solution {    private List < int > [] g;    private int ans;    private long mx;    private int n;    public int CountHighestScoreNodes(int[] parents) {        n = parents.Length;        g = new List < int > [n];        for (int i = 0; i < n; ++i) {            g[i] = new List < int > ();        }        for (int i = 1; i < n; ++i) {            g[parents[i]].Add(i);        }        Dfs(0, -1);        return ans;    }    private int Dfs(int i, int fa) {        int cnt = 1;        long score = 1;        foreach(int j in g[i]) {            if (j != fa) {                int 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;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem