Most Frequent Subtree Sum - Leetcode Solution

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.

Subtree sum of a node is the sum of all the node values in its left and right sub-trees.

Solution:

Approach:

1. Traverse the entire given binary tree and store the subtree sum of each node in a map along with its count.
2. Find the maximum count by iterating over the map.
3. Append all the subtree sums of the nodes with maximum count to the result array.
4. Return the result array.

Algorithm:

1. Traverse the binary tree and recursively calculate the subtree sum for each node.
   • For each node, calculate its subtree sum by adding the node value, its left subtree sum and its right subtree sum.
   • Increment the count of the subtree sum in a map.
2. Iterate over the map to find the maximum count.
3. Traverse the map again and append all the subtree sums of the nodes with maximum count to the result array.
4. Return the result array.

Time Complexity: O(N^2), where N is the number of nodes in the binary tree. This is because we traverse the entire tree for each node to calculate the subtree sum.

Space Complexity: O(N), where N is the size of the map which stores the subtree sum and its count.

Java code:

// Definition for a binary tree node. 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 { Map<Integer, Integer> map; int maxFreq;

public int[] findFrequentTreeSum(TreeNode root) {
    map = new HashMap<>();
    maxFreq = 0;
    calculateSubtreeSum(root);
    
    List<Integer> list = new ArrayList<>();
    for(int key: map.keySet()) {
        if(map.get(key) == maxFreq) {
            list.add(key);
        }
    }
    
    int[] result = new int[list.size()];
    for(int i=0; i<list.size(); i++) {
        result[i] = list.get(i);
    }
    
    return result;
}

public int calculateSubtreeSum(TreeNode node) {
    if(node == null) {
        return 0;
    }
    
    int leftSum = calculateSubtreeSum(node.left);
    int rightSum = calculateSubtreeSum(node.right);
    int currSum = node.val + leftSum + rightSum;
    
    int currFreq = map.getOrDefault(currSum, 0) + 1;
    map.put(currSum, currFreq);
    maxFreq = Math.max(maxFreq, currFreq);
    
    return currSum;
}

}

1