Better way to get highest key in treemap?

Question

Way1:

TreeMap<Integer, String> map = new TreeMap<Integer, String>();
int highestKey = map.lastKey();

Source Code of TreeMap.lastKey() from JDK:

 Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;

Way2:

TreeMap<Integer, String> map = new TreeMap<Integer, String>();
Object[] keys = map.keySet().toArray();
int highestKey = keys[keys.length - 1]

When you look into the implementation of the lastKey() we see that we have a while loop. I think time complexity for this is O(n).

This makes me think that Way2 is better or efficient way to implement in terms of time complexity. Is my understanding correct ? Which is the better way to use.

Bureau

Your way2 will throw ArrayIndexOutOfBoundsException when there is no item in map. – Christcrossrow

Running down the tree to a leaf node is O(log n) because that's the height of a (balanced) tree. – Shanaeshanahan

Answer 1

I think you got it wrong, the JDK implementation of lastKey() has a time complexity of O(logn) and not O(n) and no extra space complexity. It is a red-black tree(i.e., balanced).

And in the Way 2 to mentioned you are getting all the keys using keyset().toArray() which is O(n), also storing those in an object [] has extra space complexity of O(n) too.

With these, the JDK implementation has a much better time and space complexity.

Selfdenial

I think the time complexity for keySet() is O(1). #1851302 – Bureau

@adithyadn I know keySet() is O(1) for a plain Hashmap. But I doubt it is same for TreeMap as well. Will cross check the implementation and update. – Selfdenial

But then, one thing to note is you are calling map.keySet().toArray(). This is AbstractCollection.java and it has O(n) complexity, which makes finally Way2: to be O(n). Isn't it?.Please check. Regardless, it is good idea to verify treeMap.keySet(). – Selfdenial

Also, Since Set doesn't guarantee the iteration ordering of elements, assuming the last element of the Object[] keyswould be the highest element may not be safe as well. Good question, upvoting it. – Selfdenial

Answer 2

If you use a binary max-heap, the "largest" element will always be the root node of the tree and you can get it in O(1) time.

I don't think there is Java implementation of it, though, so you'd have to code it yourself.

Alternatively, provide the TreeMap a custom Comparator to flip the ordering of the elements, so the data you want is at the root, again making it O(1) lookup for the "largest" element.

Norenenorfleet