import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindModeInBinarySearchTree {
	public int[] findMode(TreeNode root){
		if(root == null) return new int[0];
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int[] maxCount = new int[1];
		helper(root, map, maxCount);
		List<Integer> list = new ArrayList<Integer>();
		for(int key : map.keySet()){
			if(map.get(key) == maxCount[0]) list.add(key);
		}
		int[] res = new int[list.size()];
		for(int i = 0; i < res.length; i++){
			res[i] = list.get(i);
		}
		return res;
	}
	
	private void helper(TreeNode node, Map<Integer, Integer> map, int[] maxCount){
		if(node.left != null) helper(node.left, map, maxCount);
		if(!map.containsKey(node.val)){
			map.put(node.val, 1);
			if(maxCount[0] == 0) maxCount[0]++;
		}
		else{
			map.put(node.val, map.get(node.val) + 1);
			if(map.get(node.val) > maxCount[0]) maxCount[0] = map.get(node.val);
		}
		if(node.right != null) helper(node.right, map, maxCount);
	}
}
