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.
1class Solution:
2 def findMode(self, root: TreeNode) -> List[int]:
3 from collections import defaultdict
4 freq = defaultdict(int)
5 self.inorder(root, freq)
6 max_freq = max(freq.values())
7 return [key for key, value in freq.items() if value == max_freq]
8
9 def inorder(self, root, freq):
10 if not root:
11 return
12 self.inorder(root.left, freq)
13 freq[root.val] += 1
14 self.inorder(root.right, freq)The Python solution takes advantage of default dictionaries to simplify frequency tracking, then list comprehension to identify modes.
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.