2049. Count Nodes With the Highest Score
Problem Description
This problem presents a binary tree rooted at node 0
and consisting of n
nodes, each uniquely labeled from 0
to n - 1
. We are given an integer array parents
where each element represents the parent of a corresponding node, such that parents[i]
is the parent of node i
. The root node’s parent is indicated by parents[0]
being -1
.
The score of a node is determined by removing the node along with its connected edges from the tree. This operation results in a number of non-empty subtrees. The size of each subtree is simply the number of nodes it contains. The score for the removed node is calculated as the product of the sizes of all resultant subtrees. The goal is to find out how many nodes in the tree have the highest score.
Flowchart Walkthrough
To determine the appropriate algorithm for LeetCode problem 2049, let's follow the steps outlined in the Flowchart. Below is a systematic breakdown based on the problem description and the criteria in the flowchart:
Is it a graph?
- Yes: The problem involves constructing a tree from a parent array, which forms a graph structure where nodes are elements and edges define parent-child relationships.
Is it a tree?
- Yes: The description specifies that it's formed by a parent array indicating the parent of each node, representing a tree structure.
Does the problem involve topological sort, directed acyclic graphs (DAGs), or shortest paths?
- No to all: The task is about determining which node yields the maximum score when considered as a root of the tree, which doesn’t fall into any of these categories.
Conclusion: Based on the flowchart and the decision paths, Depth-First Search (DFS) is the suggested algorithm. This is because manipulating tree structures often requires a DFS to efficiently traverse nodes and compute values (in this case, scores by division of the tree) recursively. This approach will enable calculation of scores for each possible root by exploring the size of each subtree rooted at different nodes.
Using DFS allows us to evaluate the contribution of each node to the so-called 'score' both when it's included and excluded from sub-trees, hence helping in efficiently counting nodes with the highest possible scores.
Intuition
To solve this problem, we need a way to compute the score of each node efficiently. Instead of actually removing nodes, which would be inefficient, we can simulate the process with a depth-first search (DFS) algorithm. Here’s the logic behind the solution:
- A tree structure often calls for a recursive strategy. DFS is a good fit here as we need to explore subtrees to calculate scores.
- The solution tracks the size of each subtree as the DFS traversal visits the nodes. The size of the subtree rooted at a node is 1 (for the node itself) plus the sizes of all subtrees of its children.
- If a node is removed, the score for that node is the product of the sizes of the subtrees left behind. However, there is one additional "subtree" to consider — the one formed by the rest of the tree outside of this node's subtree. Its size is the total number of nodes in the tree minus the size of the subtree rooted at the given node.
- For the root node, its score is simply the product of the sizes of its child subtrees because there is no "parent" subtree to consider.
- In the recursive DFS function, we track the maximum score found and count how many times nodes with this score occur.
- For each node visited, we calculate a temporary score. If it's greater than the current maximum score, we update the maximum score and reset our count of nodes with the maximum score to 1. If the score matches the current maximum, we increment our count.
- After the DFS completes, the counter will have the number of nodes with the highest score.
Putting it all together, starting the DFS from the root will give us the needed information to return the final count of nodes with the highest score.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
The solution employs a Depth-First Search (DFS) algorithm to compute subtree sizes and uses a simple list (Python's List
data structure) to model the graph (tree) structure.
-
Transformation into a graph: The given
parents
array is used to create an adjacency list that represents the tree. For each node (excluding the root), we append it to a list at the index of its parent. This meansg[i]
will contain a list of all children of thei
th node. -
DFS algorithm: We define a recursive function
dfs
that takes a single argumentcur
, which represents the current node being visited. The function initializes a local variablesize
to1
(for the current node) andscore
to1
(the initial product of subtree sizes). -
Calculating subtree sizes and scores: For every child
c
of the current nodecur
, we recursively calldfs(c)
, which returns the size of the subtree rooted atc
. This value is added to thesize
of the current subtree and also multiplied into thescore
for the current node. -
Handling of the non-subtree part: If the current node is not the root, we need to consider the rest of the tree outside of the current node's subtree. We multiply the current
score
byn - size
to incorporate this. -
Tracking the maximum score and count: We use global variables
max_score
andans
to keep track of the maximum score found so far, and the number of nodes with that score, respectively. If the score of the current node is higher than themax_score
, we updatemax_score
and setans
to1
. If the score is equal tomax_score
, we incrementans
. -
Starting the DFS and returning the result: The DFS is started by calling
dfs(0)
because the root is labeled0
. Once DFS is completed,ans
will hold the count of nodes with the highest score, and this is what is returned.
The elegance of the solution comes from its efficient traversal of the tree using DFS to calculate the scores for all nodes without any modifications to the tree's structure, and clever use of global variables to keep track of the maximum score observed, as well as the count of nodes that achieve this score.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let’s consider a small tree with n = 5
nodes, and the following parents
array representing the tree:
Node index: 0 1 2 3 4 Parents: [-1, 0, 0, 1, 1]
This represents a tree where:
- Node
0
is the root (asparents[0] = -1
). - Nodes
1
and2
are children of node0
. - Nodes
3
and4
are children of node1
.
First, we build the adjacency list based on the parents
array to represent the tree graph:
g[0] -> [1, 2] g[1] -> [3, 4] g[2] -> [] g[3] -> [] g[4] -> []
Now we run the DFS algorithm starting from the root (node 0
). We also initialize our global variables max_score
and ans
to track the maximum score and number of nodes with that maximum score.
-
Start DFS at root node
0
. Initializesize = 1
,score = 1
. -
For every child of node
0
, that is nodes1
and2
, we calldfs(child)
. -
Calling
dfs(1)
:- Start with
size = 1
,score = 1
. - Visit children of node
1
, which are nodes3
and4
. - Call
dfs(3)
, which returns1
because it has no children, adding this tosize
of node1
and settingscore = score * size_subtree(3) = 1
. - Call
dfs(4)
, similar todfs(3)
, return1
, adding tosize
of node1
, andscore = score * size_subtree(4) = 1
. - Final
size
of subtree at node1
is3
, and thescore
for node1
when removing it would bescore * (n - size) = 1 * (5 - 3) = 2
. Updatemax_score
to2
andans
to1
.
- Start with
-
Back to node
0
, now callingdfs(2)
:- Node
2
has no children, so it returns a size of1
. - Add
1
to size of node0
which is now5
(the total size of the tree).
- Node
-
With DFS complete for node
0
, node0
score would be the product of subtree sizes of its children, which are nodes1
and2
. Soscore = size_subtree(1) * size_subtree(2) = 3 * 1 = 3
. Themax_score
is less than3
, so we updatemax_score
to3
and resetans
to1
. -
DFS has now visited all nodes. Since no other nodes will have a score higher than
3
(the score when the root is removed), we conclude that the highest score is3
, and there is only1
node (the root, node0
) with this score.
Based on the solution approach, we return ans
, which is 1
, indicating there is one node (the root) with the highest score in the tree.
Solution Implementation
1from typing import List
2
3class Solution:
4 def countHighestScoreNodes(self, parents: List[int]) -> int:
5 # Initialize the number of nodes, maximum score, and answer counter.
6 num_nodes = len(parents)
7 max_score = 0
8 answer = 0
9
10 # Graph representation of the tree, with each node pointing to its children.
11 graph = [[] for _ in range(num_nodes)]
12
13 # Build the adjacency list for each parent.
14 for i in range(1, num_nodes):
15 graph[parents[i]].append(i)
16
17 # Depth-First Search to compute subtree sizes and scores.
18 def dfs(current_node: int) -> int:
19 nonlocal max_score, answer
20 subtree_size = 1
21 node_score = 1
22
23 # Visit each child and calculate the score contribution of its subtree.
24 for child in graph[current_node]:
25 child_subtree_size = dfs(child)
26 subtree_size += child_subtree_size
27 node_score *= child_subtree_size
28
29 # If not the root, multiply by the size of the "complement" subtree.
30 if current_node > 0:
31 node_score *= num_nodes - subtree_size
32
33 # Update answer and max_score in case of new max or equal score found.
34 if node_score > max_score:
35 max_score = node_score
36 answer = 1
37 elif node_score == max_score:
38 answer += 1
39
40 return subtree_size
41
42 # Start DFS from the root of the tree (node 0).
43 dfs(0)
44
45 # Return the number of nodes that have the maximum score.
46 return answer
47
1class Solution {
2
3 private int nodeCount; // Total number of nodes in the tree
4 private long maximumScore; // The highest score found so far
5 private int countOfMaxScoreNodes; // The count of nodes having the maximum score
6 private List<List<Integer>> childrenList; // Adjacency list representation of the tree
7
8 public int countHighestScoreNodes(int[] parents) {
9 nodeCount = parents.length;
10 maximumScore = 0;
11 countOfMaxScoreNodes = 0;
12 childrenList = new ArrayList<>();
13
14 // Initialize lists to hold children nodes for each node
15 for (int i = 0; i < nodeCount; i++) {
16 childrenList.add(new ArrayList<>());
17 }
18
19 // Build the adjacency list (tree graph) from the parent array
20 for (int i = 1; i < nodeCount; i++) {
21 childrenList.get(parents[i]).add(i);
22 }
23
24 // Start Depth-First Search from the root node (0)
25 dfs(0);
26
27 // Return the count of nodes that have the highest score
28 return countOfMaxScoreNodes;
29 }
30
31 // A method to perform a DFS and calculate the size and score of the current subtree
32 private int dfs(int currentNode) {
33 int subTreeSize = 1; // Current node's size is at least 1 (itself)
34 long score = 1; // Initialize score for the current node
35
36 // Iterate through the children of the current node
37 for (int child : childrenList.get(currentNode)) {
38 int childSubTreeSize = dfs(child); // Recursively get child subtree size
39
40 // Accumulate total subtree size and compute the score contribution of this child
41 subTreeSize += childSubTreeSize;
42 score *= childSubTreeSize;
43 }
44
45 // For non-root nodes, multiply the score with the size of the "rest of the tree"
46 if (currentNode > 0) {
47 score *= (nodeCount - subTreeSize);
48 }
49
50 // Compare and update the maximum score and the count of nodes
51 if (score > maximumScore) {
52 maximumScore = score;
53 countOfMaxScoreNodes = 1;
54 } else if (score == maximumScore) {
55 countOfMaxScoreNodes++;
56 }
57
58 // Return the subtree size
59 return subTreeSize;
60 }
61}
62
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 // Member variables to keep track of the total count of nodes with the highest score.
8 // Also to keep record of the current maximum score and the total number of nodes.
9 int countOfMaxScoreNodes;
10 long long maxNodeScore;
11 int numNodes;
12
13 // Function to start the process and return the number of nodes with the highest score
14 int countHighestScoreNodes(vector<int>& parents) {
15 countOfMaxScoreNodes = 0; // Initialize count of nodes with maximum score to zero
16 maxNodeScore = 0; // Initialize maximum score to zero
17 numNodes = parents.size(); // Set total number of nodes
18 unordered_map<int, vector<int>> graph; // Create a graph from the parent array
19
20 // Building the graph from the parent-child relationships
21 for (int i = 1; i < numNodes; ++i) {
22 graph[parents[i]].push_back(i);
23 }
24
25 // Start the DFS traversal from the root node, which is node 0
26 dfs(0, graph);
27
28 // Return the total count of nodes with the maximum score
29 return countOfMaxScoreNodes;
30 }
31
32 // DFS function to calculate the score of each node and the size of the subtree rooted at each node
33 int dfs(int node, unordered_map<int, vector<int>>& graph) {
34 int subtreeSize = 1; // Size of the subtree including the current node
35 long long nodeScore = 1; // Product of the sizes of each subtree
36
37 // For every child of the current node
38 for (int child : graph[node]) {
39 int childSubtreeSize = dfs(child, graph); // Recursive DFS call
40 subtreeSize += childSubtreeSize; // Update the size of the current subtree
41 nodeScore *= childSubtreeSize; // Update the score by multiplying the sizes of subtrees
42 }
43
44 // If the node is not the root, multiply node score by the size of the "rest of the tree"
45 if (node > 0) {
46 nodeScore *= (numNodes - subtreeSize);
47 }
48
49 // Update maxNodeScore and countOfMaxScoreNodes based on the calculated score for this node
50 if (nodeScore > maxNodeScore) { // Found a new maximum score
51 maxNodeScore = nodeScore;
52 countOfMaxScoreNodes = 1; // Reset count because we found a new maximum
53 } else if (nodeScore == maxNodeScore) {
54 ++countOfMaxScoreNodes; // Increment count because we found another node with the maximum score
55 }
56
57 // Return the total size of the subtree rooted at the current node
58 return subtreeSize;
59 }
60};
61
1/**
2 * This function counts the number of nodes in a tree that have the highest score.
3 * The score of each node is calculated as the product of the sizes of its subtrees,
4 * and if the node is not the root, then the size of the remaining tree is also considered.
5 *
6 * @param parents - an array where `parents[i]` is the parent of the `i`th node.
7 * @returns the number of nodes with the highest score.
8 */
9function countHighestScoreNodes(parents: number[]): number {
10 // The number of nodes in the tree
11 const nodeCount = parents.length;
12
13 // An adjacency list to store the tree, with each index representing a node and storing its children.
14 let edges = Array.from({ length: nodeCount }, () => []);
15
16 // Constructing the tree
17 for (let i = 0; i < nodeCount; i++) {
18 const parent = parents[i];
19 if (parent !== -1) {
20 edges[parent].push(i);
21 }
22 }
23
24 // Initialize the count of nodes with the maximum score and the maximum score itself
25 let maxScoreNodeCount = 0;
26 let maxScore = 0;
27
28 /**
29 * A depth-first search function that calculates the size of the subtree rooted at this index
30 * and the score for the current node.
31 *
32 * @param index - The current node index we are calculating size and score for
33 * @returns The size of the subtree rooted at the given index
34 */
35 function dfs(index: number): number {
36 let subtreeSize = 1;
37 let nodeScore = 1;
38
39 // Traversing children to calculate score and subtree sizes
40 for (const childIndex of edges[index]) {
41 const childSubtreeSize = dfs(childIndex);
42 subtreeSize += childSubtreeSize;
43 nodeScore *= childSubtreeSize;
44 }
45
46 // If the node is not root, the remaining tree size is also part of the score
47 if (index > 0) {
48 nodeScore *= nodeCount - subtreeSize;
49 }
50
51 // If the calculated score for the current node is higher than the recorded max, update it
52 if (nodeScore > maxScore) {
53 maxScore = nodeScore;
54 maxScoreNodeCount = 1;
55 } else if (nodeScore === maxScore) {
56 // If the current node has a score equal to the max, increment the count
57 maxScoreNodeCount++;
58 }
59
60 return subtreeSize;
61 }
62
63 // Start DFS from the root node (index 0)
64 dfs(0);
65
66 return maxScoreNodeCount;
67}
68
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the number of nodes in the tree. The code uses a Depth-First Search (DFS) traversal to compute the size and score for each node exactly once. For each node, it looks into its children and calculates the score based on the size of the subtrees which are the results of the DFS calls. These operations all happen within the DFS function which is called once per node, leading to a linear time complexity with respect to the number of nodes.
Space Complexity
The space complexity of the code can also be considered O(n)
for several reasons:
- The adjacency list
g
, which represents the tree, will contain a maximum ofn-1
edges, as it is a tree. - The recursive DFS will at most be called recursively for a depth equal to the height of the tree. In the worst case (a skewed tree), the recursive call stack could also be
O(n)
. - The auxiliary space required by the internal state of the DFS (variables like
size
,score
, and the returned values) will not exceedO(1)
per call.
But, typically, the tree height is much less than n
for a reasonably balanced tree, so the average case for the space complexity due to recursive calls is less than O(n)
. However, since the worst-case scenario can still be O(n)
(for a skewed tree), we mention it as such.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Want a Structured Path to Master System Design Too? Don’t Miss This!