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

Array Tree Binary Tree

Companies

DoorDash Visa

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:

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.length
2 <= n <= 10⁵
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.

1import java.util.*;2 3class Solution {4    public int countHighestScoreNodes(int[] parents) {5        int n = parents.length;6        List<Integer>[] adj = new ArrayList[n];7        for (int i = 0; i < n; i++) {8            adj[i] = new ArrayList<>();9        }10        for (int i = 1; i < n; i++) {11            adj[parents[i]].add(i);12        }13 14        long maxScore = -1;15        int count = 0;16 17        for (int i = 0; i < n; i++) {18            long currentScore = 1;19            int nodesBelow = 0;20 21            for (int child : adj[i]) {22                int childSubtreeSize = getSubtreeSize(child, adj);23                currentScore *= childSubtreeSize;24                nodesBelow += childSubtreeSize;25            }26 27            int parentComponentSize = n - 1 - nodesBelow;28            if (parentComponentSize > 0) {29                currentScore *= parentComponentSize;30            }31 32            if (currentScore > maxScore) {33                maxScore = currentScore;34                count = 1;35            } else if (currentScore == maxScore) {36                count++;37            }38        }39        return count;40    }41 42    private int getSubtreeSize(int startNode, List<Integer>[] adj) {43        int size = 0;44        Queue<Integer> queue = new LinkedList<>();45        queue.offer(startNode);46        47        while (!queue.isEmpty()) {48            int u = queue.poll();49            size++;50            for (int v : adj[u]) {51                queue.offer(v);52            }53        }54        return size;55    }56}

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.

This optimal approach avoids redundant computations by using a single Depth First Search (DFS) traversal. It calculates the size of each node's subtree in a post-order manner. Once the sizes of a node's children subtrees are known (after the recursive calls for its children return), we can immediately calculate the size of the parent component and thus the node's score. This combines subtree size calculation and score evaluation into one efficient pass.

Algorithm

Build an adjacency list adj from the parents array.
Initialize global variables maxScore = -1L and count = 0.
Create a recursive DFS function, dfs(node), that returns the size of the subtree rooted at node.
Inside dfs(node):
- Initialize mySize = 1 (for the node itself) and score = 1L.
- For each child of node:
  - Recursively call childSize = dfs(child).
  - Multiply score by childSize.
  - Add childSize to mySize.
- Calculate the size of the parent component: parentSize = n - mySize.
- If parentSize > 0, multiply score by parentSize.
- Compare the calculated score with the global maxScore. Update maxScore and count accordingly.
- Return mySize.
Start the process by calling dfs(0) on the root node.
After the traversal is complete, return the final count.

Walkthrough

The key to an efficient solution is to avoid re-calculating subtree sizes. A single post-order traversal of the tree can achieve this. We define a recursive function, let's call it dfs(node), which will compute and return the size of the subtree rooted at node.

During the traversal, after visiting all of a node's children and getting their subtree sizes from the recursive calls, we are at the 'post-order' step for the current node. At this point, we have all the information needed to calculate its score:

The sizes of the subtrees for each of its children.
The size of the current node's own subtree, which is 1 (for itself) plus the sum of its children's subtree sizes.
The size of the parent component, which is the total number of nodes n minus the size of the current node's subtree.

The score is the product of these component sizes. We must handle cases where a component might be empty (e.g., a leaf has no children, the root has no parent). A simple way is to multiply by a component's size only if it's greater than zero. We use a long for the score to prevent overflow. As we compute the score for each node during the traversal, we update a global maximum score and the count of nodes achieving it.

1import java.util.*;2 3class Solution {4    private long maxScore;5    private int count;6    private int n;7    private List<Integer>[] adj;8 9    public int countHighestScoreNodes(int[] parents) {10        this.n = parents.length;11        this.adj = new ArrayList[n];12        for (int i = 0; i < n; i++) {13            adj[i] = new ArrayList<>();14        }15        for (int i = 1; i < n; i++) {16            adj[parents[i]].add(i);17        }18 19        this.maxScore = -1;20        this.count = 0;21 22        dfs(0);23 24        return count;25    }26 27    private int dfs(int node) {28        long score = 1;29        int subtreeSize = 1;30 31        for (int child : adj[node]) {32            int childSubtreeSize = dfs(child);33            score *= childSubtreeSize;34            subtreeSize += childSubtreeSize;35        }36 37        int parentComponentSize = n - subtreeSize;38        if (parentComponentSize > 0) {39            score *= parentComponentSize;40        }41 42        if (score > maxScore) {43            maxScore = score;44            count = 1;45        } else if (score == maxScore) {46            count++;47        }48 49        return subtreeSize;50    }51}

