LeetCode 501: Find Mode in Binary Search Tree
Problem Description
Explanation
To find the mode(s) in a binary search tree (BST), we will perform an in-order traversal of the BST while keeping track of the frequency of each element. We will use a hashmap to store the frequency of each element. Then, we will determine the element(s) with the highest frequency (mode) and return them.
- Perform an in-order traversal of the BST to collect the frequency of each element using a hashmap.
- Find the element(s) with the highest frequency (mode).
- Return the mode(s).
Time complexity: O(n) - where n is the number of nodes in the BST. Space complexity: O(n) - for the hashmap to store frequencies.
Solutions
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int maxFreq = 0;
public int[] findMode(TreeNode root) {
inorder(root);
List<Integer> modes = new ArrayList<>();
for (int key : map.keySet()) {
if (map.get(key) == maxFreq) {
modes.add(key);
}
}
return modes.stream().mapToInt(Integer::intValue).toArray();
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
map.put(node.val, map.getOrDefault(node.val, 0) + 1);
maxFreq = Math.max(maxFreq, map.get(node.val));
inorder(node.right);
}
}Related LeetCode Problems
Loading editor...