#2049

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Count Nodes With the Highest Score

Find the number of nodes with the highest score in a binary tree, based on subtree sizes and node removal.

array tree depth first search binary tree

Problem Statement

You are given a binary tree rooted at node 0 with n nodes labeled from 0 to n-1. The tree structure is described by the integer array parents, where parents[i] represents the parent of node i. Node 0 is the root, so parents[0] is -1.

Each node has a score that is calculated by removing that node and the edges connected to it, dividing the tree into subtrees. The score of a node is the product of the sizes of all those subtrees. Your task is to find the number of nodes that have the highest score.

Examples

Example 1

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

Output: 3

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

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.

Solution Approach

DFS for Subtree Sizes

A Depth-First Search (DFS) is used to traverse the tree starting from the root. During this traversal, calculate the size of the subtree rooted at each node. This helps to determine the potential score of each node when it is removed.

Calculate Node Scores

For each node, calculate its score by considering the sizes of the subtrees formed by its children. The score is the product of the subtree sizes, and it involves handling edge cases where the node is the root or has no children.

Track Maximum Score and Count Nodes

Once all scores are computed, identify the maximum score. Then, iterate through the nodes to count how many nodes have the maximum score. This gives the final result for the problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of nodes in the tree, as we need to traverse the tree once with DFS. The space complexity is O(n) due to the recursion stack and storage for the subtree sizes.

What Interviewers Usually Probe

A candidate who correctly identifies the need for DFS traversal and state tracking will perform well.
Candidates should be comfortable with tree traversal and recognizing the implications of removing nodes in terms of subtree sizes.
Look for clarity in how candidates compute the scores and handle edge cases, particularly the root node.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly compute the subtree sizes, especially for the root node or leaf nodes.
Not handling cases where the node has no children or only one child correctly, leading to inaccurate score calculations.
Overcomplicating the solution or missing the need for DFS traversal to efficiently calculate subtree sizes.

Follow-up variants

Change the tree structure to allow more than two children per node, which will require adjusting the approach for calculating subtree sizes.
Introduce constraints where some nodes can be removed but not others, changing the calculation of scores based on node removal eligibility.
Modify the problem to consider multiple trees (forest) and determine the highest score across all trees combined.

FAQ

What is the main approach to solve the 'Count Nodes With the Highest Score' problem?

The main approach is to use Depth-First Search (DFS) to calculate the size of subtrees for each node and then compute the score based on these sizes.

How do you calculate the score of a node in this problem?

The score of a node is calculated by multiplying the sizes of the subtrees formed when that node is removed, including the sizes of its children and the remainder of the tree.

What is the time complexity of solving the 'Count Nodes With the Highest Score' problem?

The time complexity is O(n), where n is the number of nodes, because we traverse the tree once using DFS to calculate the scores.

How do you handle edge cases, like the root or leaf nodes, in this problem?

Edge cases like the root or leaf nodes are handled by properly calculating the size of their respective subtrees, even if they have no children or only one child.

What pattern does this problem mainly focus on?

This problem focuses on binary-tree traversal and state tracking, especially calculating subtree sizes and node scores during DFS traversal.

terminal

Solution

Solution 1: DFS

First, we construct a graph $g$ based on the given parent array `parents`, where $g[i]$ represents all child nodes of node $i$. We define a variable $ans$ to represent the number of nodes with the highest score, and a variable $mx$ to represent the highest score.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    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

Continue Practicing

#2458 height of binary tree after subtree removal queries #2476 closest nodes queries in a binary search tree #1110 delete nodes and return forest