Most Frequent Subtree Sum
Medium · Graphs · Explanation and code example
Postorder Sums and a Frequency Map
How it works
A subtree sum is its root value plus the sums of its two child subtrees. Compute sums postorder and count each result in a frequency map. Return every sum whose frequency equals the maximum, since ties are allowed.
Steps
- Recursively compute the left and right sums.
- Count their sum with the current node value.
- Find the maximum frequency and return all matching sums.
Complexity
- Time: O(n) expected with hashing.
- Space: O(n) map plus O(h) recursion stack.
Things to watch for
- Negative subtree sums are valid.
- Return all tied modes.
- An empty root returns an empty list.
Python code example
import collections
class Solution:
def findFrequentTreeSum(self, root: TreeNode | None) -> list[int]:
if not root:
return []
count = collections.Counter()
def dfs(root: TreeNode | None) -> int:
if not root:
return 0
summ = root.val + dfs(root.left) + dfs(root.right)
count[summ] += 1
return summ
dfs(root)
maxFreq = max(count.values())
return [summ for summ in count if count[summ] == maxFreq]
C++ code example
class Solution {
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> ans;
unordered_map<int, int> count;
int maxCount = 0;
sumDownFrom(root, count);
for (const auto& [_, freq] : count)
maxCount = max(maxCount, freq);
for (const auto& [sum, freq] : count)
if (freq == maxCount)
ans.push_back(sum);
return ans;
}
private:
int sumDownFrom(TreeNode* root, unordered_map<int, int>& count) {
if (root == nullptr)
return 0;
const int sum = root->val + sumDownFrom(root->left, count) +
sumDownFrom(root->right, count);
++count[sum];
return sum;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.