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.

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 ; } }

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