501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.

• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.

• Both the left and right subtrees must also be binary search trees.

For example: Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

// Brute Force with O(n) unordered_map
void helper(TreeNode* node, unordered_map<int, int>& m) {
    if (!node) return;
    ++m[node->val];
    helper(node->left, m);
    helper(node->right, m);
}
vector<int> findMode(TreeNode* root) { // time: O(n); space: O(n)
    unordered_map<int, int> m;
    helper(root, m);
    int mx = 0;
    vector<int> res;
    for (auto& e : m) {
        if (e.second > mx) {
            mx = e.second;
            res.clear();
            res.push_back(e.first);
        } else if (e.second == mx) {
            res.push_back(e.first);
        }
    }
    return res;
}

// Recursion with Constant Space Usage
void helper(TreeNode* node, TreeNode*& pre, int& cnt, int& mx, vector<int>& res) {
    if (!node) return;
    helper(node->left, pre, cnt, mx, res);
    if (pre) cnt = (pre->val == node->val) ? cnt + 1 : 1;
    if (cnt >= mx) {
        if (cnt > mx) res.clear();
        mx = cnt;
        res.push_back(node->val);
    }
    pre = node;
    helper(node->right, pre, cnt, mx, res);
}
vector<int> findMode(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    int mx = 0, cnt = 1;
    TreeNode* pre = nullptr;
    helper(root, pre, cnt, mx, res);
    return res;
}