algoadvance

Leetcode 508. Most Frequent Subtree Sum

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 the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Clarifying Questions

  1. What should be returned if there are multiple subtree sums with the same highest frequency?
    • Return all the values with the highest frequency in any order.
  2. Can the tree contain negative values?
    • Yes, the tree can contain negative values.
  3. What should be done if the tree is empty?
    • If the tree is empty, the result should be an empty list.
  4. Are there any constraints on the size of the tree?
    • Typically, you can assume the height of the tree to be manageable within the typical constraints of memory and stack size (~10^4 nodes).

Strategy

  1. Post-order Traversal: Use post-order traversal to calculate the sum of each subtree.
  2. Tracking Frequencies: Use a HashMap to track the frequency of each subtree sum.
  3. Finding Most Frequent: Identify the maximum frequency from the HashMap and collect all sums that have this frequency.
  4. Base Case: Handle the case where the tree is empty by returning an empty list.

Code

import java.util.*;

public class Solution {
    private Map<Integer, Integer> sumFrequency;
    private int maxFrequency;

    public int[] findFrequentTreeSum(TreeNode root) {
        sumFrequency = new HashMap<>();
        maxFrequency = 0;

        postOrderTraversal(root);

        List<Integer> mostFrequentSums = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : sumFrequency.entrySet()) {
            if (entry.getValue() == maxFrequency) {
                mostFrequentSums.add(entry.getKey());
            }
        }

        return mostFrequentSums.stream().mapToInt(i -> i).toArray();
    }

    private int postOrderTraversal(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftSum = postOrderTraversal(node.left);
        int rightSum = postOrderTraversal(node.right);
        int totalSum = node.val + leftSum + rightSum;

        sumFrequency.put(totalSum, sumFrequency.getOrDefault(totalSum, 0) + 1);
        maxFrequency = Math.max(maxFrequency, sumFrequency.get(totalSum));

        return totalSum;
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI