# LeetCode: 501. Find Mode in Binary Search Tree

**The Problem**

Given the `root`

of a binary search tree (BST) with duplicates, return *all the mode(s) (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
the node's key.**less than or equal to** - The right subtree of a node contains only nodes with keys
the node's key.**greater than or equal to** - Both the left and right subtrees must also be binary search trees.

**Example:**

```
Input: [1,null,2,2]
Output: [2]
```

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
vector<int> findMode(TreeNode* root) {
vector<int> modes;
int maxValue = 0, currCount = 0;
int prevVal = INT_MIN;
transverse( modes,root, maxValue, currCount, prevVal );
return modes;
}
void transverse(
vector<int> &modes, TreeNode *root,
int &maxValue, int &currCount, int &prevVal
){
if( root == nullptr ) return;
TreeNode *left = root->left;
transverse( modes, root->left, maxValue, currCount, prevVal );
if ( root->val == prevVal ) ++currCount;
else currCount = 1;
if( currCount == maxValue ) {
modes.emplace_back(root->val);
} else if( currCount > maxValue ) {
modes.clear();
modes.emplace_back(root->val);
maxValue = currCount;
}
prevVal = root->val;
TreeNode *right = root->right;
transverse(modes, right, maxValue, currCount, prevVal);
}
```

This function performs an in-order traversal of the binary tree and calculates the mode(s). Here's how it works:

`if( root == nullptr ) return;`

: If the current node is null (empty), the function stops and returns.`transverse(modes, root->left, maxValue, currCount, prevVal);`

: Recursively traverse the left subtree.`if ( root->val == prevVal ) ++currCount;`

: If the current node's value is the same as the previous value encountered, increment the current count. This helps to keep track of consecutive occurrences of the same value.`else currCount = 1;`

: If the current value is different from the previous value, reset the current count to 1.`if( currCount == maxValue )`

: If the current count matches the maximum frequency encountered so far, add the current value to the`modes`

vector.`else if( currCount > maxValue )`

: If the current count surpasses the maximum frequency encountered, clear the`modes`

vector and update it with the current value. Also, update`maxValue`

with the new maximum frequency.`prevVal = root->val;`

: Update`prevVal`

with the current value for the next iteration.`transverse(modes, right, maxValue, currCount, prevVal);`

: Recursively traverse the right subtree.

Overall, this code counts the frequency of each value during the traversal and identifies the mode(s) of the binary tree by maintaining counts and comparing them to find the maximum frequency.