Most Frequent Subtree Sum — Solution in Python, Java & C++
Most Frequent Subtree Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Most Frequent Subtree Sum is a medium coding problem on hash table, depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Hash Table, Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The subtree sum of a node is the sum of the values of every node in the subtree rooted at it, the node itself included.
Given the root of a binary tree, find the subtree sum (or sums) that occur most often among all its nodes. If several sums tie for the highest frequency, return all of them, sorted in ascending order.
Example 1
Input: root = [5,2,-3]
Output: [-3,2,4]
Explanation: The three subtree sums are 2, -3 and 4; each occurs once, so all of them are returned, smallest first.
Example 2
Input: root = [5,2,-5]
Output: [2]
Explanation: The sums are 2, -5 and 2 — the root's subtree also adds up to 2, so 2 occurs twice.
Example 3
Input: root = [3,-1,-1,1,null,null,1]
Output: [0,1]
Explanation: The two leaves give 1 and 1, the two -1 nodes give 0 and 0, and the whole tree gives 3. Both 0 and 1 occur twice.
Constraints
The number of nodes in the tree is in the range [1, 10^4]-10^5 <= Node.val <= 10^5
Hints for Most Frequent Subtree Sum
Hint 1
A node's subtree sum is its own value plus the subtree sums of its two children — so compute the children first.
Hint 2
One post-order walk gives every node's subtree sum; count how many times each sum appears in a hash map as you go.
Hint 3
After the walk, find the highest count and collect every sum that reaches it, then sort them.
How to solve Most Frequent Subtree Sum
Subtree sums compose bottom-up: a post-order DFS returns each subtree's sum to its parent, and recording every returned sum in a frequency map gives the counts in a single pass.
Approach
- Define
sum(node): 0 for an empty subtree; otherwisenode.val + sum(left) + sum(right). - Before returning, increment
count[s]for that node's sums. - Call
sum(root), then find the largest value incount. - Collect every sum whose count equals it and sort them ascending.
Why it works
Every node's subtree sum is computed exactly once and recorded exactly once, so the map holds the true frequency of each sum; the answer is just the keys with the maximum frequency.
Complexity
- Time —
O(n + k log k), where k is the number of tied sums — O(n log n) at worst - Space —
O(n) for the map and the recursion
Pitfalls
- Sums can be negative and repeat — use a hash map, not an array indexed by sum.
- Every node counts, the leaves included, and the root's sum is the whole tree's total.
- Return all tied sums, sorted ascending as the statement fixes.
Reference solution
Python
from typing import List, Optional
def findFrequentTreeSum(root: Optional[TreeNode]) -> List[int]:
count = {}
def total(node):
if node is None:
return 0
s = node.val + total(node.left) + total(node.right)
count[s] = count.get(s, 0) + 1
return s
total(root)
best = max(count.values())
return sorted(s for s, c in count.items() if c == best)Java
public static int[] findFrequentTreeSum(TreeNode root) {
Map<Integer, Integer> count = new HashMap<>();
total(root, count);
int best = 0;
for (int c : count.values()) best = Math.max(best, c);
List<Integer> out = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : count.entrySet()) if (e.getValue() == best) out.add(e.getKey());
Collections.sort(out);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}
static int total(TreeNode node, Map<Integer, Integer> count) {
if (node == null) return 0;
int s = node.val + total(node.left, count) + total(node.right, count);
count.merge(s, 1, Integer::sum);
return s;
}C++
int subtreeTotal(TreeNode* node, unordered_map<int, int>& count);
vector<int> findFrequentTreeSum(TreeNode* root) {
unordered_map<int, int> count;
subtreeTotal(root, count);
int best = 0;
for (auto& e : count) best = max(best, e.second);
vector<int> out;
for (auto& e : count) if (e.second == best) out.push_back(e.first);
sort(out.begin(), out.end());
return out;
}
int subtreeTotal(TreeNode* node, unordered_map<int, int>& count) {
if (!node) return 0;
int s = node->val + subtreeTotal(node->left, count) + subtreeTotal(node->right, count);
count[s]++;
return s;
}JavaScript
var findFrequentTreeSum = function(root) {
var count = new Map();
var total = function(node) {
if (node === null) return 0;
var s = node.val + total(node.left) + total(node.right);
count.set(s, (count.get(s) || 0) + 1);
return s;
};
total(root);
var best = 0;
count.forEach(function(c) { if (c > best) best = c; });
var out = [];
count.forEach(function(c, s) { if (c === best) out.push(s); });
return out.sort(function(a, b) { return a - b; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)