What is TreeMap, TreeSet & Natural Ordering in Java?

TreeMap and TreeSet keep their contents sorted, in a red-black tree. Every operation is O(log n). Two ways to supply the order. Without either, you get a

All topics

78 / 101

library

intermediate

TreeMap, TreeSet & Natural Ordering

Use sorted collections backed by Red-Black trees and understand Comparable vs Comparator in this context.

TreeMap and TreeSet keep their contents sorted, in a red-black tree. Every operation is O(log n).

TreeMap = a filing cabinet where files are always in alphabetical order. Finding any file takes longer than a HashMap (drawer scan) but you can instantly find 'all files from A to M.'

Key Concepts

    TreeMap<String, Integer> m = new TreeMap<>();
    m.put("banana", 2);  m.put("apple", 1);
    m.keySet();                  // [apple, banana] -- always sorted

Two ways to supply the order.

    // 1. natural ordering -- the element implements Comparable
    TreeSet<String> s = new TreeSet<>();

    // 2. a Comparator passed to the constructor
    new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
    new TreeMap<>(Comparator.comparing(Order::total).reversed());

Without either, you get a ClassCastException on the second insert — not the first, which needs nothing to compare against. That delayed failure confuses people.

ClassCastException

The navigation methods are the real reason to use these.

    firstKey() / lastKey()        the extremes
    floorKey(k) / ceilingKey(k)   nearest at or below / at or above
    lowerKey(k) / higherKey(k)    strictly below / above
    headMap(k) / tailMap(k)       everything before / after
    subMap(from, to)              a range
    descendingMap()               reversed view

Which makes range queries trivial:

    scores.subMap(60, 80);               // grades in the 60s and 70s
    events.ceilingKey(now);              // the next event due

A HashMap cannot answer either without scanning everything.

HashMap

The trap: ordering decides equality, not equals.

    Set<String> s = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
    s.add("ABC");
    s.add("abc");
    s.size();            // 1

equals

compareTo returned 0, so the second value was treated as a duplicate — even though "ABC".equals("abc") is false. A HashSet would hold both. Any comparator coarser than equals silently drops elements.

compareTo"ABC".equals("abc")HashSetequals

So choose by what you need.

    HashMap    O(1), no order              the default
    TreeMap    O(log n), sorted + ranges   when order or ranges matter
    LinkedHashMap  O(1), insertion order   when you only need stability

What the interviewer is probing.1. "A TreeSet with a case-insensitive comparator holds ABC and abc. What is the size?" Probing: that ordering defines equality here. Stalls: "Two, they are different strings." *Moves up:* one — compareTo returned zero so the second is a duplicate, even though equals is false. Any comparator coarser than equals silently drops elements.

2. "When would you choose TreeMap over HashMap?" Probing: whether you can name the capability. Stalls: "When you want it sorted." Moves up: sorted iteration and range queries — subMap, headMap, floorKey, ceilingKey — which a HashMap cannot answer without scanning everything.

3. "You insert into a TreeSet and get ClassCastException on the second add. Why?" Probing: the delayed failure. Stalls: "The types are wrong." Moves up: the element does not implement Comparable and no comparator was supplied; the first insert has nothing to compare against, so it only fails on the second.

4. "What is the cost difference?" Probing: complexity. Stalls: "Both are fast." Moves up: O(1) for HashMap against O(log n) for TreeMap, because the tree is kept balanced on every insert and removal.