Most Frequent Subtree Sum

Most Frequent Subtree Sum

What is this problem about?

The Most Frequent Subtree Sum problem gives you a binary tree where each node has an integer value. A subtree sum is the sum of all values in a subtree rooted at some node. Find the most frequently occurring subtree sum(s). If there are ties, return all of them. This Most Frequent Subtree Sum coding problem uses DFS with a frequency map.

Why is this asked in interviews?

Amazon and Bloomberg ask this because it combines DFS tree traversal with frequency counting — two fundamental skills that appear throughout data structure interviews. It tests the ability to pass computed values up a recursive tree (post-order DFS) and efficiently track result frequencies. The hash table, DFS, binary tree, and tree interview pattern is the core.

Algorithmic pattern used

Post-order DFS + frequency map. For each node, recursively compute the left subtree sum and right subtree sum. The subtree sum at the current node = node.val + left_sum + right_sum. Update a global frequency map with this sum. After the DFS completes, find and return all sums with the maximum frequency.

Example explanation

Tree:

    5
   / \
  2   -3

• Subtree at node 2: sum = 2. freq = {2:1}.
• Subtree at node -3: sum = -3. freq = {2:1, -3:1}.
• Subtree at root 5: sum = 5+2+(-3) = 4. freq = {2:1, -3:1, 4:1}. All sums appear once. Return all: [2, -3, 4].

Common mistakes candidates make

• Using pre-order instead of post-order DFS (need children's sums before computing parent).
• Returning only the first maximum-frequency sum (must return all ties).
• Not initializing the frequency map before the recursive calls.
• Confusing subtree sum with path sum or node value.

Interview preparation tip

Post-order DFS problems compute values bottom-up: process children first, then use their results for the parent. This pattern appears in subtree height, subtree size, path sum, and LCA problems. Practice writing the post-order DFS template: recurse left, recurse right, then compute result for current node. Frequency map tracking alongside recursion is a common pattern — returning the max-frequency keys is a standard post-processing step.