Most Frequent Subtree Sum

To find the most frequent subtree sum, you can follow the steps below:

  1. Use a Recursive Function to Calculate Subtree Sum: Implement a recursive function to traverse the binary tree and calculate the subtree sum for each node. The subtree sum for a node is the sum of its value and the subtree sums of its left and right children.

  2. Store the Frequency of Each Subtree Sum: Use a dictionary or a hash map to store the frequency of each subtree sum as you calculate them.

  3. Find the Most Frequent Subtree Sum: Iterate through the frequency dictionary to find the most frequent subtree sum(s). If there’s a tie, include all the values with the highest frequency.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from collections import defaultdict

class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        def subtree_sum(node):
            if not node:
                return 0
            left_sum = subtree_sum(node.left)
            right_sum = subtree_sum(node.right)
            sum_val = node.val + left_sum + right_sum
            frequency[sum_val] += 1
            return sum_val

        frequency = defaultdict(int)
        subtree_sum(root)

        max_freq = max(frequency.values())
        result = [sum_val for sum_val, freq in frequency.items() if freq == max_freq]

        return result

The function subtree_sum is a recursive function that calculates the subtree sum for a given node and updates the frequency dictionary. After calculating the subtree sums for all nodes, we find the most frequent ones and return them in a list.

The time complexity of this code is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is also (O(n)).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def counter(node, count)
    return 0 if node.nil?

    sum = node.val + counter(node.left, count) + counter(node.right, count)
    count[sum] += 1

    sum
end

# @param {TreeNode} root
# @return {Integer[]}
def find_frequent_tree_sum(root)
    hash = Hash.new(0)
    counter(root, hash)  

    most_common_frequency = 0
    result = []

    hash.each do |k, v|
       if v > most_common_frequency
           most_common_frequency = v
           result = [k]
       elsif v == most_common_frequency
           result << k
       end
    end
    result
end