Most Frequent Subtree Sum

Medium
1920.

Most Frequent Subtree Sum

Most Frequent Subtree Sum is a medium coding problem on hash table, depth-first search and trees, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findFrequentTreeSum = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    A node's subtree sum is its own value plus the subtree sums of its two children — so compute the children first.

  2. 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.

  3. 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

  1. Define sum(node): 0 for an empty subtree; otherwise node.val + sum(left) + sum(right).
  2. Before returning, increment count[s] for that node's sum s.
  3. Call sum(root), then find the largest value in count.
  4. 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)