# Most Frequent Subtree Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-frequent-subtree-sum)
Canonical: https://scaleengineer.com/dsa/problems/most-frequent-subtree-sum
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
---
## Problem
Given the `root` of a binary tree, return the most frequent **subtree sum**. If there is a tie, return all the values with the highest frequency in any order.

The **subtree sum** of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

**Example 1:**

![](https://assets.glich.co/dsa/most-frequent-subtree-sum/image0.jpg) 

**Input:** root = [5,2,-3]
**Output:** [2,-3,4]

**Example 2:**

![](https://assets.glich.co/dsa/most-frequent-subtree-sum/image1.jpg) 

**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`

# Approaches
## Brute Force with Repeated Traversals
This approach involves iterating through every node in the tree. For each node, a separate traversal is initiated to calculate the sum of its subtree. The frequencies of these sums are stored in a hash map. This method is straightforward but inefficient due to repeated calculations.
**Time:** O(N^2), where N is the number of nodes. The initial traversal to get all nodes is O(N). Then, for each of the N nodes, we perform a subtree sum calculation which can take up to O(N) time in the worst case (a skewed tree). This leads to a total time complexity dominated by N * O(N) = O(N^2). · **Space:** O(N), where N is the number of nodes. We need O(N) space to store the list of all nodes and up to O(N) for the hash map. The recursion stack for the sum calculation can also go up to O(N) in the worst case of a skewed tree.
**Pros:** Conceptually straightforward and easy to break down into smaller, distinct problems.
**Cons:** Highly inefficient due to redundant computations. The value of a node is included in the sum calculation for itself and for every one of its ancestors, leading to repeated work.
### Explanation
The core idea of this brute-force method is to separate the problem into two main parts: identifying all subtrees and then calculating the sum for each one. First, we perform a full traversal of the tree to get a list of all nodes. Each node in this list is the root of a subtree. Then, we iterate through this list. For each node, we perform a second, independent traversal starting from that node to compute its subtree sum. We use a hash map to keep track of how many times each sum occurs. After calculating all subtree sums, we find the highest frequency and collect all sums that have this frequency.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        List<TreeNode> nodes = new ArrayList<>();
        getAllNodes(root, nodes);

        Map<Integer, Integer> freqMap = new HashMap<>();
        int maxFreq = 0;

        for (TreeNode node : nodes) {
            int sum = calculateSubtreeSum(node);
            int currentFreq = freqMap.getOrDefault(sum, 0) + 1;
            freqMap.put(sum, currentFreq);
            maxFreq = Math.max(maxFreq, currentFreq);
        }

        List<Integer> resultList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            if (entry.getValue() == maxFreq) {
                resultList.add(entry.getKey());
            }
        }

        return resultList.stream().mapToInt(i -> i).toArray();
    }

    private void getAllNodes(TreeNode node, List<TreeNode> nodes) {
        if (node == null) {
            return;
        }
        nodes.add(node);
        getAllNodes(node.left, nodes);
        getAllNodes(node.right, nodes);
    }

    private int calculateSubtreeSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);
    }
}
```
### Algorithm
- 1. Define a helper function `getAllNodes` to traverse the tree (e.g., using pre-order traversal) and store all nodes in a list.
- 2. Define another helper function `calculateSubtreeSum` that takes a node and recursively calculates the sum of all nodes in its subtree.
- 3. In the main function, first call `getAllNodes` to populate a list of all tree nodes.
- 4. Initialize a `HashMap<Integer, Integer>` to store the frequency of each subtree sum and an integer `maxFreq` to track the maximum frequency found.
- 5. Iterate through each node in the list of all nodes.
- 6. For each node, call `calculateSubtreeSum` to get its subtree sum.
- 7. Update the frequency of this sum in the hash map and update `maxFreq` if necessary.
- 8. After iterating through all nodes, create a result list.
- 9. Iterate through the hash map and add any sum whose frequency equals `maxFreq` to the result list.
- 10. Convert the result list to an integer array and return it.

## Optimized Single Pass using Post-order Traversal
A more efficient approach is to use a single post-order traversal. This traversal order (Left, Right, Root) naturally allows us to compute the sum of a subtree right after we have computed the sums of its children's subtrees. We can calculate each subtree sum and update its frequency in the same pass, avoiding redundant calculations.
**Time:** O(N), where N is the number of nodes. We visit each node exactly once during the post-order traversal. Operations inside the recursive function (map access, addition) are O(1) on average. The final step of collecting results from the map takes at most O(N) time. · **Space:** O(N), where N is the number of nodes. The space is used by the hash map, which can store up to N distinct sums, and by the recursion stack. The depth of the recursion stack is equal to the height of the tree, H, which is O(N) in the worst case (a skewed tree) and O(log N) in the best case (a balanced tree).
**Pros:** Optimal time complexity as it processes each node only once.; Combines sum calculation and frequency counting into a single, elegant traversal.
**Cons:** Requires extra space for the hash map and the recursion stack, which can be O(N) in the worst case for a skewed tree.
### Explanation
This optimized approach leverages the properties of post-order traversal. The sum of a subtree at a given node is the node's own value plus the sums of its left and right subtrees. By processing children before the parent, a post-order traversal ensures that when we visit a node, the sums for its left and right subtrees have already been computed. 

We can define a recursive function that traverses the tree in a post-order fashion. This function will return the sum of the subtree rooted at the node it's given. Inside this function, after computing the current node's subtree sum, we immediately update a frequency map. We also maintain a variable to keep track of the maximum frequency seen so far. This way, we compute all subtree sums and their frequencies in a single pass over the tree.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> freqMap;
    private int maxFreq;

    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        freqMap = new HashMap<>();
        maxFreq = 0;

        postOrderSum(root);

        List<Integer> resultList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            if (entry.getValue() == maxFreq) {
                resultList.add(entry.getKey());
            }
        }

        return resultList.stream().mapToInt(i -> i).toArray();
    }

    private int postOrderSum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = postOrderSum(node.left);
        int rightSum = postOrderSum(node.right);

        int currentSum = node.val + leftSum + rightSum;
        
        int currentFreq = freqMap.getOrDefault(currentSum, 0) + 1;
        freqMap.put(currentSum, currentFreq);
        
        maxFreq = Math.max(maxFreq, currentFreq);

        return currentSum;
    }
}
```
### Algorithm
- 1. Initialize a `HashMap<Integer, Integer>` to store sum frequencies and a global or member variable `maxFreq` to track the maximum frequency.
- 2. Define a recursive helper function that performs a post-order traversal, let's call it `postOrderSum(node)`.
- 3. **Base Case:** If the current `node` is null, return 0.
- 4. **Recursive Step:** Recursively call `postOrderSum` for the left and right children to get their respective subtree sums, `leftSum` and `rightSum`.
- 5. **Process Node:** Calculate the sum of the subtree rooted at the current node: `currentSum = node.val + leftSum + rightSum`.
- 6. Update the frequency of `currentSum` in the hash map.
- 7. Update `maxFreq` if the new frequency of `currentSum` is greater than the current `maxFreq`.
- 8. Return `currentSum` to be used by its parent's calculation.
- 9. Start the process by calling `postOrderSum(root)`.
- 10. After the traversal is complete, iterate through the hash map's keys. Collect all sums whose frequency equals `maxFreq`.
- 11. Return the collected list of sums as an array.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Integer , Integer > counter ; private int mx ; public int [] findFrequentTreeSum ( TreeNode root ) { counter = new HashMap <>(); mx = Integer . MIN_VALUE ; dfs ( root ); List < Integer > res = new ArrayList <>(); for ( Map . Entry < Integer , Integer > entry : counter . entrySet ()) { if ( entry . getValue () == mx ) { res . add ( entry . getKey ()); } } int [] ans = new int [ res . size ()]; for ( int i = 0 ; i < res . size (); ++ i ) { ans [ i ] = res . get ( i ); } return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int s = root . val + dfs ( root . left ) + dfs ( root . right ); counter . put ( s , counter . getOrDefault ( s , 0 ) + 1 ); mx = Math . max ( mx , counter . get ( s )); return s ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map < int , int > counter ; int mx = 0 ; vector < int > findFrequentTreeSum ( TreeNode * root ) { mx = INT_MIN ; dfs ( root ); vector < int > ans ; for ( auto & entry : counter ) if ( entry . second == mx ) ans . push_back ( entry . first ); return ans ; } int dfs ( TreeNode * root ) { if ( ! root ) return 0 ; int s = root -> val + dfs ( root -> left ) + dfs ( root -> right ); ++ counter [ s ]; mx = max ( mx , counter [ s ]); return s ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def findFrequentTreeSum ( self , root : TreeNode ) -> List [ int ]: def dfs ( root ): if root is None : return 0 left , right = dfs ( root . left ), dfs ( root . right ) s = root . val + left + right counter [ s ] += 1 return s counter = Counter () dfs ( root ) mx = max ( counter . values ()) return [ k for k , v in counter . items () if v == mx ]
```