Java TreeSet

In the last lesson you learned about Java LinkedHashSet, which stores unique items but in no particular order. Sometimes you want the same uniqueness and automatic sorting, like a leaderboard of unique scores. Java has a set for exactly that: the TreeSet. It keeps unique items in sorted order, all on its own.

🤔 Why a TreeSet?

Picture a wall noticeboard where people pin their names. With a HashSet, the pins land wherever there is space. The names are all there, and none of them repeats, but the wall looks like a mess. Every time you want to read them in alphabetical order, you have to take them all down, sort them by hand, and pin them back up.

A TreeSet is a smarter noticeboard. The moment you hand it a new name, it walks along the wall and slides the pin into the exact right spot so the whole board stays in order. You never sort anything yourself. The board is correct the instant each name goes up.

The problem a TreeSet solves:

• A HashSet gives you uniqueness, but prints items in a random order.
• To get sorted output, you must copy the items to a list and sort them every time.
• That repeated copy-and-sort wastes your effort and the program’s time.

A TreeSet removes all of that. It keeps items sorted at all times, so reading them in order is free. The small price: adding is a little slower, because the set sorts for you up front.

🧩 What is a TreeSet?

A TreeSet is a set that stores unique items in sorted order. The extra promise on top of uniqueness is the ordering.

• It keeps items in natural sorted order: numbers ascending, Strings A to Z.
• It still ignores duplicates, like every other set.
• It offers navigation methods to find the smallest, largest, or nearest items.

Think of it as the “ordered set”. Reach for it when you need unique values kept sorted with no extra work.

How it stays sorted: the balanced tree

A TreeSet is backed by a red-black tree, a kind of self-balancing tree.

• A tree stores items in a branching shape, smaller items on one side, larger on the other.
• “Self-balancing” means the tree reshapes itself so no branch grows too long.
• A short balanced tree finds an item’s spot in O(log n) time, not O(n).
• So even with a million items, an add or lookup takes about twenty steps, not a million.
• That is slower than a HashSet’s O(1), but it is the price for staying ordered.

💡 Automatic sorting in action

Let’s add numbers in a jumbled order and watch the TreeSet sort them. We never call a sort method.

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> scores = new TreeSet<>();
        scores.add(50);
        scores.add(10);
        scores.add(30);
        scores.add(10);   // ❌ duplicate, ignored

        System.out.println(scores);   // ✅ always sorted
    }
}

What happened:

• We added 50, then 10, then 30, in that messy order.
• The second 10 was a duplicate, so the set dropped it.
• Printing shows the items smallest first, with no sort call from us.
• Strings behave the same way, sorted alphabetically.

[10, 30, 50]

🏆 Worked example: a unique sorted leaderboard

Imagine a game where players submit scores. We want the distinct scores, always sorted lowest to highest, so we can show a clean leaderboard and pick the top score.

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> leaderboard = new TreeSet<>();

        leaderboard.add(420);
        leaderboard.add(150);
        leaderboard.add(990);
        leaderboard.add(420);   // ❌ Alex tied an existing score, ignored
        leaderboard.add(310);

        System.out.println("All scores: " + leaderboard);
        System.out.println("Lowest score: " + leaderboard.first());
        System.out.println("Top score: " + leaderboard.last());
    }
}

What happened:

• We submit five scores, but 420 repeats.
• The set keeps one 420 and slots each score into sorted position as it arrives.
• first() returns the smallest score and last() the largest, instantly.
• We never sorted or looped to find the min or max. The set already knew the order.

All scores: [150, 310, 420, 990]
Lowest score: 150
Top score: 990

🧭 Navigation methods

Because a TreeSet is always sorted, it can answer order questions a HashSet cannot. These methods make it a NavigableSet, the formal name for “a set you can move around inside by order”.

• first() and last() give the smallest and largest items.
• higher(x) gives the smallest item strictly above x; lower(x) the largest strictly below x.
• ceiling(x) gives the smallest item at or above x; floor(x) the largest at or below x.
• headSet(x) is the part below x; tailSet(x) is from x upward; subSet(a, b) is the slice between.
• higher/lower are strict, so they never return x itself. ceiling/floor include x if present.

Let’s see all of this run.

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> nums = new TreeSet<>();
        nums.add(10);
        nums.add(20);
        nums.add(30);
        nums.add(40);

        System.out.println("First: " + nums.first());            // smallest
        System.out.println("Last: " + nums.last());              // largest
        System.out.println("Higher than 20: " + nums.higher(20)); // strictly above 20
        System.out.println("Ceiling of 20: " + nums.ceiling(20)); // 20 itself counts
        System.out.println("Floor of 25: " + nums.floor(25));     // largest <= 25
        System.out.println("Below 30: " + nums.headSet(30));      // slice under 30
    }
}

Walking through the calls:

• first() and last() give the two ends, 10 and 40.
• higher(20) skips 20 and returns the next value up, 30.
• ceiling(20) lets 20 count, so it returns 20.
• floor(25) finds the largest value not over 25, which is 20.
• headSet(30) returns every item below 30 as a sorted view.
• A HashSet can do none of these. It has no order to navigate.

First: 10
Last: 40
Higher than 20: 30
Ceiling of 20: 20
Floor of 25: 20
Below 30: [10, 20]

🔧 How does it decide the order?

A TreeSet must compare items to know which comes first. It learns the order in one of two ways:

• Natural ordering. The item’s class compares itself by implementing the Comparable interface. Built-in types like Integer, Double, and String already do this, so they just work.
• A custom Comparator. You hand a comparison rule to the constructor. The set uses your rule instead.
• Store your own class with neither, and the set cannot compare your objects. It throws a ClassCastException on the second add. More on that in the mistakes section.

Worked example: a custom Comparator for reverse order

Suppose we want the same unique scores, but sorted highest to lowest. We pass a Comparator to the constructor that flips the comparison. The easy way is Comparator.reverseOrder().

import java.util.TreeSet;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        // ✅ tell the TreeSet to sort high-to-low
        TreeSet<Integer> ranking = new TreeSet<>(Comparator.reverseOrder());

        ranking.add(420);
        ranking.add(150);
        ranking.add(990);
        ranking.add(310);

        System.out.println("Ranked: " + ranking);
        System.out.println("Winner: " + ranking.first()); // first is now the largest
    }
}

The key line is the constructor:

• We passed Comparator.reverseOrder() instead of leaving it empty.
• The set now treats “bigger” as “comes first”, so it sorts descending.
• With the order flipped, first() returns the largest score, the winner.
• You decide the ordering rule, and the set obeys it for every item.

Ranked: [990, 420, 310, 150]
Winner: 990

⚖️ TreeSet vs HashSet vs LinkedHashSet

All three keep items unique. The difference is the order they keep and how fast they work.

Which one to pick:

• HashSet when you only need uniqueness and the fastest speed.
• LinkedHashSet when you want uniqueness plus items back in the order you added them.
• TreeSet when you need sorted items or the navigation methods.

⚠️ Common Mistakes

A few TreeSet slip-ups trip people up again and again.

Storing a custom class with no ordering rule

No Comparable and no Comparator means the set cannot compare your items. It crashes with a ClassCastException on the second add.

// ❌ Wrong: Player does not implement Comparable, and no Comparator is given
class Player {
    String name;
    Player(String name) { this.name = name; }
}

TreeSet<Player> players = new TreeSet<>();
players.add(new Player("Alex"));
players.add(new Player("Riya")); // ❌ throws ClassCastException here

Exception in thread "main" java.lang.ClassCastException:
class Player cannot be cast to class java.lang.Comparable

Fix it by passing a Comparator to the constructor.

import java.util.TreeSet;
import java.util.Comparator;

class Player {
    String name;
    Player(String name) { this.name = name; }
}

// ✅ Right: tell the TreeSet to order players by name
TreeSet<Player> players = new TreeSet<>(Comparator.comparing(p -> p.name));
players.add(new Player("Alex"));
players.add(new Player("Riya")); // ✅ works, sorted by name

Expecting items in the order you added them

A TreeSet sorts. It does not remember insertion order.

TreeSet<String> names = new TreeSet<>();
names.add("Riya");
names.add("Alex");
// ❌ Wrong assumption: this prints [Riya, Alex]
// ✅ Reality: it prints [Alex, Riya], sorted alphabetically
System.out.println(names);

If you truly want insertion order, use a LinkedHashSet instead.

Adding null

A TreeSet must compare every item, and it cannot compare null, so it throws a NullPointerException. (A HashSet allows one null.)

TreeSet<String> names = new TreeSet<>();
names.add("Alex");
names.add(null);   // ❌ throws NullPointerException

Just never put null into a TreeSet.

Expecting index access

Like all sets, a TreeSet has no get(index) method. There is no positional lookup.

// ❌ Wrong: TreeSet has no get(0)
// String top = scores.get(0);

// ✅ Right: use navigation methods or a loop
String top = scores.first();

✅ Best Practices

Habits that keep your TreeSet code clean:

• Use it for unique, sorted data. Leaderboards, distinct sorted names, ordered numbers.
• Lean on the navigation methods. first, last, floor, ceiling beat looping by hand.
• Handle null at the edges. higher, lower, floor, ceiling return null when nothing is there.
• Prefer HashSet when order does not matter. Do not pay the O(log n) cost for nothing.
• Give custom classes an ordering rule. Implement Comparable, or pass a Comparator.
• Never store null. It cannot compare null, so it throws.

🧩 What You’ve Learned

Nicely done. Let’s recap TreeSet.

• ✅ A TreeSet stores unique items in sorted order, automatically.
• ✅ It is backed by a balanced red-black tree, so add and lookup are O(log n), slower than a HashSet but always ordered.
• ✅ It offers navigation methods like first, last, higher, lower, floor, ceiling, headSet, tailSet, and subSet.
• ✅ Order comes from natural ordering (Comparable) or a Comparator you pass to the constructor.
• ✅ A custom class with no ordering rule throws a ClassCastException, and null is not allowed.
• ✅ Compared to HashSet and LinkedHashSet, TreeSet is the one that keeps everything sorted and supports navigation.

🚀 What’s Next?

Sets store single items. But a huge amount of real data comes in pairs: a name and a phone number, a product and its price. For key-to-value data, Java has the Map. Let’s learn the interface behind all of them.

Java Map Interface