Sponsored
Sponsored
This approach uses an inorder traversal to exploit the nature of BSTs, where an inorder traversal yields elements in sorted order. Utilize a HashMap (or equivalent) to count the frequency of each element. Traverse the tree, update frequencies, and then determine the mode(s) based on maximum frequency.
Time Complexity: O(n), as each node is visited twice. Space Complexity: O(n) due to the recursion stack and the use of an array to store the modes.
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12class Solution {
13public:
14 vector<int> findMode(TreeNode* root) {
15 unordered_map<int, int> freq;
16 inorder(root, freq);
17 return findMaxFreq(freq);
18 }
19
20 void inorder(TreeNode* root, unordered_map<int, int>& freq) {
21 if (!root) return;
22 inorder(root->left, freq);
23 freq[root->val]++;
24 inorder(root->right, freq);
25 }
26
27 vector<int> findMaxFreq(unordered_map<int, int>& freq) {
28 int maxFreq = 0;
29 for (const auto& p : freq) {
30 maxFreq = max(maxFreq, p.second);
31 }
32 vector<int> modes;
33 for (const auto& p : freq) {
34 if (p.second == maxFreq) {
35 modes.push_back(p.first);
36 }
37 }
38 return modes;
39 }
40};This solution uses two main functions: one to perform an inorder traversal and fill the frequency map, and another to determine the mode(s) from this map.
Morris Traversal allows inorder traversal without using additional stack space, which could be advantageous in follow-up scenarios described by the problem constraints. By threading the tree, we can traverse without recursion or explicit stack, maintaining a space complexity of O(1).
Time Complexity: O(n), Space Complexity: O(1).
1In JavaScript, Morris Traversal's reduction of space is noted yet not fully constructed, with a nod to its potential efficiency gains.