TreeSet in Java Explained: Sorting, Comparators & NavigableSet

TreeSet in Java explained simply — red-black tree internals, natural ordering vs Comparator, the null-handling trap, and NavigableSet methods.

1. Introduction

You’ve probably used HashSet already. Now you’re looking at TreeSet, and you expect it to work the same way. It doesn’t.

A TreeSet keeps its elements sorted. Always. There’s no sort method to call, no extra step to remember. Add elements, and TreeSet keeps them in order the whole time.

Think about a leaderboard. Scores keep coming in, and you always want them sorted. Or think about a list of timestamps you want in order, without calling Collections.sort() every single time something new arrives. That’s exactly what TreeSet is for.

In this article, we’ll open up TreeSet and see what’s really going on inside it. We’ll look at:

How TreeSet stores and sorts elements internally

Natural ordering vs a custom Comparator

A weird null-handling rule that catches people off guard

The NavigableSet methods that make TreeSet actually useful

How it stacks up against HashSet and LinkedHashSet

Common mistakes and a solid set of interview questions

If you haven’t read our HashSet and LinkedHashSet articles yet, take a quick look first. We compare TreeSet to both of them throughout this piece.

2. TreeSet at a Glance

Here’s the one-line version: TreeSet is a Set that keeps its elements sorted, all the time. Under the hood, it’s backed by a TreeMap, the same way HashSet is backed by a HashMap.

A few things make TreeSet stand out:

It sorts elements automatically, either by their natural order or by a Comparator you give it.

Basic operations run in O(log n) time. Not O(1) like HashSet.

It implements NavigableSet, which gives you methods like floor(), ceiling(), and subSet().

It won’t let you insert null once the set already has something in it. (More on that oddity later.)

Let’s see it in action before we go any deeper.

import java.util.TreeSet;
 
public class TreeSetBasics {
    public static void main(String[] args) {
        TreeSet<Integer> scores = new TreeSet<>();
        scores.add(45);
        scores.add(10);
        scores.add(99);
        scores.add(45); // duplicate, ignored
 
        System.out.println(scores); // [10, 45, 99]
    }
}

We added the numbers in a random order. The output came back sorted anyway. Nobody called a sort method here. That’s the whole point of TreeSet — sorting isn’t something you do to it. It’s something it just does, on its own, every time.

3. How TreeSet Works Internally

3.1 It’s Really Just a TreeMap in Disguise

HashSet wraps a HashMap. TreeSet wraps a TreeMap. Same trick, different Map underneath.

Every element you add becomes a key in that internal TreeMap. The value doesn’t matter — it’s just a dummy placeholder object.

// Simplified view of what TreeSet does internally
public class TreeSet<E> {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();
 
    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }
}

Since TreeMap keeps its keys sorted, TreeSet gets sorting for free. You’ve now seen this pattern three times: HashSet, LinkedHashSet, and TreeSet all lean on a Map to do the heavy lifting.

3.2 The Red-Black Tree Behind the Scenes

A TreeMap stores its entries in a red-black tree. That’s a type of self-balancing binary search tree.

Why does it need to balance itself? Picture a plain binary search tree. If you insert elements in sorted order, the tree turns lopsided. It basically becomes a linked list, and lookups slow down to O(n). A red-black tree won’t let that happen. It rebalances itself after every insert and delete, using a set of coloring and rotation rules.

You don’t need to memorize those rules to use TreeSet well. Just remember the outcome: the tree stays roughly balanced, so add, remove, and contains all run in O(log n), no matter what order you throw elements at it.

3.3 Why It’s O(log n) Instead of O(1)

HashSet is fast because it hashes an element straight to a bucket. No comparisons needed, mostly.

TreeSet can’t take that shortcut. It has to figure out where an element belongs, relative to everything else already in the tree. So every insert walks down the tree, comparing the new element to existing ones, until it finds the right spot. That walk takes O(log n) steps.

This isn’t a weakness. It’s just the price of staying sorted all the time, instead of sorting once when you actually need it.

4. Natural Ordering vs a Custom Comparator

TreeSet needs some way to compare your elements. You can give it that in two ways.

