How to Find out the Most Frequent Subtree Sum using Depth First Search Algorithm?

Given the root of a tree, you are asked to find the most frequent subtree sum. 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). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

  5
 /  \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

Most Frequent Subtree Sum using DFS Algorithm

We can use a hash map e.g. unordered_map in C++ to store the Subtree sum and their frequencies. Also, we need to keep track of the maximum frequency so that later we can iterate the map and push the sum (that is one of the most occurred) to the result.

We need to search the entire binary tree using Depth First Search algorithm, in recursion style.

The frequencies of the current subtree sum are updated before recursion calls.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        vector<int> r;
        for (auto it = sums.begin(); it != sums.end(); ++ it) {
            if (it->second == count) { // check if it is one of the max occurred number
                r.push_back(it->first);
            }
        }
        return r;
    }
    
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftsum = dfs(root->left);
        int rightsum = dfs(root->right);
        int sum = root->val + leftsum + rightsum;
        if (sums.find(sum) == sums.end()) {
            sums[sum] = 1;
        } else {
            sums[sum] ++;
        }
        count = max(count, sums[sum]); // update max freq
        return sum;
    }
    
private:
    // sum and the frequencies 
    unordered_map<int, int> sums;
    // max frequency
    int count = 0;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        vector<int> r;
        for (auto it = sums.begin(); it != sums.end(); ++ it) {
            if (it->second == count) { // check if it is one of the max occurred number
                r.push_back(it->first);
            }
        }
        return r;
    }
    
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftsum = dfs(root->left);
        int rightsum = dfs(root->right);
        int sum = root->val + leftsum + rightsum;
        if (sums.find(sum) == sums.end()) {
            sums[sum] = 1;
        } else {
            sums[sum] ++;
        }
        count = max(count, sums[sum]); // update max freq
        return sum;
    }
    
private:
    // sum and the frequencies 
    unordered_map<int, int> sums;
    // max frequency
    int count = 0;
};

The runtime complexity for the above C++ DFS algorithm is O(N) where N is the number of the nodes in the binary tree i.e. each node has to be visited exactly once. And the space complexity is O(N) because a binary tree with N nodes will have N subtrees exactly and we are using a hashmap to store those sum values.

With C++ unordered_map, the default value (when it is integer) is zero, thus we can simply do this instead to update the counter:

1

sums[sum] ++;

sums[sum] ++;

The same DFS algorithm can be applied to solve this: The Maximum Average Subtree of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —