# LeetCode 508: Most Frequent Subtree Sum

## Problem Restatement

We are given the root of a binary tree.

For every node, define its subtree sum as the sum of all values in the subtree rooted at that node. This includes the node itself and all of its descendants.

We need to return the subtree sum value or values that appear most frequently.

If several subtree sums have the same highest frequency, return all of them in any order. The official problem asks for the most frequent subtree sum, with ties returned together.

## Input and Output

| Item | Meaning |
|---|---|
| Input | The root of a binary tree |
| Output | A list of integer subtree sums |
| Goal | Return every subtree sum with maximum frequency |
| Order | Any order is accepted |

Function shape:

```python
class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        ...
```

## Examples

Example 1:

```text
    5
   / \
  2  -3
```

The subtree sums are:

| Node | Subtree sum |
|---:|---:|
| `2` | `2` |
| `-3` | `-3` |
| `5` | `5 + 2 + (-3) = 4` |

Each sum appears once.

So the answer can be:

```python
[2, -3, 4]
```

Example 2:

```text
    5
   / \
  2  -5
```

The subtree sums are:

| Node | Subtree sum |
|---:|---:|
| `2` | `2` |
| `-5` | `-5` |
| `5` | `5 + 2 + (-5) = 2` |

The sum `2` appears twice.

So the answer is:

```python
[2]
```

## First Thought: Compute Every Subtree Sum

We need the subtree sum for every node.

For a node, the formula is:

```text
subtree_sum = node.val + left_subtree_sum + right_subtree_sum
```

This means we need the children sums before the parent sum.

So the natural traversal is postorder DFS:

1. Visit the left subtree.
2. Visit the right subtree.
3. Process the current node.

## Key Insight

DFS can return information upward.

For each recursive call:

```python
dfs(node)
```

return the sum of the subtree rooted at `node`.

Then the parent can use it directly.

At the same time, we count how often each subtree sum appears:

```python
count[subtree_sum] += 1
```

After visiting the whole tree, we scan the frequency map and return every sum whose frequency equals the maximum frequency.

## Algorithm

Create a frequency map:

```python
count = defaultdict(int)
```

Define a DFS function.

For each node:

1. If the node is `None`, return `0`.
2. Recursively compute the left subtree sum.
3. Recursively compute the right subtree sum.
4. Compute the current subtree sum.
5. Increment its frequency.
6. Return the current subtree sum.

After DFS finishes:

1. Find the maximum frequency.
2. Return all sums with that frequency.

## Correctness

For a null child, the subtree sum is `0`, which contributes nothing to its parent.

For a real node, the algorithm first computes the exact sum of the left subtree and the exact sum of the right subtree by recursion.

It then adds those two sums to the current node value. Therefore, the computed value is exactly the subtree sum rooted at that node.

The algorithm records this sum once for every node. Since every node is visited exactly once, the frequency map stores the exact number of times each subtree sum occurs.

Finally, the algorithm returns all sums whose frequency equals the largest frequency in the map. These are exactly the most frequent subtree sums.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(n)` | The frequency map can store up to `n` distinct sums |

The recursion stack uses `O(h)` space, where `h` is the tree height. In the worst case, `h = n`.

## Implementation

```python
from typing import Optional, List
from collections import defaultdict

# 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: Optional[TreeNode]) -> List[int]:
        count = defaultdict(int)

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            left_sum = dfs(node.left)
            right_sum = dfs(node.right)

            subtree_sum = node.val + left_sum + right_sum
            count[subtree_sum] += 1

            return subtree_sum

        dfs(root)

        max_freq = max(count.values())

        return [
            subtree_sum
            for subtree_sum, freq in count.items()
            if freq == max_freq
        ]
```

## Code Explanation

The frequency map stores how often each subtree sum appears:

```python
count = defaultdict(int)
```

The DFS returns an integer:

```python
def dfs(node: Optional[TreeNode]) -> int:
```

For an empty child, the sum is `0`:

```python
if not node:
    return 0
```

Compute child sums first:

```python
left_sum = dfs(node.left)
right_sum = dfs(node.right)
```

Then compute the current subtree sum:

```python
subtree_sum = node.val + left_sum + right_sum
```

Record it:

```python
count[subtree_sum] += 1
```

Return it to the parent:

```python
return subtree_sum
```

After traversal, find the highest frequency:

```python
max_freq = max(count.values())
```

Then return every subtree sum with that frequency.

## Testing

```python
def sorted_result(root):
    return sorted(Solution().findFrequentTreeSum(root))

def test_find_frequent_tree_sum():
    # Tree:
    #     5
    #    / \
    #   2  -3
    root = TreeNode(5)
    root.left = TreeNode(2)
    root.right = TreeNode(-3)
    assert sorted_result(root) == [-3, 2, 4]

    # Tree:
    #     5
    #    / \
    #   2  -5
    root = TreeNode(5)
    root.left = TreeNode(2)
    root.right = TreeNode(-5)
    assert sorted_result(root) == [2]

    # Single node
    root = TreeNode(7)
    assert sorted_result(root) == [7]

    # Tree:
    #      0
    #     / \
    #    0   0
    root = TreeNode(0)
    root.left = TreeNode(0)
    root.right = TreeNode(0)
    assert sorted_result(root) == [0]

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `[5, 2, -3]` tree | All subtree sums tie |
| `[5, 2, -5]` tree | One sum appears twice |
| Single node | Minimum tree case |
| All zero values | Repeated identical subtree sums |