LeetCode 2049 - Count Nodes With the Highest Score

LeetCode Problem 2049

Difficulty: 🟡 Medium
Topics: Array, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The input describes a rooted binary tree using a parent array. Every node is identified by an integer from 0 to n - 1, and parents[i] tells us which node is the parent of node i. The root node is always 0, so its parent is -1.

The goal is to compute a score for every node. To calculate the score of a node, we imagine removing that node and all edges connected to it. This breaks the original tree into several disconnected subtrees. The score is the product of the sizes of all resulting non-empty subtrees.

For example, suppose removing a node creates three disconnected parts with sizes 2, 4, and 5. The score for that node would be:

2 * 4 * 5 = 40

The task is not to return the highest score itself. Instead, we must count how many nodes achieve that highest score.

The constraints are important:

• n can be as large as 10^5
• The structure is guaranteed to be a valid binary tree
• Every node has at most two children

Since n is very large, any solution that repeatedly traverses the tree for each node would be too slow. We need an algorithm close to linear time.

There are several important edge cases to keep in mind:

• The root node behaves differently because removing it does not leave a "parent side" subtree.
• Leaf nodes behave differently because removing them leaves only the remaining tree.
• Scores can become very large because they are products of subtree sizes, so we must use sufficiently large integer types.
• Some resulting subtree sizes may be zero. These should not be included in the product because the problem only considers non-empty subtrees.

Approaches

Brute Force Approach

A straightforward approach is to process every node independently.

For each node:

1. Remove the node conceptually.
2. Determine all connected components that remain.
3. Compute the size of each component using DFS or BFS.
4. Multiply the component sizes together.
5. Track the maximum score and its frequency.

This approach is correct because it directly simulates the definition of the score.

However, it is far too slow. For each node, we may need to traverse nearly the entire tree again to compute component sizes. Since there are n nodes, the total complexity becomes approximately O(n^2).

With n = 10^5, this would be infeasible.

Optimal Approach

The key insight is that removing a node splits the tree into at most three parts:

1. The left subtree
2. The right subtree
3. The remaining part of the tree above the node

If we already know the size of every subtree, we can compute the score of a node immediately.

Suppose:

• left_size is the size of the left subtree
• right_size is the size of the right subtree
• remaining = n - 1 - left_size - right_size

Then the score is:

left_size * right_size * remaining

except we skip any component whose size is zero.

This suggests a DFS solution:

• Build the child adjacency list from the parent array.
• Use DFS to compute subtree sizes.
• While returning from DFS, compute each node's score.
• Track the highest score and how many nodes achieve it.

Because every node is visited only once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Recomputes subtree/component sizes for every node
Optimal	O(n)	O(n)	Single DFS computes subtree sizes and scores simultaneously

Algorithm Walkthrough

1. Build a children adjacency list from the parents array.

Since the input only tells us each node's parent, we first convert it into a structure that allows downward traversal. For every node i > 0, we append i to children[parents[i]]. 2. Initialize variables for tracking the best score.

We maintain:

• max_score, the largest score seen so far
• count, the number of nodes achieving that score

3. Perform a depth-first search starting from the root.

The DFS function returns the size of the subtree rooted at the current node. 4. Recursively compute subtree sizes for all children.

For each child:

• Call DFS recursively
• Store the returned subtree size
• Add it to the current subtree size

5. Compute the size of the remaining tree.

After calculating all child subtree sizes, the part of the tree outside the current subtree has size:

n - subtree_size

6. Compute the node's score.

Start with score = 1.

For every child subtree size:

• Multiply it into the score

If the remaining tree size is greater than zero:

• Multiply it into the score

We exclude zero-sized components because the problem only counts non-empty subtrees. 7. Update the global maximum score.

• If the current score is larger than max_score, update the maximum and reset the count to 1.
• If the current score equals max_score, increment the count.

8. Return the subtree size.

The subtree size is:

1 + sum(child subtree sizes)

The 1 accounts for the current node itself.

Why it works

