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 <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11// Helper function to do inorder traversal and record frequency
12void inorder(struct TreeNode* root, int *modeCount, int *maxCount, int lastVal, int currentCount) {
13 if (root == NULL) return;
14 inorder(root->left, modeCount, maxCount, lastVal, currentCount);
15
16 if (lastVal == root->val) {
17 currentCount++;
18 } else {
19 currentCount = 1;
20 }
21
22 if (currentCount > *maxCount) {
23 *maxCount = currentCount;
24 *modeCount = 1;
25 } else if (currentCount == *maxCount) {
26 (*modeCount)++;
27 }
28 lastVal = root->val;
29 inorder(root->right, modeCount, maxCount, lastVal, currentCount);
30}
31
32// Fill modes array
33void findModes(struct TreeNode* root, int *modes, int *index, int maxCount, int lastVal, int currentCount) {
34 if (root == NULL) return;
35 findModes(root->left, modes, index, maxCount, lastVal, currentCount);
36
37 if (lastVal == root->val) {
38 currentCount++;
39 } else {
40 currentCount = 1;
41 }
42
43 if (currentCount == maxCount) {
44 modes[*index] = root->val;
45 (*index)++;
46 }
47 lastVal = root->val;
48 findModes(root->right, modes, index, maxCount, lastVal, currentCount);
49}
50
51int* findMode(struct TreeNode* root, int* returnSize) {
52 int modeCount = 0, maxCount = 0;
53 inorder(root, &modeCount, &maxCount, INT_MIN, 0);
54 int* modes = (int*)malloc(sizeof(int) * modeCount);
55 int index = 0;
56 findModes(root, modes, &index, maxCount, INT_MIN, 0);
57 *returnSize = modeCount;
58 return modes;
59}This code performs two passes of inorder traversal. First, it determines the highest frequency of any value, then it constructs an array of all values with this frequency.
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).
1#
C implementation of Morris Traversal is complex and often requires intricate manipulation of node pointers. This outline conceptually placeholders the possible linking structure one would apply.