# LC 501. Find Mode in Binary Search Tree

### [Problem link](https://leetcode.com/problems/find-mode-in-binary-search-tree/)

###### tags: `leedcode` `easy` `c++` `BST`

Given the <code>root</code> of a binary search tree (BST) with duplicates, return all the <a href="https://en.wikipedia.org/wiki/Mode_(statistics)" target="_blank">mode(s)</a> (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in **any order** .

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.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/11/mode-tree.jpg" style="width: 142px; height: 222px;" />

Input: root = [1,null,2,2]
Output: [2]

**Example 2:**

Input: root = [0]
Output: [0]

**Constraints:**

- The number of nodes in the tree is in the range <code>[1, 10⁴]</code>.
- <code>-10⁵ <= Node.val <= 10⁵</code>

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

class Solution {
public:
    void traversal(TreeNode *cur, unordered_map<int, int> &counter) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left, counter);
        counter[cur->val]++;
        traversal(cur->right, counter);
    }

    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> counter;
        traversal(root, counter);

        int maxFreq = 0;
        for (auto &[key, val]: counter) {
            maxFreq = max(maxFreq, val);
        }

        vector<int> res;
        for (auto &[key, val]: counter) {
            if (val == maxFreq) {
                res.push_back(key);
            }
        }
        return res;
    }
};

## Solution 2 - (Follow up)
#### C++

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        stack<TreeNode *> st;
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        int maxCnt = 0;
        int cnt = 0;
        vector<int> res;
        
        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                if (pre != nullptr && pre->val == cur->val) {
                    cnt++;
                } else {
                    cnt = 1;
                }
                if (cnt == maxCnt) {
                    res.push_back(cur->val);
                }
                if (cnt > maxCnt) {
                    maxCnt = cnt;
                    res.clear();
                    res.push_back(cur->val);
                }
                pre = cur;
                cur = cur->right;
            }
        }
        return res;
    }
};

>### Complexity
>n = The number of nodes in the tree
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(1) |

## Note
follow up - [代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.md)