Most Frequent Subtree Sum

medium tree dfs hash map

Problem

Given the root of a binary tree, return the most frequent subtree sum — the sum of all node values rooted at a given node, including the node itself. If multiple sums tie, return all of them.

Inputtree = [5, 2, -3]

Output[2, -3, 4]

Subtree sums: leaf 2 → 2, leaf −3 → −3, root → 4. All three appear once, so all win.

tree (level-order, "null" for empty)

from collections import Counter

def find_frequent_tree_sum(root):
    counts = Counter()

    def dfs(node):
        if not node:
            return 0
        s = node.val + dfs(node.left) + dfs(node.right)
        counts[s] += 1
        return s

    dfs(root)
    if not counts:
        return []
    top = max(counts.values())
    return [s for s, c in counts.items() if c == top]

function findFrequentTreeSum(root) {
  const counts = new Map();
  function dfs(node) {
    if (!node) return 0;
    const s = node.val + dfs(node.left) + dfs(node.right);
    counts.set(s, (counts.get(s) || 0) + 1);
    return s;
  }
  dfs(root);
  if (!counts.size) return [];
  const top = Math.max(...counts.values());
  return [...counts].filter(([, c]) => c === top).map(([s]) => s);
}

class Solution {
    Map<Integer, Integer> counts = new HashMap<>();
    int top = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        List<Integer> ans = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
            if (e.getValue() == top) ans.add(e.getKey());
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }

    private int dfs(TreeNode n) {
        if (n == null) return 0;
        int s = n.val + dfs(n.left) + dfs(n.right);
        counts.merge(s, 1, Integer::sum);
        top = Math.max(top, counts.get(s));
        return s;
    }
}

vector<int> findFrequentTreeSum(TreeNode* root) {
    unordered_map<int, int> counts;
    int top = 0;
    function<int(TreeNode*)> dfs = [&](TreeNode* n) -> int {
        if (!n) return 0;
        int s = n->val + dfs(n->left) + dfs(n->right);
        top = max(top, ++counts[s]);
        return s;
    };
    dfs(root);
    vector<int> ans;
    for (auto& [k, v] : counts) if (v == top) ans.push_back(k);
    return ans;
}

Explanation

A subtree sum at a node is the total of that node plus everything below it. To get all of them efficiently, we use a post-order DFS — we compute both children's sums first, then add the current node's value on top.

The trick that makes this clean is that a node's sum is simply node.val + dfs(node.left) + dfs(node.right). Each recursive call returns its own subtree sum, so the parent just adds them together without re-walking anything.

Every time we compute a subtree sum, we tally it in a hash map called counts that maps each sum to how many times it has appeared. After the whole tree is processed, we find the highest frequency and return every sum tied for it.

Example: tree [5, 2, -3]. The leaf 2 gives sum 2, the leaf -3 gives -3, and the root gives 5 + 2 + (-3) = 4. Each appears once, so the top frequency is 1 and the answer is [2, -3, 4].

Since each node contributes exactly one sum to the map and we scan the map once at the end, the whole thing is one pass plus a quick tally.

Time: O(n) Space: O(n)