# 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).

``````class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
int mx = 0;
unordered_map<int, int> m;
inorder(root, m, mx);
for (auto a : m) {
if (a.second == mx) {
res.push_back(a.first);
}
}
return res;
}
void inorder(TreeNode* node, unordered_map<int, int>& m, int& mx) {
if (!node) return;
inorder(node->left, m, mx);
mx = max(mx, ++m[node->val]);
inorder(node->right, m, mx);
}
};
``````

``````class Solution {
public:
vector<int> findMode(TreeNode* root) {
if (!root) return {};
vector<int> res;
TreeNode *p = root;
stack<TreeNode*> s;
unordered_map<int, int> m;
int mx = 0;
while (!s.empty() || p) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
mx = max(mx, ++m[p->val]);
p = p->right;
}
for (auto a : m) {
if (a.second == mx) {
res.push_back(a.first);
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
int mx = 0, cnt = 1;
TreeNode *pre = NULL;
inorder(root, pre, cnt, mx, res);
return res;
}
void inorder(TreeNode* node, TreeNode*& pre, int& cnt, int& mx, vector<int>& res) {
if (!node) return;
inorder(node->left, pre, cnt, mx, res);
if (pre) {
cnt = (node->val == pre->val) ? cnt + 1 : 1;
}
if (cnt >= mx) {
if (cnt > mx) res.clear();
res.push_back(node->val);
mx = cnt;
}
pre = node;
inorder(node->right, pre, cnt, mx, res);
}
};
``````

``````class Solution {
public:
vector<int> findMode(TreeNode* root) {
if (!root) return {};
vector<int> res;
TreeNode *p = root, *pre = NULL;
stack<TreeNode*> s;
int mx = 0, cnt = 1;;
while (!s.empty() || p) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
if (pre) {
cnt = (p->val == pre->val) ? cnt + 1 : 1;
}
if (cnt >= mx) {
if (cnt > mx) res.clear();
res.push_back(p->val);
mx = cnt;
}
pre = p;
p = p->right;
}
return res;
}
};
``````

Binary Tree Inorder Traversal

https://discuss.leetcode.com/topic/77335/proper-o-1-space

https://discuss.leetcode.com/topic/77080/c-dfs-time-o-n-space-o-n

https://discuss.leetcode.com/topic/77077/ugly-but-straight-forward-java-solution

https://discuss.leetcode.com/topic/77330/java-4ms-beats-100-extra-o-1-solution-no-map

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation