Chapter 58 of 77

TreeSet & TreeMap in Java

In the HashSet and HashMap chapters, we saw that they are very fast, but they do not keep elements in any particular order. If you print a HashSet of marks, the numbers can come out in any order.

But many problems need sorted data: a leaderboard, a dictionary of words, prices from lowest to highest, or "find the closest available time slot after 3 PM". For these, Java provides TreeSet and TreeMap.

TreeSet is a Set that keeps its elements sorted. TreeMap is a Map that keeps its keys sorted.

Both are in the java.util package, and both keep their data sorted automatically, every time you add or remove something.

How They Work Inside

As the name suggests, both are built on a tree. Specifically, they use a red-black tree, a kind of self-balancing binary search tree. In a binary search tree, everything in a node's left subtree is smaller than the node and everything in its right subtree is larger:

            72
          /    \
        45      91       smaller → left, larger → right
          \
           60

"Self-balancing" means the tree automatically rearranges itself so it never becomes a long chain. Its height stays around log n, so adding, removing, and searching all take O(log n) time. That is a little slower than the O(1) average of HashSet and HashMap, and that is the price you pay for keeping everything in order.

You don't need to know how the balancing works to use these classes. You'll study binary search trees in detail in Data Structures.

Creating a TreeSet

import java.util.TreeSet;

class Main {
    public static void main(String[] args) {

        TreeSet<Integer> marks = new TreeSet<>();

        marks.add(72);
        marks.add(45);
        marks.add(91);
        marks.add(60);
        marks.add(45);   // duplicate, ignored

        System.out.println(marks);
        System.out.println("Lowest: " + marks.first());
        System.out.println("Highest: " + marks.last());
        System.out.println("Has 60? " + marks.contains(60));

        TreeSet<String> names = new TreeSet<>();
        names.add("Rohan");
        names.add("Ananya");
        names.add("Zara");
        names.add("Ishaan");
        System.out.println(names);
    }
}

Output:

[45, 60, 72, 91]
Lowest: 45
Highest: 91
Has 60? true
[Ananya, Ishaan, Rohan, Zara]

Just like a HashSet, a TreeSet ignores duplicates. The difference is that it always prints (and loops) in ascending order: numbers from smallest to largest, Strings in alphabetical (dictionary) order. first() and last() give the smallest and largest elements directly.

Finding Nearby Values in a TreeSet

The real power of TreeSet is that it can answer questions like "what is the closest value to X?" in O(log n) time. A HashSet cannot do this at all.

import java.util.TreeSet;

class Main {
    public static void main(String[] args) {

        TreeSet<Integer> prices = new TreeSet<>();
        prices.add(199);
        prices.add(499);
        prices.add(999);
        prices.add(1499);
        prices.add(2999);

        // Closest values around 1000
        System.out.println("floor(1000)   = " + prices.floor(1000));    // largest <= 1000
        System.out.println("ceiling(1000) = " + prices.ceiling(1000));  // smallest >= 1000
        System.out.println("lower(999)    = " + prices.lower(999));     // largest < 999
        System.out.println("higher(999)   = " + prices.higher(999));    // smallest > 999
        System.out.println("floor(100)    = " + prices.floor(100));     // nothing <= 100

        // Ranges
        System.out.println("Under 999: " + prices.headSet(999));          // < 999
        System.out.println("999 and above: " + prices.tailSet(999));      // >= 999
        System.out.println("499 to 1499: " + prices.subSet(499, true, 1499, true));

        System.out.println("Descending: " + prices.descendingSet());

        System.out.println("Removed cheapest: " + prices.pollFirst());
        System.out.println("Now: " + prices);
    }
}

Output:

floor(1000)   = 999
ceiling(1000) = 1499
lower(999)    = 499
higher(999)   = 1499
floor(100)    = null
Under 999: [199, 499]
999 and above: [999, 1499, 2999]
499 to 1499: [499, 999, 1499]
Descending: [2999, 1499, 999, 499, 199]
Removed cheapest: 199
Now: [499, 999, 1499, 2999]

Here is a quick reference for these methods:

Method

Returns

floor(x)

Largest element ≤ x

ceiling(x)

Smallest element ≥ x

lower(x)

Largest element strictly < x

higher(x)

Smallest element strictly > x

headSet(x)

All elements < x

tailSet(x)

All elements ≥ x

subSet(a, true, b, true)

Elements from a to b (the booleans say whether each end is included)

