{x}
blog image

Most Frequent Subtree Sum

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

 

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]

Example 2:

Input: root = [5,2,-5]
Output: [2]

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105

508. Most Frequent Subtree Sum

Problem Description

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order. The subtree sum of a node is the sum of all node values in the subtree rooted at that node.

Solution Explanation

The optimal solution involves a depth-first search (DFS) combined with a hash map (or dictionary). We'll traverse the tree, calculating the subtree sum at each node. We'll use a hash map to keep track of the frequency of each subtree sum encountered.

Algorithm:

  1. Depth-First Search (DFS): A recursive DFS function will traverse the tree. For each node, it recursively calculates the subtree sums of its left and right subtrees. Then, it adds the node's value to these subtree sums to get the total subtree sum for the current node.

  2. Hash Map (Frequency Counting): A hash map (like HashMap in Rust, unordered_map in C++, dict in Python, or Map in Java/TypeScript) stores the frequency of each subtree sum encountered. For each calculated subtree sum, we increment its count in the hash map.

  3. Finding the Most Frequent Sum(s): After the DFS is complete, we iterate through the hash map to find the sum(s) with the highest frequency. We return a list of these sums.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once during the DFS traversal.
  • Space Complexity: O(N) in the worst case. This is because the hash map might store up to N different subtree sums (e.g., a skewed tree where each subtree sum is unique). The recursive call stack during DFS also takes up space, but it's at most O(H), where H is the height of the tree, which is bounded by N.

Code Implementation in Multiple Languages

Python

from collections import Counter
 
# 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
 
class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        count = Counter()
 
        def dfs(node):
            if not node:
                return 0
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            subtree_sum = left_sum + right_sum + node.val
            count[subtree_sum] += 1
            return subtree_sum
 
        dfs(root)
        max_freq = max(count.values())
        return [s for s, freq in count.items() if freq == max_freq]

Java

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    Map<Integer, Integer> count = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        int maxFreq = 0;
        for (int freq : count.values()) {
            maxFreq = Math.max(maxFreq, freq);
        }
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if (entry.getValue() == maxFreq) {
                result.add(entry.getKey());
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
 
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = dfs(node.left);
        int rightSum = dfs(node.right);
        int subtreeSum = leftSum + rightSum + node.val;
        count.put(subtreeSum, count.getOrDefault(subtreeSum, 0) + 1);
        return subtreeSum;
    }
}

C++

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution {
public:
    std::map<int, int> count;
    std::vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        int maxFreq = 0;
        for (auto const& [key, val] : count) {
            maxFreq = std::max(maxFreq, val);
        }
        std::vector<int> result;
        for (auto const& [key, val] : count) {
            if (val == maxFreq) {
                result.push_back(key);
            }
        }
        return result;
    }
 
    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int leftSum = dfs(node->left);
        int rightSum = dfs(node->right);
        int subtreeSum = leftSum + rightSum + node->val;
        count[subtreeSum]++;
        return subtreeSum;
    }
};

(Other languages like Javascript, Go, Rust would follow a similar structure, adapting the data structures and syntax accordingly.)

This detailed explanation, along with the provided code examples in multiple languages, should clarify the solution to the problem. Remember to adapt the code to your specific environment and coding style.