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.
1var findMode = function(root) {
2 const freq = new Map();
3 inorder(root, freq);
4 let maxFreq = Math.max(...freq.values());
5 const modes = [];
6 for (const [key, value] of freq) {
7 if (value === maxFreq) {
8 modes.push(key);
9 }
10 }
11 return modes;
12};
13
14function inorder(root, freq) {
15 if (!root) return;
16 inorder(root.left, freq);
17 freq.set(root.val, (freq.get(root.val) || 0) + 1);
18 inorder(root.right, freq);
19}JavaScript makes use of ES6 Maps and spreads to handle the frequency counting and maximum frequency determination.
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 public int[] FindMode(TreeNode root) {
// Placeholder code for Morris Traversal method.
return new int[0];
}
}C# currently serves as a roadmap for emphasizing the conceptual utility of Morris Traversal in mode determination, absent detailed node manipulation.