Find Mode in a Binary Search Tree using C++
Find Mode in a Binary Search Tree
Given the root of a Binary Search Tree and we have to find the element which has the maximum frequency. There could be more than one element so we will store the elements in a vector.
Approach:
We will find the frequency of every element by using maps and also side by side, we will be finding the maximum frequency. Though the maximum frequency can be found later but it would take an extra traversal.
For traversing, we can use any method, here I have used the inorder traversal.
Finally, we will add every element having a frequency equal to the maximum frequency to the answer vector and return the vector.
Time Complexity:
For traversing the BST: O(n)
For Traversing the Map: O(n)
Space Complexity:
For storing elements: O(n)
C++ Code:
class Solution {
public:
vector<int> findMode(TreeNode* root) {
unordered_map<int,int>mpp;
int max=-1;
vector<int>ans;
inorder(root,mpp,max);
for(auto it:mpp){
if(it.second==max)ans.push_back(it.first);
}
return ans;
}
void inorder(TreeNode* root,unordered_map<int,int>&mpp,int &max){
if(root==NULL)return;
inorder(root->left,mpp,max);
mpp[root->val]++;
if(mpp[root->val]>max)max=mpp[root->val];
inorder(root->right,mpp,max);
}
};
Comments
Post a Comment