pollFirst() / pollLast()

Removes and returns the smallest / largest

descendingSet()

A view of the set in reverse order

Two details to remember: these methods return null when no such element exists (like floor(100) above), and headSet(x) excludes x while tailSet(x) includes it. The shorter subSet(a, b) includes a but excludes b.

Creating a TreeMap

A TreeMap works like the HashMap you already know (put(), get(), remove(), containsKey(), entrySet()...), but its entries are always sorted by key:

import java.util.Map;
import java.util.TreeMap;

class Main {
    public static void main(String[] args) {

        TreeMap<String, Integer> marks = new TreeMap<>();

        marks.put("Vikram", 78);
        marks.put("Anita", 92);
        marks.put("Sameer", 65);
        marks.put("Deepa", 88);

        System.out.println(marks);                      // sorted by key
        System.out.println("First key: " + marks.firstKey());
        System.out.println("Last entry: " + marks.lastEntry());

        marks.put("Sameer", 70);                        // update an existing key
        marks.remove("Deepa");

        for (Map.Entry<String, Integer> entry : marks.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

Output:

{Anita=92, Deepa=88, Sameer=65, Vikram=78}
First key: Anita
Last entry: Vikram=78
Anita : 92
Sameer : 70
Vikram : 78

The names were added in a random order but always come out alphabetically. Note that the map is sorted by keys, not values: Sameer=65 comes before Vikram=78 because "S" comes before "V", not because of the marks.

TreeMap has the same "nearby" methods as TreeSet, but for keys: firstKey(), lastKey(), floorKey(), ceilingKey(), lowerKey(), higherKey(), plus versions that return the whole entry, such as firstEntry(), lastEntry(), and floorEntry().

A Real-World Use: Grade Lookup with floorEntry()

Suppose a college gives grades based on marks ranges. Instead of a long chain of if-else statements, we can store the minimum marks for each grade in a TreeMap and use floorEntry():

import java.util.TreeMap;

class Main {
    public static void main(String[] args) {

        // minimum marks : grade
        TreeMap<Integer, String> gradeCutoffs = new TreeMap<>();
        gradeCutoffs.put(0, "F");
        gradeCutoffs.put(40, "C");
        gradeCutoffs.put(60, "B");
        gradeCutoffs.put(75, "A");
        gradeCutoffs.put(90, "A+");

        int[] allMarks = {95, 75, 74, 52, 39};

        for (int marks : allMarks) {
            // floorEntry finds the highest cutoff that is <= marks
            String grade = gradeCutoffs.floorEntry(marks).getValue();
            System.out.println(marks + " : " + grade);
        }

        System.out.println(gradeCutoffs.headMap(60));        // keys < 60
        System.out.println(gradeCutoffs.tailMap(60));        // keys >= 60
        System.out.println(gradeCutoffs.descendingMap());
    }
}

Output:

95 : A+
75 : A
74 : B
52 : C
39 : F
{0=F, 40=C}
{60=B, 75=A, 90=A+}
{90=A+, 75=A, 60=B, 40=C, 0=F}

For 74 marks, floorEntry(74) finds the highest cutoff that is ≤ 74, which is 60, so the grade is B. Adding a new grade is now just one more put(). The same pattern works for tax slabs, shipping charges by weight, or discounts by order amount.

Sorting in Reverse Order

To sort from largest to smallest, pass Collections.reverseOrder() to the constructor, exactly as we did with PriorityQueue in the previous chapter:

import java.util.Collections;
import java.util.TreeMap;
import java.util.TreeSet;

class Main {
    public static void main(String[] args) {

        TreeSet<Integer> scores = new TreeSet<>(Collections.reverseOrder());
        scores.add(450);
        scores.add(980);
        scores.add(720);
        System.out.println(scores);
        System.out.println("Top score: " + scores.first());

        TreeMap<Integer, String> rankings = new TreeMap<>(Collections.reverseOrder());
        rankings.put(450, "Kavya");
        rankings.put(980, "Farhan");
        rankings.put(720, "Nikhil");
        System.out.println(rankings);
    }
}

Output:

[980, 720, 450]
Top score: 980
{980=Farhan, 720=Nikhil, 450=Kavya}

You can also keep the normal order and just look at it backwards using descendingSet() or descendingMap().

A Complete Example: Word Frequency

Let's count how many times each word appears in a sentence and print the result in alphabetical order:

import java.util.Map;
import java.util.TreeMap;

class Main {
    public static void main(String[] args) {

        String text = "the quick brown fox jumps over the lazy dog the fox";

        TreeMap<String, Integer> frequency = new TreeMap<>();

        for (String word : text.split(" ")) {
            frequency.put(word, frequency.getOrDefault(word, 0) + 1);
        }

        System.out.println("Word count (alphabetical):");
        for (Map.Entry<String, Integer> entry : frequency.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }

        System.out.println("Unique words: " + frequency.size());
        System.out.println("First word: " + frequency.firstKey());
        System.out.println("Words from 'l' to 'q': " + frequency.subMap("l", "q").keySet());
    }
}

Output:

Word count (alphabetical):
brown = 1
dog = 1
fox = 2
jumps = 1
lazy = 1
over = 1
quick = 1
the = 3
Unique words: 8
First word: brown
Words from 'l' to 'q': [lazy, over]

With a HashMap, the counts would be the same, but the words could come out in any order. By changing just the class to TreeMap, we get alphabetical order for free.

Notice the last line: "quick" is not included in subMap("l", "q"). The end key "q" is excluded, and "quick" comes after "q" in dictionary order (a longer word that starts with "q" is larger than just "q").

Using Your Own Objects

A TreeSet or TreeMap must be able to compare elements to know where they go in the tree. Numbers, Strings, characters, and dates already know how to compare themselves. Your own classes don't.

If you add a plain Student object to a TreeSet, Java throws a ClassCastException at runtime, because it doesn't know whether one student is "smaller" than another. In the upcoming Comparable & Comparator chapter, you will learn how to define that order, for example by marks or by name, and then TreeSet and TreeMap will work with your own classes too.

HashSet vs TreeSet, HashMap vs TreeMap

Feature

HashSet / HashMap

TreeSet / TreeMap

Order

No guaranteed order

Sorted (ascending by default)

add / remove / contains (or put / get)

O(1) on average

O(log n)

first, last, floor, ceiling, ranges

Not available

Available, O(log n)

null element / key

One null allowed

Not allowed with the default (natural) ordering; throws NullPointerException

Elements / keys need

equals() and hashCode()

A way to compare them

Internal structure

Hash table

Red-black tree

There is also a middle option: LinkedHashSet and LinkedHashMap keep elements in insertion order (the order you added them) with hash-table speed. Choose:

  • HashSet/HashMap when order doesn't matter (the fastest, and the most common choice).

  • LinkedHashSet/LinkedHashMap when you want the order in which items were added.

  • TreeSet/TreeMap when you want sorted order or need floor/ceiling/range queries.

Common Mistakes

  • Adding null. TreeSet.add(null) and TreeMap.put(null, value) throw NullPointerException. (A TreeMap can store null as a value, just not as a key.)

  • Expecting a TreeMap to be sorted by values. It is always sorted by keys.

  • Forgetting that floor(), ceiling(), and similar methods can return null. Calling a method on the result, or unboxing it into an int, without checking can cause a NullPointerException.

  • Using TreeSet/TreeMap when order isn't needed. You pay O(log n) instead of O(1) for nothing; use HashSet/HashMap instead.

  • Adding objects that can't be compared. Your own classes need a defined order (Comparable or Comparator), or you get a ClassCastException.

Interview Tips

  • What data structure is behind TreeMap? A red-black tree (a self-balancing binary search tree). TreeSet uses a TreeMap internally.

  • Time complexity of TreeMap get/put? O(log n).

  • When would you choose TreeMap over HashMap? When you need keys in sorted order, or need floor/ceiling/range queries.

  • How do you find the closest smaller value? floor(x) (≤ x) or lower(x) (< x) on a TreeSet, or floorKey()/lowerKey() on a TreeMap.

Practice Problems

  • Store the marks of 10 students in a TreeSet and print the top 3 using descendingSet().

  • Given a list of meeting start times, find the next meeting after a given time using ceiling() or higher().

  • Count the frequency of each character in a string and print the characters in alphabetical order with a TreeMap<Character, Integer>.

  • Build an income tax slab calculator using TreeMap.floorEntry().

The Main Idea

TreeSet and TreeMap trade a little speed for order. They keep data sorted at all times and give you powerful "nearby value" and range operations.

Need fast lookups with no order → HashSet / HashMap. Need sorted data or closest-value queries → TreeSet / TreeMap.