## Find Mode in Binary Search Tree

• Time:O(n)
• Space:O(\log n)

## C++

``````class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> ans;
int count = 0;
int maxCount = 0;

inorder(root, count, maxCount, ans);
return ans;
}

private:
TreeNode* pred = nullptr;

void inorder(TreeNode* root, int& count, int& maxCount, vector<int>& ans) {
if (!root)
return;

inorder(root->left, count, maxCount, ans);
updateCount(root, count, maxCount, ans);
inorder(root->right, count, maxCount, ans);
}

void updateCount(TreeNode* root, int& count, int& maxCount,
vector<int>& ans) {
if (pred && pred->val == root->val)
++count;
else
count = 1;

if (count > maxCount) {
maxCount = count;
ans = {root->val};
} else if (count == maxCount) {
ans.push_back(root->val);
}

pred = root;
}
};
``````

## JAVA

``````class Solution {
public int[] findMode(TreeNode root) {
List<Integer> ans = new ArrayList<>();
// count[0] := currCount
// count[1] := maxCount
int[] count = new int[2];

inorder(root, count, ans);
return ans.stream().mapToInt(i -> i).toArray();
}

private TreeNode pred = null;

private void inorder(TreeNode root, int[] count, List<Integer> ans) {
if (root == null)
return;

inorder(root.left, count, ans);
updateCount(root, count, ans);
inorder(root.right, count, ans);
}

private void updateCount(TreeNode root, int[] count, List<Integer> ans) {
if (pred != null && pred.val == root.val)
++count[0];
else
count[0] = 1;

if (count[0] > count[1]) {
count[1] = count[0];
ans.clear();
} else if (count[0] == count[1]) {
}

pred = root;
}
}
``````

## Python

``````class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.ans = []
self.pred = None
self.count = 0
self.maxCount = 0

def updateCount(root: Optional[TreeNode]) -> None:
if self.pred and self.pred.val == root.val:
self.count += 1
else:
self.count = 1

if self.count > self.maxCount:
self.maxCount = self.count
self.ans = [root.val]
elif self.count == self.maxCount:
self.ans.append(root.val)

self.pred = root

def inorder(root: Optional[TreeNode]) -> None:
if not root:
return

inorder(root.left)
updateCount(root)
inorder(root.right)

inorder(root)
return self.ans
``````