Complexity

Time

O(N). The DFS-based approach visits each node and edge of the tree exactly once. All operations performed at each node are constant time (excluding the recursive calls).

Space

O(N). This space is used for the adjacency list and the recursion call stack. In the worst-case scenario of a skewed tree, the recursion depth can be O(N).

Trade-offs

Pros

Extremely efficient with optimal time complexity.
Solves the problem in a single pass over the tree, avoiding any redundant work.
Elegant and concise implementation using recursion.

Cons

The recursive implementation might lead to a StackOverflowError for extremely deep, skewed trees, although this is unlikely given the problem constraints and typical system stack sizes.

Solutions

Solution

1public class Solution {2    private List < int > [] g;3    private int ans;4    private long mx;5    private int n;6    public int CountHighestScoreNodes(int[] parents) {7        n = parents.Length;8        g = new List < int > [n];9        for (int i = 0; i < n; ++i) {10            g[i] = new List < int > ();11        }12        for (int i = 1; i < n; ++i) {13            g[parents[i]].Add(i);14        }15        Dfs(0, -1);16        return ans;17    }18    private int Dfs(int i, int fa) {19        int cnt = 1;20        long score = 1;21        foreach(int j in g[i]) {22            if (j != fa) {23                int t = Dfs(j, i);24                cnt += t;25                score *= t;26            }27        }28        if (n - cnt > 0) {29            score *= n - cnt;30        }31        if (mx < score) {32            mx = score;33            ans = 1;34        } else if (mx == score) {35            ++ans;36        }37        return cnt;38    }39}

1class Solution {2private3  List<Integer>[] g;4private5  int ans;6private7  long mx;8private9  int n;10public11  int countHighestScoreNodes(int[] parents) {12    n = parents.length;13    g = new List[n];14    Arrays.setAll(g, i->new ArrayList<>());15    for (int i = 1; i < n; ++i) {16      g[parents[i]].add(i);17    }18    dfs(0, -1);19    return ans;20  }21private22  int dfs(int i, int fa) {23    int cnt = 1;24    long score = 1;25    for (int j : g[i]) {26      if (j != fa) {27        int t = dfs(j, i);28        cnt += t;29        score *= t;30      }31    }32    if (n - cnt > 0) {33      score *= n - cnt;34    }35    if (mx < score) {36      mx = score;37      ans = 1;38    } else if (mx == score) {39      ++ans;40    }41    return cnt;42  }43}

1class Solution {2public:3  int countHighestScoreNodes(vector<int> &parents) {4    int n = parents.size();5    vector<int> g[n];6    for (int i = 1; i < n; ++i) {7      g[parents[i]].push_back(i);8    }9    int ans = 0;10    long long mx = 0;11    function<int(int, int)> dfs = [&](int i, int fa) {12      long long score = 1;13      int cnt = 1;14      for (int j : g[i]) {15        if (j != fa) {16          int t = dfs(j, i);17          cnt += t;18          score *= t;19        }20      }21      if (n - cnt) {22        score *= n - cnt;23      }24      if (mx < score) {25        mx = score;26        ans = 1;27      } else if (mx == score) {28        ++ans;29      }30      return cnt;31    };32    dfs(0, -1);33    return ans;34  }35};

1class Solution:2    def countHighestScoreNodes(self, parents: List[int]) -> int: def dfs(i: int, fa: int): cnt = score = 1 for j in g[i]: if j != fa: t = dfs(j, i) score *= t cnt += t if n - cnt: score *= n - cnt nonlocal ans, mx if mx < score: mx = score ans = 1 elif mx == score: ans += 1 return cnt n = len(parents) g = [[] for _ in range(n)] for i in range(1, n): g[parents[i]]. append(i) ans = mx = 0 dfs(0, - 1) return ans

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 problem