Most Frequent Subtree Sum

Problem Statement

We are given the root of a binary tree and are tasked to find the most frequent subtree sum. The subtree sum for a node is defined as the overall sum of all nodes within the subtree, including the node itself. The goal is to calculate these sums for all subtrees in the binary tree, and identify which sum(s) appear most frequently. If more than one sum appears the same maximum number of times, all those sums should be returned in any order.

Examples

Example 1

Input:

root = [5,2,-3]

Output:

[2,-3,4]

Example 2

Input:

root = [5,2,-5]

Output:

[2]

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

Approach and Intuition

1. The first step involves calculating the subtree sum for every node in the binary tree. We can achieve this through a recursive post-order traversal (left-right-root). In this traversal, the sum of a node is computed as the sum of its value and the sums of its left and right children.
2. As we compute these sums, we can use a dictionary (or hash map) to keep a count of how many times each sum occurs.
3. Once all sums have been computed and their frequencies tallied, the next task is identifying the sums with the maximum frequency. This requires examining the values in our frequency dictionary to find the highest frequency.
4. Collect and return all sums that match this maximum frequency. These are the most frequent subtree sums. Depending on the values and structure of the binary tree, this could be one sum or multiple sums.

Example Walk-through:

• For root = [5,2,-3]:

  • The sum of the subtree rooted at node 2 is just 2 (no children).
  • The sum of the subtree rooted at node -3 is -3 (no children).
  • The sum of the subtree rooted at node 5 (including its children) is 5 + 2 + (-3) = 4.
  • Here, the sums 2, -3, and 4 each appear once, thus they all are the most frequent sums. So the output is [2, -3, 4].

• For root = [5,2,-5]:

  • The subtree rooted at node 2 sums to 2.
  • The subtree rooted at node -5 sums to -5.
  • The sum for the subtree of the root node 5 becomes 5 + 2 + (-5) = 2.
  • Here, the sum 2 appears twice (once at node 2 and once for the entire tree rooted at node 5), making it the most frequent subtree sum. Thus, the output is [2].

Solutions

class Solution {
public:
    int calculateSum(TreeNode* node, unordered_map<int, int>& sumCounts, int& highestFrequency) {
        if (!node) return 0;
    
        int leftSum = calculateSum(node->left, sumCounts, highestFrequency);
        int rightSum = calculateSum(node->right, sumCounts, highestFrequency);
    
        int totalSum = node->val + leftSum + rightSum;
    
        sumCounts[totalSum]++;
        highestFrequency = max(highestFrequency, sumCounts[totalSum]);
        return totalSum;
    }
        
    vector<int> mostFrequentSum(TreeNode* root) {
        unordered_map<int, int> sumCounts;
        int highestFrequency = 0;
    
        calculateSum(root, sumCounts, highestFrequency);
    
        vector<int> result;
        for (auto& pair : sumCounts) {
            if (pair.second == highestFrequency) {
                result.push_back(pair.first);
            }
        }
    
        return result;
    }
};