Most Frequent Subtree Sum - Solution & Explanation
Problem Statement
Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.
The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).
Example 1:
Input: root = [5,2,-3] Output: [2,-3,4]
Example 2:
Input: root = [5,2,-5] Output: [2]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105
Approach Overview
Problem Overview: You receive the root of a binary tree and must compute the sum of every subtree. A subtree sum equals the value of the node plus the sums of its left and right subtrees. The task is to return the value(s) that appear most frequently among all subtree sums.
Approach 1: Post-order Traversal with Hash Map (O(n) time, O(n) space)
The most direct solution uses depth-first search with post-order traversal. Process the left and right children first, compute their subtree sums, then calculate the current node's sum as node.val + leftSum + rightSum. Store each computed sum in a hash table that tracks how many times each sum appears.
Post-order traversal is critical because a node’s subtree sum depends on its children. As DFS unwinds, update the frequency map and track the maximum occurrence count. After the traversal finishes, iterate through the map and collect all sums with the highest frequency. This approach touches each node exactly once, giving O(n) time complexity and O(n) space for the recursion stack and frequency map.
This method is efficient and straightforward. Most production and interview solutions follow this pattern because it combines computation and frequency tracking in a single traversal of the binary tree.
Approach 2: Pre-compute Subtree Sums then DFS Frequency Count (O(n) time, O(n) space)
This variant separates the computation into two logical phases. First perform a DFS to compute and store the subtree sum for every node. The recursion still follows post-order so that child sums are available before calculating the parent’s sum. Store each result in a list or array during traversal.
Once all subtree sums are collected, run a second pass that counts frequencies using a hash map. Track the maximum frequency while iterating over the stored sums. Finally, return all sums whose frequency matches that maximum.
The algorithm still runs in O(n) time because each node is processed a constant number of times. Space usage remains O(n) for the stored subtree sums and the frequency map. This structure can make debugging easier because the computation and counting phases are separated, but it requires slightly more memory and an additional pass.
Recommended for interviews: The post-order traversal with a hash map is the expected solution. It demonstrates a solid understanding of recursive tree processing and efficient frequency counting. The two-pass approach also works, but interviewers usually prefer the single DFS version because it computes subtree sums and tracks frequencies in one traversal.
Approach 1: Post-order Traversal with Hash Map
This approach involves using a post-order traversal to calculate the subtree sum for each node. We store each computed sum in a hash map or dictionary which keeps track of how many times each sum appears. After the traversal, we determine the maximum frequency of the sums and return the list of all sums that have this maximum frequency.
The solution creates a simple binary tree structure and uses a post-order traversal to visit each node in the tree. Each subtree sum is calculated and stored in a hash map, where keys are the sums and values are their frequencies. We then determine the highest frequency sums and return them.
Complexity
Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(N), for storing sums in the hash map.
Approach 2: Pre-compute and DFS
This method involves pre-computing the subtree sums using a depth-first search (DFS). A map is used to record the number of occurrences of each sum, similar to the first method but differing in traversal style. Instead of post-order, a conventional DFS approach computes sums as the tree is traversed depth-first.
In this C solution, we use a full DFS to traverse through each node and pre-compute all subtree sums, storing them in a hash table that maintains their frequency. The method allows for an efficient retreival of the most frequent sums post traversal.
Complexity
Time Complexity: O(N), visiting every node by DFS.
Space Complexity: O(N), storing sums and frequencies.
Approach 3: Hash Table + DFS
We can use a hash table 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 cnt.
Finally, we traverse cnt to find all subtree sums that appear most frequently.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Post-order Traversal with Hash Map | Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. |
| Pre-compute and DFS | Time Complexity: O(N), visiting every node by DFS. |
| Hash Table + DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Post-order Traversal with Hash Map | O(n) | O(n) | General case. Best interview solution because subtree sums and frequency tracking happen in one DFS. |
| Pre-compute Subtree Sums + DFS Counting | O(n) | O(n) | Useful when separating computation and analysis phases for debugging or clarity. |
Video Solution
LeetCode 508( Most Frequent Subtree Sum) • MyCodingBuddy • 2,139 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Most Frequent Subtree Sum easy or hard?
Most Frequent Subtree Sum Python/Java solution
How to solve Most Frequent Subtree Sum in O(n)?
What is the best approach for Most Frequent Subtree Sum?
Is Most Frequent Subtree Sum asked at Google/Amazon/Meta?
What data structure is used in Most Frequent Subtree Sum?
What is the time complexity of Most Frequent Subtree Sum?
Ready to solve this problem?
Practice Most Frequent Subtree Sum with our built-in code editor and test cases.
Practice on FleetCode