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.
1import java.util.*;
2
3public class Solution {
4 public int[] findMode(TreeNode root) {
5 Map<Integer, Integer> freqMap = new HashMap<>();
6 inorder(root, freqMap);
7 return findMaxFreq(freqMap);
8 }
9
10 private void inorder(TreeNode root, Map<Integer, Integer> freqMap) {
11 if (root == null) return;
12 inorder(root.left, freqMap);
13 freqMap.put(root.val, freqMap.getOrDefault(root.val, 0) + 1);
14 inorder(root.right, freqMap);
15 }
16
17 private int[] findMaxFreq(Map<Integer, Integer> freqMap) {
18 int maxFreq = 0;
19 for (int freq : freqMap.values()) {
20 maxFreq = Math.max(maxFreq, freq);
21 }
22 List<Integer> modes = new ArrayList<>();
23 for (int key : freqMap.keySet()) {
24 if (freqMap.get(key) == maxFreq) {
25 modes.add(key);
26 }
27 }
28 return modes.stream().mapToInt(i -> i).toArray();
29 }
30}This Java version accomplishes the task with a single Map to track value frequencies and auxiliary methods to gather mode elements.
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.