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.

A subtree sum is defined as the sum of all the node values in a subtree.

Example:

Input: root = [5,2,-3]
Output: [2,-3,4]
Explanation: 
  5
 / \
2  -3
The subtree sums are 2, -3, and 4.

Example:

Input: root = [5,2,-5]
Output: [2]
Explanation: 
  5
 / \
2  -5
The subtree sums are 2, -5, and 2.

Clarifying Questions

  1. Input Constraints:
    • What is the range of the node values in the tree?
    • Can the tree contain negative values?
    • What is the maximum number of nodes in the tree?
  2. Output Specification:
    • Should the output be sorted in any particular order if there is a tie?
    • Is the function expected to handle empty tree cases?

Assuming the function should handle negative values, not necessarily be sorted in any order if there’s a tie, and can handle up to typical tree node constraints (e.g., values between INT_MIN and INT_MAX, nodes count typical to competitive programming constraints).

Strategy

  1. DFS Traversal:
    • Use a depth-first search (DFS) to traverse the tree and compute the subtree sums for each node.
  2. Subtree Sum Calculation:
    • For every node, the subtree sum is the node’s value plus the sum of its left and right subtrees.
  3. Frequency Count:
    • Maintain a hash map to count the frequency of each subtree sum encountered.
  4. Determining Most Frequent Sums:
    • Find the maximum frequency from the frequency map and collect all subtree sums that have this frequency.

Time Complexity

Overall, the approach has a time complexity of O(N), where N is the number of nodes in the tree.

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <functional> // for std::function

using namespace std;

// 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:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        if (!root) {
            return {};
        }

        unordered_map<int, int> sumFrequencyMap;
        int maxFrequency = 0;

        function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
            if (!node) {
                return 0;
            }

            int leftSum = dfs(node->left);
            int rightSum = dfs(node->right);
            int subtreeSum = node->val + leftSum + rightSum;

            sumFrequencyMap[subtreeSum]++;
            maxFrequency = max(maxFrequency, sumFrequencyMap[subtreeSum]);

            return subtreeSum;
        };

        dfs(root);

        vector<int> result;
        for (const auto& pair : sumFrequencyMap) {
            if (pair.second == maxFrequency) {
                result.push_back(pair.first);
            }
        }

        return result;
    }
};

This code defines a Solution class with a findFrequentTreeSum function that takes the root of a binary tree and returns a vector containing the most frequent subtree sums. The code uses DFS to traverse the tree, calculates subtree sums, and maintains a frequency count of these sums to identify the most frequent ones.

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