4.1 Natural Ordering with Comparable

By default, TreeSet sorts elements using their natural order. For that to work, your elements need to implement Comparable and define a compareTo() method. String and Integer already do this, so most beginner examples just work.

import java.util.TreeSet;
 
public class NaturalOrderingDemo {
    public static void main(String[] args) {
        TreeSet<String> names = new TreeSet<>();
        names.add("Charlie");
        names.add("Alice");
        names.add("Bob");
 
        System.out.println(names); // [Alice, Bob, Charlie]
    }
}

What if your class doesn’t implement Comparable? Add one element, and it works fine. Add a second one, and TreeSet throws a ClassCastException. Why does the first one succeed? There’s nothing to compare it against yet. We’ll dig into this exact detail again in the null section, because it explains a genuinely strange bug.

4.2 Custom Ordering with a Comparator

Sometimes, natural ordering isn’t what you want. Or maybe your class has no natural ordering at all. Either way, pass a Comparator to the constructor, and it takes over completely.

import java.util.Comparator;
import java.util.TreeSet;
 
public class ComparatorDemo {
    public static void main(String[] args) {
        TreeSet<String> byLength =
            new TreeSet<>(Comparator.comparingInt(String::length));
 
        byLength.add("banana");
        byLength.add("kiwi");
        byLength.add("fig");
 
        System.out.println(byLength); // [fig, kiwi, banana]
    }
}

4.3 compareTo() vs compare(): What’s Actually Different?

Both answer the same question: is this thing smaller, equal, or bigger than that thing? But they live in different places.

compareTo(other) lives inside your class. It’s part of Comparable, takes one argument, and defines one “natural” way to sort your objects.

compare(a, b) lives in a separate Comparator object. It takes two arguments, and you can write as many of these as you want, for the same class, without touching the class itself.

Here’s a simple rule of thumb. Use Comparable when there’s one obvious way to sort something, like sorting numbers by value. Reach for a Comparator when the sorting depends on context, or when you don’t own the class and can’t add compareTo to it.

4.4 Watch Out: Ordering Should Match equals()

Here’s something that trips people up a lot. In a TreeSet, two elements count as duplicates when compareTo() returns zero. Not when equals() returns true. Most of the time these two line up. But they don’t have to.

import java.util.Comparator;
import java.util.TreeSet;
 
public class ConsistencyTrap {
    public static void main(String[] args) {
        TreeSet<String> byLength =
            new TreeSet<>(Comparator.comparingInt(String::length));
 
        byLength.add("cat");
        byLength.add("dog"); // same length as "cat"
 
        System.out.println(byLength.size()); // 1, not 2!
    }
}

“cat” and “dog” clearly aren’t equal. But they’re both three letters long, so the Comparator treats them as “equal” for sorting purposes. TreeSet silently drops the second one.

Oracle calls this being “consistent with equals.” Break that rule, and your TreeSet still works, technically. But it stops behaving like a normal Set for anyone relying on equals(). Double check your comparator covers every field you actually care about.

5. The TreeSet Null Trap

Every collections interview eventually lands on null handling. TreeSet has the strangest rule of the three Set types. Most articles just say “TreeSet doesn’t allow null” and leave it there. That’s not the full picture.

5.1 An Empty TreeSet Will Actually Take a Null

If the TreeSet is completely empty, adding null works just fine.

import java.util.TreeSet;
 
public class NullOnEmptyTree {
    public static void main(String[] args) {
        TreeSet<String> tree = new TreeSet<>();
        tree.add(null); // works! tree has one element: null
 
        System.out.println(tree.size()); // 1
    }
}

5.2 Add Anything Else, and It Blows Up

Try adding a second element now, and TreeSet needs to compare it against what’s already there. Comparing against null throws a NullPointerException.

import java.util.TreeSet;
 
public class NullThenAddThrows {
    public static void main(String[] args) {
        TreeSet<String> tree = new TreeSet<>();
        tree.add(null);
 
        try {
            tree.add("hello"); // NullPointerException
        } catch (NullPointerException e) {
            System.out.println("Boom: can't compare hello to null");
        }
    }
}

