Most Frequent Subtree Sum

Med

#0495Time: O(N^2), where N is the number of nodes. The initial traversal to get all nodes is O(N). Then, for each of the N nodes, we perform a subtree sum calculation which can take up to O(N) time in the worst case (a skewed tree). This leads to a total time complexity dominated by N * O(N) = O(N^2).Space: O(N), where N is the number of nodes. We need O(N) space to store the list of all nodes and up to O(N) for the hash map. The recursion stack for the sum calculation can also go up to O(N) in the worst case of a skewed tree.

Algorithms

Depth-First Search

Data structures

Hash Table Tree Binary Tree

Prompt

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, 10⁴].
-10⁵ <= Node.val <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every node in the tree. For each node, a separate traversal is initiated to calculate the sum of its subtree. The frequencies of these sums are stored in a hash map. This method is straightforward but inefficient due to repeated calculations.

Algorithm

1. Define a helper function getAllNodes to traverse the tree (e.g., using pre-order traversal) and store all nodes in a list.
1. Define another helper function calculateSubtreeSum that takes a node and recursively calculates the sum of all nodes in its subtree.
1. In the main function, first call getAllNodes to populate a list of all tree nodes.
1. Initialize a HashMap<Integer, Integer> to store the frequency of each subtree sum and an integer maxFreq to track the maximum frequency found.
1. Iterate through each node in the list of all nodes.
1. For each node, call calculateSubtreeSum to get its subtree sum.
1. Update the frequency of this sum in the hash map and update maxFreq if necessary.
1. After iterating through all nodes, create a result list.
1. Iterate through the hash map and add any sum whose frequency equals maxFreq to the result list.
1. Convert the result list to an integer array and return it.

Walkthrough

The core idea of this brute-force method is to separate the problem into two main parts: identifying all subtrees and then calculating the sum for each one. First, we perform a full traversal of the tree to get a list of all nodes. Each node in this list is the root of a subtree. Then, we iterate through this list. For each node, we perform a second, independent traversal starting from that node to compute its subtree sum. We use a hash map to keep track of how many times each sum occurs. After calculating all subtree sums, we find the highest frequency and collect all sums that have this frequency.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int[] findFrequentTreeSum(TreeNode root) {18        if (root == null) {19            return new int[0];20        }21 22        List<TreeNode> nodes = new ArrayList<>();23        getAllNodes(root, nodes);24 25        Map<Integer, Integer> freqMap = new HashMap<>();26        int maxFreq = 0;27 28        for (TreeNode node : nodes) {29            int sum = calculateSubtreeSum(node);30            int currentFreq = freqMap.getOrDefault(sum, 0) + 1;31            freqMap.put(sum, currentFreq);32            maxFreq = Math.max(maxFreq, currentFreq);33        }34 35        List<Integer> resultList = new ArrayList<>();36        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {37            if (entry.getValue() == maxFreq) {38                resultList.add(entry.getKey());39            }40        }41 42        return resultList.stream().mapToInt(i -> i).toArray();43    }44 45    private void getAllNodes(TreeNode node, List<TreeNode> nodes) {46        if (node == null) {47            return;48        }49        nodes.add(node);50        getAllNodes(node.left, nodes);51        getAllNodes(node.right, nodes);52    }53 54    private int calculateSubtreeSum(TreeNode node) {55        if (node == null) {56            return 0;57        }58        return node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);59    }60}

Complexity

Time

O(N^2), where N is the number of nodes. The initial traversal to get all nodes is O(N). Then, for each of the N nodes, we perform a subtree sum calculation which can take up to O(N) time in the worst case (a skewed tree). This leads to a total time complexity dominated by N * O(N) = O(N^2).

Space

O(N), where N is the number of nodes. We need O(N) space to store the list of all nodes and up to O(N) for the hash map. The recursion stack for the sum calculation can also go up to O(N) in the worst case of a skewed tree.

Trade-offs

Pros

Conceptually straightforward and easy to break down into smaller, distinct problems.

Cons

Highly inefficient due to redundant computations. The value of a node is included in the sum calculation for itself and for every one of its ancestors, leading to repeated work.

A more efficient approach is to use a single post-order traversal. This traversal order (Left, Right, Root) naturally allows us to compute the sum of a subtree right after we have computed the sums of its children's subtrees. We can calculate each subtree sum and update its frequency in the same pass, avoiding redundant calculations.

Algorithm

