Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [1,null,2,2]
Output: [2]
Example 2:
Input: root = [0]
Output: [0]
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- -105 <= Node.val <= 105
My Solution
We can keep the counts of each number in the tree with a HashMap. In our helper function, we add to the count of the current node’s value and then recurse on the left and right subtrees. In our main function, we call the helper to get the counts HashMap. Then we iterate through all numbers in the HashMap and keep track of the maximum count. Finally we iterate again though the HashMap and add all numbers with a count equal to the maximum to our output list. Finally we add all elements of the output list to an array, because the problem expects the result to be in an array.
Time complexity is O(n) because we visit all nodes in the Binary Search Tree and then we iterate through our HashSet twice. Space complexity is also O(n) due to the space required for the HashMap.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int[] findMode(TreeNode root) {
List<Integer> modes = new ArrayList<>();
Map<Integer,Integer> cnts = new HashMap<>();
int max = 0;
counts(root, cnts);
for (int num : cnts.keySet()) {
max = Math.max(max, cnts.get(num));
}
for (int num : cnts.keySet()) {
if (cnts.get(num) == max) {
modes.add(num);
}
}
int[] out = new int[modes.size()];
for (int i = 0; i < out.length; i++) {
out[i] = modes.get(i);
}
return out;
}
public void counts(TreeNode root, Map<Integer,Integer> cnts) {
if (root == null) {
return;
}
cnts.put(root.val, cnts.getOrDefault(root.val,0)+1);
counts(root.left, cnts);
counts(root.right, cnts);
}
}