5.3 Why Does This Even Happen?

It comes down to how a binary search tree inserts its very first node. When the tree is empty, there’s nothing to compare against. So the tree just plants the new element as the root, no comparison needed. Null slides right in.

Every insert after that has to walk the tree and compare the new value to existing nodes, to figure out whether it goes left or right. If either side of that comparison is null, boom — NullPointerException. You can’t call a method on null.

Here’s the practical takeaway: don’t build anything around this quirk. Treat TreeSet as “no nulls, period” in real code. Filter nulls out before they ever reach it. Knowing the mechanics is great for an interview. Relying on a one-element edge case in production is a bug waiting to happen.

6. NavigableSet: What You Actually Get With TreeSet

This is where TreeSet really earns its keep. Since everything stays sorted, TreeSet can answer questions a HashSet just can’t.

6.1 The Basics: first() and last()

import java.util.TreeSet;
 
public class FirstLastDemo {
    public static void main(String[] args) {
        TreeSet<Integer> nums = new TreeSet<>();
        nums.add(30);
        nums.add(10);
        nums.add(50);
        nums.add(20);
 
        System.out.println(nums.first()); // 10
        System.out.println(nums.last());  // 50
    }
}

6.2 Finding Neighbours: floor, ceiling, lower, higher

These four methods find an element’s neighbours without you writing a single loop.

floor(e) — the biggest element that’s less than or equal to e

ceiling(e) — the smallest element that’s greater than or equal to e

lower(e) — the biggest element strictly less than e

higher(e) — the smallest element strictly greater than e

import java.util.TreeSet;
 
public class NeighbourDemo {
    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(nums.floor(25));   // 20
        System.out.println(nums.ceiling(25)); // 30
        System.out.println(nums.lower(20));   // 10 (strictly less)
        System.out.println(nums.higher(20));  // 30 (strictly greater)
    }
}

All four run in O(log n), same as a regular add or contains. HashSet simply can’t do this.

6.3 Slicing Ranges: headSet, tailSet, subSet

These three return a *view* of part of the set, not a fresh copy. Change the view, and the original set changes too.

import java.util.TreeSet;
 
public class RangeViewDemo {
    public static void main(String[] args) {
        TreeSet<Integer> nums = new TreeSet<>();
        for (int n : new int[]{10, 20, 30, 40, 50}) nums.add(n);
 
        System.out.println(nums.headSet(30));    // [10, 20]
        System.out.println(nums.tailSet(30));    // [30, 40, 50]
        System.out.println(nums.subSet(20, 40)); // [20, 30]
    }
}

Notice something? headSet(30) leaves 30 out. tailSet(30) includes it. And subSet(20, 40) includes the start but skips the end. This “start included, end excluded” pattern shows up all over Java. Worth memorizing instead of re-checking every time.

6.4 pollFirst() and pollLast()

These grab and remove the smallest or largest element in one step. Handy for anything shaped like a priority queue.

import java.util.TreeSet;
 
public class PollDemo {
    public static void main(String[] args) {
        TreeSet<Integer> queue = new TreeSet<>();
        queue.add(5);
        queue.add(1);
        queue.add(9);
 
        System.out.println(queue.pollFirst()); // 1, removed
        System.out.println(queue.pollLast());  // 9, removed
        System.out.println(queue);             // [5]
    }
}

6.5 Need It Backwards? Try descendingSet()

Want the set in reverse order without rebuilding anything? descendingSet() gives you a reversed view, backed by the same underlying data.

import java.util.TreeSet;
 
public class DescendingDemo {
    public static void main(String[] args) {
        TreeSet<Integer> nums = new TreeSet<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
 
        System.out.println(nums.descendingSet()); // [3, 2, 1]
    }
}

7. TreeSet vs HashSet vs LinkedHashSet

You’ve now met all three Set types in this series. Here’s how they line up, side by side.

7.1 So Which One Should You Actually Use?

Pick HashSet when you just need uniqueness and speed, and you don’t care about order at all. Make this your default.

