Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import defaultdict

class Solution:
    def findFrequentTreeSum(self, root: TreeNode):
        if not root:
            return []
        count = defaultdict(int)
        def subtree_sum(node):
            if not node:
                return 0
            s = node.val + subtree_sum(node.left) + subtree_sum(node.right)
            count[s] += 1
            return s
        subtree_sum(root)
        max_freq = max(count.values())
        return [s for s in count if count[s] == max_freq]
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    unordered_map<int, int> count;
    int maxFreq = 0;
    
    int subtreeSum(TreeNode* node) {
        if (!node) return 0;
        int s = node->val + subtreeSum(node->left) + subtreeSum(node->right);
        count[s]++;
        if (count[s] > maxFreq) maxFreq = count[s];
        return s;
    }
    
    vector<int> findFrequentTreeSum(TreeNode* root) {
        if (!root) return {};
        subtreeSum(root);
        vector<int> res;
        for (auto& p : count) {
            if (p.second == maxFreq)
                res.push_back(p.first);
        }
        return res;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

class Solution {
    Map<Integer, Integer> count = new HashMap<>();
    int maxFreq = 0;
    
    private int subtreeSum(TreeNode node) {
        if (node == null) return 0;
        int s = node.val + subtreeSum(node.left) + subtreeSum(node.right);
        count.put(s, count.getOrDefault(s, 0) + 1);
        maxFreq = Math.max(maxFreq, count.get(s));
        return s;
    }
    
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) return new int[0];
        subtreeSum(root);
        List<Integer> res = new ArrayList<>();
        for (int s : count.keySet()) {
            if (count.get(s) == maxFreq)
                res.add(s);
        }
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); ++i)
            result[i] = res.get(i);
        return result;
    }
}
      

/**
 * Definition for a binary tree node.
 * 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) {
    if (!root) return [];
    const count = {};
    let maxFreq = 0;
    
    function subtreeSum(node) {
        if (!node) return 0;
        const s = node.val + subtreeSum(node.left) + subtreeSum(node.right);
        count[s] = (count[s] || 0) + 1;
        if (count[s] > maxFreq) maxFreq = count[s];
        return s;
    }
    
    subtreeSum(root);
    const res = [];
    for (const key in count) {
        if (count[key] === maxFreq) {
            res.push(Number(key));
        }
    }
    return res;
};
      

Problem Description

Given the root of a binary tree, find all the subtree sums that occur most frequently. The subtree sum of a node is defined as the sum of all the node values in its subtree, including itself. Return all the values of the most frequent subtree sum(s) in any order.

• Each node in the tree contains an integer value.
• There may be multiple subtree sums with the same highest frequency; you must return all of them.
• If the tree is empty (root is null), return an empty array.
• The input is a binary tree; you are given the root node.

Thought Process

To solve this problem, we need to find the sum of all nodes for every subtree in the binary tree, and then determine which sums occur most frequently. At first glance, you might think about traversing each subtree individually and calculating its sum, but this would be highly inefficient because of overlapping subtrees.

Instead, we notice that we can use a post-order traversal (left, right, root) to compute the sum for each subtree in a single pass. Every time we compute a sum, we record it in a hash map to keep track of how many times each sum has occurred. At the end, we simply look for the sums with the highest frequency in our map.

This approach avoids redundant calculations and leverages the recursive nature of trees, making it both intuitive and efficient.

Solution Approach

• Step 1: Post-order Traversal
  • We use a post-order traversal because we need to know the sum of the left and right subtrees before we can compute the sum at the current node.
• Step 2: Compute Subtree Sums
  • For each node, compute the sum as node.val + left subtree sum + right subtree sum.
• Step 3: Track Frequencies
  • Use a hash map (dictionary) to record how many times each subtree sum occurs.
• Step 4: Find Most Frequent Sums
  • After traversal, determine the maximum frequency from the hash map.
  • Collect all subtree sums that have this maximum frequency.
• Step 5: Handle Edge Cases
  • If the tree is empty, return an empty list.

We use a hash map because it allows us to update and look up frequencies in constant time, making the algorithm efficient.

Example Walkthrough

Let's consider the following binary tree:

        5
       / \
      2  -3
  

• Start at the left child (2): Its sum is 2.
• Right child (-3): Its sum is -3.
• Root (5): Sum is 5 + 2 + (-3) = 4.

The subtree sums we have are: 2, -3, and 4. Each occurs once, so all are the most frequent. The output is [2, -3, 4] (order doesn't matter).

Time and Space Complexity

• Brute-force Approach:
  • For each node, traverse its entire subtree to compute the sum. This leads to O(N^2) time in the worst case (where N is the number of nodes).
• Optimized Approach:
  • We traverse each node exactly once, and each operation (sum calculation, hash map update) is O(1).
  • Time Complexity: O(N), where N is the number of nodes.
  • Space Complexity: O(N), due to the hash map storing up to N unique subtree sums, and the recursion stack.

Summary

The "Most Frequent Subtree Sum" problem is a classic example of using tree traversal and hash maps to efficiently solve a problem that might otherwise require redundant calculations. By leveraging post-order traversal, we compute each subtree sum in a single pass, and a hash map allows us to track frequencies efficiently. The result is an elegant and optimal O(N) solution that highlights the power of recursive thinking and hash-based counting.