How to Retrieve the Key with a Maximum Value in a Treemap in Java?

O(1) complexity is not possible with TreeMap. you need to create one more map which uses value of first map as keys. or use BiMap

public TreeBiMap implements Map {
   private Map<Integer, Integer> map;
   private Map<Integer, Integer> reverseMap;
   public TreeBiMap() {
     map = new TreeMap<>();
     reverseMap = new TreeMap<>();
   }

   public void put(Integer key, Integer value) {
      map.put(key, value);
      reverseMap.put(value, key);
   }

   public Integer getMaxValue() {
      return reverseMap.lastEntry().getKey()
   }

}

The answer provided by @PeterLawrey answers the question fair enough. If you are looking for a simpler implementation, here it is:

TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
// populate the tree with values
Map.Entry<Integer, Integer> maxEntry = null;
for(Map.Entry<Integer, Integer> entry : tree.entrySet()){
   if(maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0)
      maxEntry = entry;
}

System.out.println("The key with maximum value is : " + maxEntry.getKey());

Do you depend on using a TreeMap/do you fill it yourself? I ran into a similar situation and extended the TreeMap by the missing functionality:

public class TreeMapInteger<T> extends TreeMap<Integer,T> {

    private static final long serialVersionUID = -1193822925120665963L;

    private int minKey = Integer.MAX_VALUE;
    private int maxKey = Integer.MIN_VALUE;

    @Override
    public T put(Integer key, T value) {

        if(key > maxKey) {
            maxKey = key;
        }

        if(key < minKey) {
            minKey = key;
        }

        return super.put(key, value);

    }

    public int getMaxKey() {
        return maxKey;
    }

    public int getMinKey() {
        return minKey;
    }

}

This won't decrease the complexity but depending on when and how your Map is filled having the values prepared for you when you need them might be preferable.

As others have said, you basically have to iterator each map entry and find the entry with the largest value.

Note that in your post you made a mistake.

I know that maximum and minimum keys can be retrieved from a TreeMap in O(1) time as follows:

int maxKey = tree.lastEntry().getKey();
int minKey = tree.firstEntry().getKey();

I think the time complexity should be O(lgn).

The source code of getLastEntry:

/**
     * Returns the last Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final Entry<K,V> getLastEntry() {
        Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

Also refer to this post in SO