LeetCode Solutions Blog

Most Frequent Subtree Sum

Number: 508

Difficulty: Medium

Paid? No

Companies: Amazon, Uber

Problem Description

Given the root of a binary tree, we need to compute the sum of each subtree (where a subtree includes the node itself and all of its descendants). Then, identify the subtree sum(s) that occur most frequently. If there is a tie, return all the sums with the highest frequency in any order.

Key Insights

Use depth-first search (DFS) recursion to compute the subtree sum for each node.
Use a hash table (or dictionary/map) to keep track of the frequency of each subtree sum.
After processing all nodes, determine the maximum frequency and select all sums matching that frequency.
Handle potential negative values and ties properly.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since each node is visited once. Space Complexity: O(n) in the worst case due to the dictionary storing subtree sums and the recursion stack.

Solution

The approach is to perform a post-order DFS traversal to compute the subtree sum at every node. For each node, calculate the sum of its left subtree, the sum of its right subtree, and add the node's own value. Update the frequency dictionary with this computed subtree sum. After the traversal, determine the maximum frequency from the dictionary and extract all the subtree sums that have this frequency. The main data structures used are a hash table (or dictionary) for storing the frequencies and a recursive function to compute subtree sums.

Code Solutions

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

class Solution:
    def findFrequentTreeSum(self, root: TreeNode):
        # Dictionary to keep count of subtree sums
        frequency = {}
        
        # Function to perform DFS and compute subtree sums
        def dfs(node):
            if not node:
                return 0
            # Compute left subtree sum
            left_sum = dfs(node.left)
            # Compute right subtree sum
            right_sum = dfs(node.right)
            # Current subtree sum is the sum of the current node and its children
            subtree_sum = node.val + left_sum + right_sum
            # Update the frequency of the current subtree sum
            frequency[subtree_sum] = frequency.get(subtree_sum, 0) + 1
            return subtree_sum
        
        dfs(root)
        
        # Get the max frequency from the dictionary
        if not frequency:
            return []
        max_freq = max(frequency.values())
        # Return all subtree sums that have the max frequency
        return [s for s, count in frequency.items() if count == max_freq]

# Example usage:
# Construct a sample tree: [5,2,-3]
#      5
#     / \
#    2  -3
# sol = Solution()
# root = TreeNode(5, TreeNode(2), TreeNode(-3))
# print(sol.findFrequentTreeSum(root))