# C++ O(n) time and O(1) space by inorder traversal

• The basic idea is that the inorder traversal of the BST is in ascending order. For example, the inorder traversal of the BST [2, 1, 3] is [1, 2, 3]. Then we can easily find the most frequently occurred elements by comparing the successive elements.

class Solution {
public:
int maxFreq = 0, currFreq = 0, precursor = INT_MIN;
vector<int> res;

vector<int> findMode(TreeNode *root)
{
inorderTraversal(root);
return res;
}

void inorderTraversal(TreeNode *root)
{
if (root == NULL) return; // Stop condition
inorderTraversal(root->left); // Traverse left subtree
if (precursor == root->val) currFreq++;
else currFreq = 1;
if (currFreq > maxFreq)
{// Current node value has higher frequency than any previous visited
res.clear();
maxFreq = currFreq;
res.push_back(root->val);
}
else if (currFreq == maxFreq)
{// Current node value has a frequency equal to the highest of previous visited
res.push_back(root->val);
}
precursor = root->val; // Update the precursor
inorderTraversal(root->right); // Traverse right subtree
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.