LeetCode: Most Frequent Subtree Sum

Question

My solution to LeetCode problem Most Frequent Subtree Sum works, but I have several questions regarding the code. I am also looking for an advice on how to improve the code.

Problem:

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.

Example 1

  5
 /  \
2   -3

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

Example 2

  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once

My questions:

1. The function get_sums_freqs returns an int, but when I call it, I do not assign the result to anything: get_sums_freqs (root, sum_freqs);. Is it ok to do it this way?

2. For some reason, it feels like a bad style to me to initialize the hash map unordered_map<int, int> sum_freqs; in one function and then pass it to another function to fill it out. Is there a better way to do it? Or is this a correct way?

My solution:

vector<int> find_frequent_tree_sum(TreeNode* root) {

    // Collect freqs of sums into map
    unordered_map<int, int> sum_freqs;
    get_sums_freqs (root, sum_freqs);

    // Get the max freq
    int max_freq = 0;
    unordered_map<int, int>::iterator it;
    for (it = sum_freqs.begin(); it != sum_freqs.end(); ++it) {
        max_freq = max(max_freq, it->second);
    }

    // Collect all the values, which freq == max_freq
    vector<int> res;
    //unordered_map<int, int>::iterator it;
    for (it = sum_freqs.begin(); it != sum_freqs.end(); ++it) {
        if (it->second == max_freq) {
            res.push_back(it->first);
        }
    }

    return res;
}

int get_sums_freqs (TreeNode* root, unordered_map<int, int>& sum_freqs) {

    if (root) {

        int curr_sum = root->val +
            get_sums_freqs (root->left, sum_freqs) + 
            get_sums_freqs (root->right, sum_freqs);

        sum_freqs[curr_sum]++;

        return curr_sum;

    } else {

        return 0;
    }
}

For context, here's the definition of TreeNode given by LeetCode:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Answer 1

The function get_sums_freqs returns an int, but when I call it, I do not assign the result to anything: get_sums_freqs (root, sum_freqs);. Is it ok to do it this way?

Your uneasiness here probably arises from the difference between a Tree and a TreeNode. A TreeNode is an internal tree detail, which should be hidden from the user of the Tree. I should be able to pass an Tree object to some function, and have it add some number of nodes to the Tree. If I pass an nullptr as the TreeNode * root, the caller can't modify my tree. Similarly, if two entities are supposed to share access to a Tree, that is fine as long as the TreeNode *root contains at least one node. But you can't share a common empty Tree; instead you have two nullptr ... which are not "shareable".

class Tree {
    TreeNode *root;
    int num_nodes;
    int max_depth;
}

Now we have a Tree object, which can be shared ... even if it is an empty tree. As a bonus, our Tree can hold meta-information about the tree, such as the number of nodes in the tree, the maximum depth of the tree, and so on.

The LeetCode challenge is promoting a broken tree model, by using a TreeNode * to represent a tree. It works, but it has issues; I wouldn't want to see it used in a professional "Project".

I prefer not to walk into nullptr nodes. Imagine:

void TreeNode::get_sums_freqs(unordered_map<int, int>& sum_freqs) { ... }

Now, you would be calling TreeNode::get_sums_freqs() with a nullptr for this, which is bad.

Instead:

int get_sums_freqs(TreeNode* node, unordered_map<int, int>& sum_freqs) {

    int curr_sum = root->val;

    if (node->left)
       curr_sum += get_sums_freqs(node->left, sum_freqs);
    if (node->right)
       curr_sum += get_sums_freqs(node->right, sum_freqs);

    sum_freqs[curr_sum]++;

    return curr_sum;
}

Note we are calling the current node node, instead of root. We need to start off the search at the root of the tree, which is a little different:

void tree_get_sums_freqs(Tree* tree, unordered_map<int, int> &sum_freqs) {
    if (tree->root) {
       root_sum = get_sums_freqs(tree->root, sum_freqs);
       sum_freqs[root_sum]++;
    }
}

No root_sum needs to be returned from this top-level.

Of course, since LeetCode doesn't define their trees this way, you have your odd, unused return value.

For some reason, it feels like a bad style to me to initialize the hash map unordered_map<int, int> sum_freqs; in one function and then pass it to another function to fill it out. Is there a better way to do it? Or is this a correct way?

This is fine. It is a visitor pattern. You create an accumulator object, and visit every node of your structure with it, to accumulate the results.