508. Most Frequent Subtree Sum
Model: qwen3.5:9b
Topics: Hash Table,Tree
FAANG asked: 1
Acceptance rate: 59.2%
Problem Breakdown
We are given the root of a binary tree where each node contains an integer value (positive or negative). We need to calculate the “subtree sum” for every node in the tree. The subtree sum is defined as the sum of all values within that specific node’s subtree, including itself and its descendants recursively.
Inputs:
root: A pointer to a binary tree (TreeNode). Each node has.val,.left, and.right.
Outputs:
- A list of integers representing the most frequent subtree sums found across all nodes in the tree. If multiple distinct sum values share the highest frequency, return all of them (order does not matter). Return an empty list if the input is null/empty.
Constraints & Edge Cases:
- Empty Tree:
rootcould beNone. The code must handle this gracefully without crashing or returning incorrect data structures. - Negative Values: Node values and resulting subtree sums can be negative (e.g., Example 1 includes
-3). Hash maps work fine with negatives as keys, but we need to ensure logic doesn’t assume positive-only arithmetic properties. - Ties: The problem explicitly allows for ties in frequency; the output list must contain all values that tie for the maximum count.
- Overflow Note: While sums are guaranteed to fit within a 32-bit signed integer, Python handles arbitrary precision integers automatically, so we don’t need explicit overflow checks (unlike C++ or Java).
Intuition
A brute-force approach would be: For every node in the tree, traverse its entire subtree to calculate the sum. Then store these sums and count frequencies using a hash map. Finally, identify the maximum frequency.
Why Brute Force Fails: Calculating the subtree sum for one node takes time proportional to the size of that subtree (O(N) worst case). Doing this for every node results in O(N^2) total time complexity. Given typical tree constraints where N can be up to 10^4 or higher, an O(N^2) solution will likely Time Out (TLE).
Key Insight:
We don’t need to recalculate sums from scratch for each subtree. If we process the tree using a Post-Order Traversal, when we visit any node u, its left and right children have already been processed in recursive calls. This means their subtree sums are available immediately. We can compute the current node’s sum as:
current_sum = node.val + dfs(left) + dfs(right)
This allows us to calculate every single subtree sum exactly once during a standard DFS traversal, resulting in O(N). While calculating these sums, we simultaneously update a frequency map (Hash Map/Counter). After traversing the entire tree, we simply scan this map to find which keys have the highest value. This reduces complexity significantly while maintaining correctness.
Approach
- Initialize State: Create a hash map (
collections.Counterordict) to store frequencies of subtree sums encountered so far. Also initialize a variable to track the maximum frequency found (optional, but scanning at end is cleaner). - Define DFS Helper: A recursive function that takes a node and returns its subtree sum.
- Base Case: If the current
nodeisNone, return0. This acts as an identity element for addition so parent nodes can ignore missing children’s contribution (sum of empty tree = 0). - Recursive Step: Recursively call DFS on left and right children. Add their returned sums to the current node’s value (
node.val).
- Base Case: If the current
- Update Frequency Map: For every computed
current_sum, increment its count in our frequency map. - Post-Traversal Analysis: Once the initial traversal completes, iterate through the values of the frequency map to find the maximum frequency.
- Construct Result: Collect all keys (sums) that match this maximum frequency into a list and return it.
Complexity Analysis
- Time Complexity: O(N) where N is the number of nodes in the tree. We visit each node exactly once during DFS to compute sums, perform constant-time map updates per node, and scan the map (at most N unique keys) at the end. Map operations are average O(1).
- Space Complexity: O(H + K) where H is the height of the tree (recursion stack depth in worst case skewed tree = O(N)) and K is the number of distinct subtree sums stored in our hash map (K <= N). In a balanced binary tree, space for recursion is O(log N), but we must account for the map storage.
Solution
from collections import Counter
from typing import List, Optional
# Definition for a Node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mostFrequentSubtreeSum(root: 'Optional[TreeNode]') -> List[int]:
# Map to store frequency of each subtree sum encountered.
counter = Counter()
def dfs(node) -> int:
if not node:
return 0
# Get sums from left and right subtrees (already computed recursively).
left_sum = dfs(node.left)
right_sum = dfs(node.right)
# Calculate current subtree sum including the node itself.
current_subtree_sum = node.val + left_sum + right_sum
# Update frequency map for this specific sum value.
counter[current_subtree_sum] += 1
return current_subtree_sum
if not root:
return []
dfs(root)
# Find the highest frequency in our collected sums.
max_freq = max(counter.values())
# Return all sum values that appear with this maximum frequency.
return [sum_val for sum_val, freq in counter.items() if freq == max_freq]
# Example usage logic (not part of function signature):
# root = TreeNode(5)
# left_child = TreeNode(2)
# right_child = TreeNode(-3)
# ... etc
Edge Cases Handled
- Empty Tree (
rootisNone): The code checksif not root:at the start and returns an empty list immediately. Inside DFS, returning 0 for null nodes ensures correct summation logic without crashing on missing children. - Single Node: If only one node exists, it calls itself with left/right as None (returning 0), computes sum =
node.val, updates counter once, and returns that value in the list if no other sums exist. - All Sums Unique: The frequency map will have all counts equal to 1.
max_freqbecomes 1, and the function correctly returns a list of all unique subtree sum values found (as per Example 1). - Tie in Frequencies: If multiple sums appear with count X where X is greater than any other frequency, the final filtering step
[sum_val for ... if freq == max_freq]captures all such keys.