# Java recursion O(n)

• `````` /*
use a hashmap to store sum - frequency
priority queue to store rank
recursively traverse each node and put their sum in hashmap and queue:
sum(node):
if node == null: return 0
int sum = node.val + sum(node.left) + sum(node.right)
map put (sum, map.get(sum) + 1)
return sum
*/
public class Solution {
Map<Integer, Integer> map = new HashMap<>();

public int[] findFrequentTreeSum(TreeNode root) {
sum(root);
List<Integer> result = new ArrayList<>();
int max = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
max = Math.max(entry.getValue(), max);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
}
int[] array = new int[result.size()];
for (int i = 0; i < result.size(); i += 1) array[i] = result.get(i);
return array;
}

public int sum(TreeNode node) {
if (node == null) return 0;
int sum = node.val + sum(node.left) + sum(node.right);
if (map.containsKey(sum)) map.put(sum, map.get(sum) + 1);
else map.put(sum, 1);
return sum;
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.