The DFS guarantees that before computing a node's score, we already know the sizes of all its child subtrees. Removing a node partitions the tree exactly into its child subtrees and the remaining parent-side component. These components are disjoint and collectively contain every other node in the tree. Therefore, multiplying their sizes exactly matches the score definition from the problem statement.

Python Solution

from typing import List

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        n = len(parents)

        children = [[] for _ in range(n)]

        for node in range(1, n):
            parent = parents[node]
            children[parent].append(node)

        max_score = 0
        count = 0

        def dfs(node: int) -> int:
            nonlocal max_score, count

            subtree_size = 1
            score = 1

            for child in children[node]:
                child_size = dfs(child)

                subtree_size += child_size
                score *= child_size

            remaining_size = n - subtree_size

            if remaining_size > 0:
                score *= remaining_size

            if score > max_score:
                max_score = score
                count = 1
            elif score == max_score:
                count += 1

            return subtree_size

        dfs(0)

        return count

The implementation begins by constructing the children adjacency list. This converts the parent representation into a tree structure suitable for DFS traversal.

The dfs function computes the subtree size for a node. It starts with size 1 because the subtree always contains the node itself.

For each child, DFS recursively computes the child's subtree size. That size contributes in two ways:

• It increases the current subtree size
• It contributes multiplicatively to the node's score

After processing all children, we compute the size of the remaining component outside the current subtree. If this component is non-empty, we multiply it into the score.

The global variables max_score and count track the best score encountered so far and how many nodes achieve it.

Finally, the DFS returns the subtree size so the parent can use it in its own calculations.

Go Solution

