#508

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Most Frequent Subtree Sum

Identify the most frequent subtree sum in a binary tree using DFS and hash table tracking for efficient state management.

hash table tree depth first search binary tree

Problem Statement

Given the root of a binary tree, calculate the sum of each subtree rooted at every node, including the node itself, and determine the sum(s) that occur most frequently. Return all sums that have the highest frequency in any order.

Each node contains an integer value. The number of nodes in the tree is in the range [1, 104], and each node's value can range from -105 to 105. You must compute the subtree sums efficiently, using a pattern that combines depth-first search with hash table state tracking.

Examples

Example 1

Input: root = [5,2,-3]

Output: [2,-3,4]

Example details omitted.

Example 2

Input: root = [5,2,-5]

Output: [2]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105

Solution Approach

DFS-Based Subtree Sum Calculation

Recursively traverse the tree in a post-order manner, computing the sum of the current node plus its left and right subtrees. Return the sum to the parent call for aggregation.

Frequency Tracking with Hash Table

Store each computed subtree sum in a hash table and increment its count. Keep track of the maximum frequency dynamically to simplify retrieval at the end.

Extract Most Frequent Sums

After traversing all nodes, iterate through the hash table and collect all sums with the maximum frequency. Return the result as a list in any order, accommodating ties.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) since each node is visited once during DFS. Space complexity is O(N) for the hash table storing subtree sums, plus O(H) for the recursion stack where H is tree height.

What Interviewers Usually Probe

Check if the candidate correctly computes subtree sums without redundant recalculation.
Observe whether the hash table is updated inline during DFS for accurate frequency tracking.
Verify handling of ties and negative node values in the final result list.

Common Pitfalls or Variants

Common pitfalls

Recomputing subtree sums multiple times instead of storing results in a hash table.
Failing to handle multiple sums with the same maximum frequency correctly.
Ignoring negative values, which can appear frequently in subtree sums and affect frequency counts.

Follow-up variants

Return the least frequent subtree sums instead of the most frequent ones.
Compute the sum of all subtrees whose sums fall within a specific range.
Adapt the problem to an N-ary tree where each node can have more than two children.

FAQ

What is the main pattern behind Most Frequent Subtree Sum?

The problem primarily uses binary-tree traversal combined with hash table frequency tracking to find the sums that appear most often.

Can the tree contain negative values?

Yes, node values range from -105 to 105, so negative sums must be correctly counted and included in the frequency calculation.

How are ties handled in the output?

If multiple subtree sums have the same highest frequency, return all such sums in any order.

What traversal is best for computing subtree sums?

Post-order DFS is optimal because it ensures child subtrees are summed before aggregating at the parent node.

What is the time and space complexity?

Time complexity is O(N) for visiting each node once, and space complexity is O(N) for the hash table plus O(H) for the recursion stack.

terminal

Solution

Solution 1: Hash Table + DFS

We can use a hash table $\textit{cnt}$ to record the frequency of each subtree sum. Then, we use depth-first search (DFS) to traverse the entire tree, calculate the sum of elements for each subtree, and update $\textit{cnt}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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]:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            s = l + r + root.val
            cnt[s] += 1
            return s

        cnt = Counter()
        dfs(root)
        mx = max(cnt.values())
        return [k for k, v in cnt.items() if v == mx]

Continue Practicing

#652 find duplicate subtrees #653 two sum iv input is a bst #863 all nodes distance k in binary tree