Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
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.
For example:
Given BST [1,n1ull,2,2], 1 \ 2 / 2 return [2].Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
My own solution, regardless of O(1) restriction:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] findMode(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
int max = traverse(root,map, 0);
List<Integer> mapKeys = new ArrayList<>(map.keySet());
Iterator<Integer> keyIt = mapKeys.iterator();
List<Integer> list = new ArrayList<>();
while (keyIt.hasNext()) {
int k = keyIt.next();
if(map.get(k)==max) list.add(k);
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); ++i) res[i] = list.get(i).intValue();
return res;
}
public int traverse(TreeNode root, Map<Integer, Integer> map, int max){
if(root!=null) {
int cnt = map.getOrDefault(root.val,0)+1;
if(max<cnt) max=cnt;
map.put(root.val, cnt);
max = traverse(root.left, map, max);
max = traverse(root.right, map, max);
}
return max;
}
}
Faster solution:
which keeps track of the max count when iterates thru the tree, since this is a BST, the left nodes should always be >= than root, we can simply check if the next nodes is same as the previous one when counting the appearance.
class Solution {
private int maxCnt = 0, cnt = 0;
private TreeNode prevNode = null;
private ArrayList<Integer> list = new ArrayList<Integer>();
public int[] findMode(TreeNode root) {
if(root==null) return new int[]{};
inOrder(root);
if(cnt>maxCnt){
list.clear();
list.add(prevNode.val);
}else if(cnt==maxCnt){
list.add(prevNode.val);
}
int[] modes = new int[list.size()];
for(int i=0;i<list.size();i++){
modes[i] = list.get(i);
}
return modes;
}
private void inOrder(TreeNode root){
if(root==null)
return;
inOrder(root.left);
updateCnt(root.val);
prevNode = root;
cnt++;
inOrder(root.right);
}
private void updateCnt(int val){
if(prevNode==null||prevNode.val!=val){
if(cnt>maxCnt){
list.clear();
if(prevNode!=null){
list.add(prevNode.val);
}
maxCnt = cnt;
}else if(cnt==maxCnt){
if(prevNode!=null){
list.add(prevNode.val);
}
}
cnt = 0;
}
}
}
###
I’ve seen several solutions claimed to be O(1) space, but I disagree. They traverse the tree in in-order and keep track of the current set of modes (among other things). But that’s not O(1) space, not even when disregarding recursion stack space (as explicitly allowed) and result space (not mentioned but reasonable). The set’s contents aren’t on stack space, so it can’t be disregarded that way. And if the values are for example 1,2,3,4,…,n-2,n-1,n-1 (unique values followed by one double value), the set grows to Ω(n) and it can’t be disregarded because the result only has size 1.
I think the way to do it properly is to do two passes. One to find the highest number of occurrences of any value, and then a second pass to collect all values occurring that often. Any other ideas?
Here’s a (two-pass) solution that I think can rightfully be called O(1) space. Both passes keep track of the current value etc, and the second pass additionally collects the modes in the result array. I took the value handling out of the in-order traversal into its own function for clarity. Also, this way you could very easily replace my recursive in-order traversal with for example Morris traversal. Then you wouldn’t even need to disregard the recursion stack space in order to claim O(1) extra space usage.
public class Solution {
public int[] findMode(TreeNode root) {
inorder(root);
modes = new int[modeCount];
modeCount = 0;
currCount = 0;
inorder(root);
return modes;
}
private int currVal;
private int currCount = 0;
private int maxCount = 0;
private int modeCount = 0;
private int[] modes;
private void handleValue(int val) {
if (val != currVal) {
currVal = val;
currCount = 0;
}
currCount++;
if (currCount > maxCount) {
maxCount = currCount;
modeCount = 1;
} else if (currCount == maxCount) {
if (modes != null)
modes[modeCount] = currVal;
modeCount++;
}
}
private void inorder(TreeNode root) {
TreeNode node = root;
while (node != null) {
if (node.left == null) {
handleValue(node.val);
node = node.right;
} else {
TreeNode prev = node.left;
while (prev.right != null && prev.right != node)
prev = prev.right;
if (prev.right == null) {
prev.right = node;
node = node.left;
} else {
prev.right = null;
handleValue(node.val);
node = node.right;
}
}
}
}
}