Practice/Meta/Leetcode 508. Most Frequent Subtree Sum

Leetcode 508. Most Frequent Subtree Sum

CodingMust

Problem

Given the root of a binary tree, calculate the sum of all node values in each possible subtree. A subtree sum is the total of all values within that subtree, including the subtree's root node.

After computing all subtree sums across the entire tree, identify which sum value(s) occur most frequently. Return all sum values that appear with the maximum frequency.

If multiple sums tie for the highest frequency, return all of them in any order.

Requirements

1. Calculate the sum for every subtree in the tree
2. Track how many times each unique sum value occurs
3. Return all sum values that have the maximum occurrence count
4. Handle ties by returning all sums with the highest frequency
5. The order of returned sums does not matter

Constraints

• The number of nodes in the tree is in the range [1, 10000]
• Node values are in the range [-100000, 100000]
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(n) for the recursion stack and frequency map

Examples

Example 1:

` Input: root = [5, 2, -3] Tree structure: 5 /
2 -3

Output: [2, -3, 4] Explanation:

• Subtree rooted at node with value 2: sum = 2
• Subtree rooted at node with value -3: sum = -3
• Subtree rooted at node with value 5: sum = 5 + 2 + (-3) = 4 Each sum appears exactly once, so all are returned. `

Example 2:

` Input: root = [5, 2, -5] Tree structure: 5 /
2 -5

Output: [2] Explanation:

• Subtree at node 2: sum = 2
• Subtree at node -5: sum = -5
• Subtree at root: sum = 5 + 2 + (-5) = 2 The sum 2 appears twice (most frequent), while -5 appears once. `

Example 3:

Input: root = [1] Output: [1] Explanation: Only one node exists, so its value is the only subtree sum.