func countHighestScoreNodes(parents []int) int {
	n := len(parents)

	children := make([][]int, n)

	for node := 1; node < n; node++ {
		parent := parents[node]
		children[parent] = append(children[parent], node)
	}

	var maxScore int64 = 0
	count := 0

	var dfs func(int) int

	dfs = func(node int) int {
		subtreeSize := 1
		score := int64(1)

		for _, child := range children[node] {
			childSize := dfs(child)

			subtreeSize += childSize
			score *= int64(childSize)
		}

		remainingSize := n - subtreeSize

		if remainingSize > 0 {
			score *= int64(remainingSize)
		}

		if score > maxScore {
			maxScore = score
			count = 1
		} else if score == maxScore {
			count++
		}

		return subtreeSize
	}

	dfs(0)

	return count
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is integer handling. Scores can become very large because they are products of subtree sizes, so the implementation uses int64 for score calculations.

The adjacency list is implemented using slices of integer slices:

children := make([][]int, n)

The DFS function is declared as a recursive closure using:

var dfs func(int) int

This allows the function to reference itself recursively.

Worked Examples

Example 1

parents = [-1,2,0,2,0]

Step 1: Build the Tree

The tree structure becomes:

        0
       / \
      2   4
     / \
    1   3

Adjacency list:

Node	Children
0	[2, 4]
1	[]
2	[1, 3]
3	[]
4	[]

Step 2: DFS Traversal

We process nodes bottom-up.

Node 1

• No children
• Subtree size = 1
• Remaining tree size = 5 - 1 = 4
• Score = 4

Node	Child Sizes	Remaining	Score
1	[]	4	4

Node 3

• No children
• Subtree size = 1
• Remaining = 4
• Score = 4

Node	Child Sizes	Remaining	Score
3	[]	4	4

Node 2

Children:

• Node 1 subtree size = 1
• Node 3 subtree size = 1

Subtree size:

1 + 1 + 1 = 3

Remaining:

5 - 3 = 2

Score:

1 * 1 * 2 = 2

Node	Child Sizes	Remaining	Score
2	[1, 1]	2	2

Node 4

• No children
• Remaining = 4
• Score = 4

Node	Child Sizes	Remaining	Score
4	[]	4	4

Node 0

Children:

• Node 2 subtree size = 3
• Node 4 subtree size = 1

Subtree size:

1 + 3 + 1 = 5

Remaining:

0

Score:

3 * 1 = 3

Node	Child Sizes	Remaining	Score
0	[3, 1]	0	3

Highest score is 4.

Nodes achieving it:

• 1
• 3
• 4

Final answer:

3

Example 2

parents = [-1,2,0]

Step 1: Build the Tree

    0
   /
  2
 /
1

Adjacency list:

Node	Children
0	[2]
1	[]
2	[1]

Step 2: DFS Traversal

Node 1

• Subtree size = 1
• Remaining = 2
• Score = 2

Node 2

• Child subtree size = 1
• Remaining = 1
• Score = 1 * 1 = 1

Node 0

• Child subtree size = 2
• Remaining = 0
• Score = 2

Node	Score
0	2
1	2
2	1

Highest score is 2.

Number of nodes with highest score:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once during DFS
Space	O(n)	Adjacency list and recursion stack both require linear space

The DFS traversal processes each node exactly one time, and every edge is traversed once. Since a tree with n nodes has n - 1 edges, the total runtime is linear.

The adjacency list stores all edges, requiring O(n) space. The recursion stack may also reach O(n) depth in the worst case of a completely skewed tree.

Test Cases

from typing import List

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        n = len(parents)

        children = [[] for _ in range(n)]

        for node in range(1, n):
            children[parents[node]].append(node)

        max_score = 0
        count = 0

        def dfs(node: int) -> int:
            nonlocal max_score, count

            subtree_size = 1
            score = 1

            for child in children[node]:
                child_size = dfs(child)
                subtree_size += child_size
                score *= child_size

            remaining = n - subtree_size

            if remaining > 0:
                score *= remaining

            if score > max_score:
                max_score = score
                count = 1
            elif score == max_score:
                count += 1

            return subtree_size

        dfs(0)

        return count

solution = Solution()

assert solution.countHighestScoreNodes([-1,2,0,2,0]) == 3  # Example 1
assert solution.countHighestScoreNodes([-1,2,0]) == 2  # Example 2

assert solution.countHighestScoreNodes([-1,0]) == 2  # Smallest valid tree

assert solution.countHighestScoreNodes([-1,0,1,2,3]) == 3  # Skewed chain

assert solution.countHighestScoreNodes([-1,0,0,1,1,2,2]) == 1  # Complete binary tree

assert solution.countHighestScoreNodes([-1,0,0,0]) == 3  # Root with multiple leaves

assert solution.countHighestScoreNodes([-1,0,1,1,2,2]) == 2  # Mixed subtree sizes

assert solution.countHighestScoreNodes([-1,0,0,1,3]) == 3  # Unbalanced tree

print("All tests passed.")

Test	Why
[-1,2,0,2,0]	Validates the first provided example
[-1,2,0]	Validates the second provided example
[-1,0]	Tests the minimum tree size
[-1,0,1,2,3]	Tests a completely skewed tree
[-1,0,0,1,1,2,2]	Tests a balanced binary tree
[-1,0,0,0]	Tests multiple leaf nodes under the root
[-1,0,1,1,2,2]	Tests uneven subtree distributions
[-1,0,0,1,3]	Tests an unbalanced structure

Edge Cases

Root Node Removal

The root node is special because removing it does not leave any "parent-side" component. A common bug is accidentally multiplying by zero for the missing remaining subtree.

The implementation handles this correctly by only multiplying the remaining component when its size is greater than zero:

if remaining_size > 0:
    score *= remaining_size

This ensures the root's score only includes its actual child subtrees.

Leaf Nodes

Leaf nodes have no children. Removing a leaf leaves the entire remaining tree as a single component.

For example, in a tree of size n, removing a leaf produces exactly one component of size n - 1.

The DFS naturally handles this because the child loop does not execute, leaving:

score = 1

Then the remaining component is multiplied in.

Highly Skewed Trees

A tree may degenerate into a linked list, where every node has exactly one child. This creates the maximum possible recursion depth.

The algorithm still works correctly because each node's subtree size is computed from the bottom upward. Even though the recursion depth becomes O(n), the total work remains linear.

This case is important because many incorrect solutions accidentally recompute subtree sizes repeatedly, causing quadratic runtime on skewed trees.