Pick LinkedHashSet when you need uniqueness but also want elements to come back in the order you added them. Think of deduplicating a list of tags while keeping the order the user typed them in.

Pick TreeSet when you need the data sorted at all times, or you need to ask things like “what comes right after this value?”

Quick shortcut: only reach for TreeSet if you’d otherwise be calling Collections.sort() over and over. Sorting once and reading many times? A plain ArrayList with one sort call might be simpler.

8. Real-World Places You’d Actually Use This

Theory sticks better when it’s tied to something real. Here are three spots where TreeSet is the obvious pick.

8.1 A Live Leaderboard

Say you’re building a game. Scores need to stay unique, sorted, and update instantly as new ones come in. You also want to answer “what score sits just above 8,200?” without scanning the whole list. TreeSet does all of that out of the box. Adding a score keeps everything sorted automatically, and ceiling() answers the neighbour question fast.

8.2 Scheduling and Time Slots

Picture a calendar app storing unique appointment times. You’ll often need the next free slot after a given time, or every appointment between 9 AM and 5 PM. That’s exactly what floor(), ceiling(), and subSet() are built for. No manual loops required.

8.3 Dedupe and Sort in One Shot

Say you’re reading a huge log file and want the distinct error codes, sorted, for a report. Dump each code into a TreeSet as you read the file. You get deduplication and sorting together, instead of three separate steps: collect, dedupe, then sort.

9. Common Mistakes and Pitfalls

9.1 Mixing In Non-Comparable Types

Add an object without Comparable, and without a Comparator, and it compiles just fine. Add a second one, though, and you’ll get a ClassCastException at runtime.

class Item {
    String name;
    Item(String name) { this.name = name; }
}
 
// TreeSet<Item> items = new TreeSet<>();
// items.add(new Item("A"));
// items.add(new Item("B")); // ClassCastException at runtime

Always give TreeSet a Comparator for types that aren’t naturally comparable.

9.2 Changing an Element After It’s Already Inserted

Change a field that’s used in compareTo() after the object is already sitting in the tree, and things get messy. The tree no longer knows where that object actually belongs. Lookups and future inserts can misbehave, and you might not catch it for a while. Treat your set elements as immutable. Same advice we gave for HashSet.

9.3 Assuming equals() and compareTo() Always Match Up

We covered this in section 4.4, but it’s worth repeating: a Comparator that returns 0 for genuinely different objects will quietly merge them into one entry. Make sure your comparison logic actually covers every field you care about.

9.4 Forgetting That TreeSet Basically Rejects Null

You already know the real rule from section 5. Don’t write logic that leans on the empty-set exception. Don’t assume TreeSet is as forgiving as HashSet about null. Filter nulls out before they get anywhere near a TreeSet.

9.5 Expecting O(1) Speed

Coming from HashSet, it’s easy to forget TreeSet costs O(log n) for everything, not O(1). Most apps won’t notice the difference. But if you’re churning through millions of elements in a hot loop, that gap adds up fast. Profile it before you assume TreeSet is “fast enough.”

10. Interview Questions on Set

11. Conclusion

TreeSet gives up HashSet’s raw speed in exchange for something HashSet can never do: keeping everything sorted, automatically, no matter how much you insert or remove. That trade makes total sense once your problem involves order — leaderboards, range queries, or anything where “what’s the next value above this one” actually matters.

Across this series, the three Set types map onto three different jobs. HashSet is your default when you just need uniqueness and speed. LinkedHashSet keeps insertion order for almost no extra cost. TreeSet keeps everything sorted and unlocks NavigableSet’s range and neighbour queries, at the cost of O(log n) speed and a much stricter relationship with null.

Know all three well enough to pick the right one without thinking twice, and you’ll be ahead of most developers who’ve only ever reached for HashSet by default.

Further Reading

Oracle Java Docs – TreeSet: https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html

Oracle Java Docs – NavigableSet: https://docs.oracle.com/javase/8/docs/api/java/util/NavigableSet.html

Oracle Java Docs – TreeMap: https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

Oracle Java Docs – Comparable: https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html

Oracle Java Docs – Comparator: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html