We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Nodes With the Highest Score

Difficulty: Medium

Problem Description

Given a binary tree rooted at node 0 consisting of n nodes, represented by a 0-indexed integer array parents, where parents[i] is the parent of node i, calculate the number of nodes that have the highest score. The score of a node is determined by the product of the sizes of all non-empty subtrees formed by removing the node and its edges.

Key Insights

  • Each node's score is derived from the product of sizes of its child subtrees.
  • The size of a subtree can be calculated using a depth-first search (DFS) traversal.
  • The root node's score takes into account the size of the entire tree minus itself.
  • Keeping track of maximum scores and their occurrences is essential to determine the result.

Space and Time Complexity

Time Complexity: O(n) - We traverse through all nodes in the tree once. Space Complexity: O(n) - Additional space is used for storing the sizes of subtrees and adjacency lists.

Solution

To solve the problem, we can employ a depth-first search (DFS) approach. First, we need to build the tree using an adjacency list representation based on the parents array. Then, we will compute the sizes of subtrees for each node. While calculating the sizes, we can simultaneously compute the scores for each node by multiplying the sizes of its child subtrees and considering the size of the remaining tree. Finally, we identify the maximum score and count how many nodes achieve this score.

Code Solutions

def countHighestScoreNodes(parents):
    from collections import defaultdict
    
    n = len(parents)
    tree = defaultdict(list)
    size = [1] * n  # Initialize sizes
    score = [0] * n  # Initialize scores

    # Build the tree
    for child in range(1, n):
        tree[parents[child]].append(child)

    def dfs(node):
        total_size = 0
        for child in tree[node]:
            subtree_size = dfs(child)
            total_size += subtree_size
            size[node] *= subtree_size  # Calculate the product of sizes
        if total_size > 0:
            size[node] *= (n - total_size)  # Include the remaining tree size
        return total_size + 1  # Return total size including the current node

    dfs(0)  # Start DFS from the root

    max_score = max(size)
    return size.count(max_score)  # Count how many nodes have the maximum score
← Back to All Questions