1. Initialize a HashMap<Integer, Integer> to store sum frequencies and a global or member variable maxFreq to track the maximum frequency.
1. Define a recursive helper function that performs a post-order traversal, let's call it postOrderSum(node).
1. Base Case: If the current node is null, return 0.
1. Recursive Step: Recursively call postOrderSum for the left and right children to get their respective subtree sums, leftSum and rightSum.
1. Process Node: Calculate the sum of the subtree rooted at the current node: currentSum = node.val + leftSum + rightSum.
1. Update the frequency of currentSum in the hash map.
1. Update maxFreq if the new frequency of currentSum is greater than the current maxFreq.
1. Return currentSum to be used by its parent's calculation.
1. Start the process by calling postOrderSum(root).
1. After the traversal is complete, iterate through the hash map's keys. Collect all sums whose frequency equals maxFreq.
1. Return the collected list of sums as an array.

Walkthrough

This optimized approach leverages the properties of post-order traversal. The sum of a subtree at a given node is the node's own value plus the sums of its left and right subtrees. By processing children before the parent, a post-order traversal ensures that when we visit a node, the sums for its left and right subtrees have already been computed.

We can define a recursive function that traverses the tree in a post-order fashion. This function will return the sum of the subtree rooted at the node it's given. Inside this function, after computing the current node's subtree sum, we immediately update a frequency map. We also maintain a variable to keep track of the maximum frequency seen so far. This way, we compute all subtree sums and their frequencies in a single pass over the tree.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private Map<Integer, Integer> freqMap;18    private int maxFreq;19 20    public int[] findFrequentTreeSum(TreeNode root) {21        if (root == null) {22            return new int[0];23        }24 25        freqMap = new HashMap<>();26        maxFreq = 0;27 28        postOrderSum(root);29 30        List<Integer> resultList = new ArrayList<>();31        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {32            if (entry.getValue() == maxFreq) {33                resultList.add(entry.getKey());34            }35        }36 37        return resultList.stream().mapToInt(i -> i).toArray();38    }39 40    private int postOrderSum(TreeNode node) {41        if (node == null) {42            return 0;43        }44 45        int leftSum = postOrderSum(node.left);46        int rightSum = postOrderSum(node.right);47 48        int currentSum = node.val + leftSum + rightSum;49        50        int currentFreq = freqMap.getOrDefault(currentSum, 0) + 1;51        freqMap.put(currentSum, currentFreq);52        53        maxFreq = Math.max(maxFreq, currentFreq);54 55        return currentSum;56    }57}

Complexity

Time

O(N), where N is the number of nodes. We visit each node exactly once during the post-order traversal. Operations inside the recursive function (map access, addition) are O(1) on average. The final step of collecting results from the map takes at most O(N) time.

Space

O(N), where N is the number of nodes. The space is used by the hash map, which can store up to N distinct sums, and by the recursion stack. The depth of the recursion stack is equal to the height of the tree, H, which is O(N) in the worst case (a skewed tree) and O(log N) in the best case (a balanced tree).

Trade-offs

Pros

Optimal time complexity as it processes each node only once.
Combines sum calculation and frequency counting into a single, elegant traversal.

Cons

Requires extra space for the hash map and the recursion stack, which can be O(N) in the worst case for a skewed tree.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Integer , Integer > counter ; private int mx ; public int [] findFrequentTreeSum ( TreeNode root ) { counter = new HashMap <>(); mx = Integer . MIN_VALUE ; dfs ( root ); List < Integer > res = new ArrayList <>(); for ( Map . Entry < Integer , Integer > entry : counter . entrySet ()) { if ( entry . getValue () == mx ) { res . add ( entry . getKey ()); } } int [] ans = new int [ res . size ()]; for ( int i = 0 ; i < res . size (); ++ i ) { ans [ i ] = res . get ( i ); } return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int s = root . val + dfs ( root . left ) + dfs ( root . right ); counter . put ( s , counter . getOrDefault ( s , 0 ) + 1 ); mx = Math . max ( mx , counter . get ( s )); return s ; } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map < int , int > counter ; int mx = 0 ; vector < int > findFrequentTreeSum ( TreeNode * root ) { mx = INT_MIN ; dfs ( root ); vector < int > ans ; for ( auto & entry : counter ) if ( entry . second == mx ) ans . push_back ( entry . first ); return ans ; } int dfs ( TreeNode * root ) { if ( ! root ) return 0 ; int s = root -> val + dfs ( root -> left ) + dfs ( root -> right ); ++ counter [ s ]; mx = max ( mx , counter [ s ]); return s ; } };

1# 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 : TreeNode ) -> List [ int ]: def dfs ( root ): if root is None : return 0 left , right = dfs ( root . left ), dfs ( root . right ) s = root . val + left + right counter [ s ] += 1 return s counter = Counter () dfs ( root ) mx = max ( counter . values ()) return [ k for k , v in counter . items () if v == mx ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem