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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Nodes With the Highest Score

Number: 2175

Difficulty: Medium

Paid? No

Companies: DoorDash, Amazon, Visa

Problem Description

Given a binary tree represented by a parents array where each element indicates the parent of that node (with node 0 as the root), remove a node (and its connected edges) to partition the tree into a forest of non-empty subtrees. The score of a node is defined as the product of the sizes of each resulting subtree. The task is to determine how many nodes achieve the highest possible score.

Key Insights

  • Use Depth-First Search (DFS) to compute the size of each subtree.
  • When a node is removed, its children form separate subtrees. Also, the "rest of the tree" (nodes not in the removed node's subtree) forms an additional subtree.
  • The node's score is computed as the product of the sizes of all its resulting subtrees.
  • During DFS, update and track the maximum score encountered and count nodes that achieve this score.

Space and Time Complexity

Time Complexity: O(n), since we traverse every node exactly once via DFS.
Space Complexity: O(n), required for storing the tree structure (adjacency list) and the recursion stack in the worst case.

Solution

We first build an adjacency list from the parents array. Then, using DFS starting from the root (node 0), we compute the subtree size for every node. During the DFS, for each node, we calculate its score by multiplying the size of each child's subtree and the size of the "remaining" tree (n - current subtree size, if non-zero). We constantly update the maximum score and count how many nodes have that maximum score. This one-pass DFS ensures optimal performance for large inputs.

Code Solutions

def count_highest_score_nodes(parents):
    n = len(parents)
    # Build the tree as an adjacency list
    tree = [[] for _ in range(n)]
    for child in range(1, n):
        parent = parents[child]
        tree[parent].append(child)
    
    max_score = 0
    count = 0
    
    # DFS function returns the size of the subtree rooted at 'node'
    def dfs(node):
        nonlocal max_score, count
        total_size = 1  # Count the current node
        product = 1   # Initialize product for score computation
        
        # Process every child and update subtree size and product
        for child in tree[node]:
            subtree_size = dfs(child)
            total_size += subtree_size
            product *= subtree_size
        
        # Compute the remaining part (nodes not in the current subtree)
        remaining = n - total_size
        if remaining:
            product *= remaining
        
        # Update max_score and corresponding count
        if product > max_score:
            max_score = product
            count = 1
        elif product == max_score:
            count += 1
        
        return total_size
    
    dfs(0)
    return count

# Example usage:
parents = [-1, 2, 0, 2, 0]
print(count_highest_score_nodes(parents))  # Expected output: 3

if __name__ == "__main__":
    # Additional tests can be added here if desired
    pass
← Back to All Questions