grid47 Exploring patterns and algorithms
Sep 17, 2024
6 min read
Solution to LeetCode 508: Most Frequent Subtree Sum Problem
Given the root of a binary tree, return the most frequent subtree sum. A subtree sum is the sum of all the node values in the subtree rooted at any node, including the node itself. If there is a tie, return all the subtree sums with the highest frequency.
Problem
Approach
Steps
Complexity
Input: The input is the root node of a binary tree with integer values.
Example: [5, 2, -3]
Constraints:
• 1 <= Number of nodes <= 10^4
• -10^5 <= Node.val <= 10^5
Output: The output should be a list of the most frequent subtree sums.
Example: [2, -3, 4]
Constraints:
• The output list contains the most frequent subtree sums, with no specific order.
Goal: The goal is to identify the most frequent subtree sum(s) by traversing the tree and calculating the sum of each subtree.
Steps:
• 1. Perform a depth-first search (DFS) on the tree.
• 2. Calculate the sum of each subtree and keep track of their frequencies.
• 3. Identify the subtree sum(s) with the highest frequency.
• 4. Return the list of those sums.
Goal: The tree contains at least one node, and the number of nodes is within the specified limit.
Steps:
• 1 <= Number of nodes <= 10^4
• -10^5 <= Node.val <= 10^5
Assumptions:
• The binary tree is well-formed and follows valid tree structure rules.
• The values of the nodes are integers, and they may be negative.
• Input: [5, 2, -3]
• Explanation: In this example, the subtree sums are calculated as follows: the sum of the subtree rooted at 5 is 5 + 2 + (-3) = 4; the sum of the subtree rooted at 2 is 2; the sum of the subtree rooted at -3 is -3. Therefore, the most frequent sums are [2, -3, 4].
Approach: We will perform a depth-first search (DFS) on the tree, calculate the subtree sums, and track the frequency of each sum. The most frequent sums will be identified and returned.
Observations:
• DFS allows us to calculate the sum of each subtree while traversing the tree.
• We need a data structure to store the frequencies of each subtree sum.
• We can use a map or hash map to track the frequency of each sum. After the DFS, we will identify the sums with the highest frequency.
Steps:
• 1. Initialize a map to store the frequency of each subtree sum.
• 2. Perform DFS on the tree, calculate the sum for each node, and update the frequency map.
• 3. Track the maximum frequency encountered.
• 4. Collect all sums with the highest frequency and return them.
Empty Inputs:
• The tree will always have at least one node, so this case does not occur.
Large Inputs:
• The solution should handle trees with up to 10,000 nodes efficiently.
Special Values:
• Nodes with negative values should be correctly handled in the sum calculations.
Constraints:
• The algorithm should ensure that it works efficiently within the given constraints.
classSolution {
int mx;
public:vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> ans;
map<int, int> mp;
mx =0;
dfs(root, mp, ans);
return ans;
}
intdfs(TreeNode* root, map<int, int>& mp, vector<int>& ans) {
if (root ==NULL) return0;
int res;
if (root->left ==NULL&& root->right ==NULL)
{ res = root->val; }
else {
int l = dfs(root->left , mp, ans);
int r = dfs(root->right, mp, ans);
res = l + r + root->val;
}
mp[res] +=1;
if(mx < mp[res]) {
ans.clear();
ans.push_back(res);
mx = mp[res];
} elseif(mx == mp[res]) {
ans.push_back(res);
}
return res;
}
1 : Variable Initialization
int mx;
A variable to keep track of the maximum frequency of the tree sums.
2 : Access Modifiers
public:
Public section where the function definitions are accessible.
3 : Function Definition
vector<int> findFrequentTreeSum(TreeNode* root) {
Defines the function that returns the most frequent tree sums from a given root.
4 : Variable Declaration
vector<int> ans;
A vector to store the most frequent tree sums.
5 : Data Structure Initialization
map<int, int> mp;
A map to store the frequency of each tree sum.
6 : Frequency Reset
mx =0;
Initializes the maximum frequency to 0.
7 : Function Call
dfs(root, mp, ans);
Calls the dfs function to traverse the tree and compute the frequencies.
8 : Return Statement
return ans;
Returns the vector containing the most frequent tree sums.
Defines the dfs function to traverse the tree and calculate the sum for each node.
10 : Base Case
if (root ==NULL) return0;
Base case for the DFS, returns 0 if the current node is NULL.
11 : Local Variable Declaration
int res;
Declares a variable to store the current subtree sum.
12 : Leaf Node Check
if (root->left ==NULL&& root->right ==NULL) { res = root->val; }
Checks if the current node is a leaf node. If it is, the sum is just the node's value.
13 : Recursive DFS Calls
else {
If the current node is not a leaf, recursively calculate the left and right subtree sums.
14 : Recursive DFS Left
int l = dfs(root->left , mp, ans);
Recursively calls dfs for the left child and stores the result in l.
15 : Recursive DFS Right
int r = dfs(root->right, mp, ans);
Recursively calls dfs for the right child and stores the result in r.
16 : Subtree Sum Calculation
res = l + r + root->val;
Calculates the sum of the current node, left and right subtree sums.
17 : Frequency Tracking
mp[res] +=1;
Updates the frequency map with the current subtree sum.
18 : Max Frequency Check
if(mx < mp[res]) {
Checks if the current subtree sum frequency is greater than the max frequency.
19 : Update Results
ans.clear();
Clears the results vector if a new max frequency is found.
20 : Add New Max Frequency
ans.push_back(res);
Adds the current sum to the results list.
21 : Update Max Frequency
mx = mp[res];
Updates the max frequency to the current frequency.
22 : Frequency Equality Check
} elseif(mx == mp[res]) {
Checks if the current sum frequency equals the max frequency.
23 : Add Equal Frequency
ans.push_back(res);
Adds the current sum to the results list if it matches the max frequency.
24 : Return Subtree Sum
return res;
Returns the current subtree sum to the caller.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited once during the DFS.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required for the map to store the frequency of subtree sums and the recursion stack during DFS.
