TreeSet is the Set implementation that keeps its elements in sorted order. Where HashSet provides unordered membership and LinkedHashSet remembers insertion order, TreeSet does something different: it actively arranges elements by value, so iterating the set walks from smallest to largest. This lesson covers how the ordering works, the navigation and range methods that come with it, the cost of those guarantees, and the rules around null.

The defining property of TreeSet is that iteration order is always sorted, regardless of insertion order. For numbers, that means ascending. For strings, that means lexicographic order (which is roughly alphabetic for ASCII letters).

The IDs print in ascending order even though they were inserted in a scrambled sequence. The duplicate 101 was rejected, just like with any other Set. The size is 4, not 5.

Strings sort the same way without any extra work:

The order is the natural ordering for the element type. For Integer, that's numeric ascending. For String, it's the compareTo definition built into String, which compares character by character using Unicode values. For this lesson, treat natural ordering as a property that Integer, String, Double, and most other standard types already supply.

For a different order, pass a Comparator to the constructor. Here's a TreeSet of product names sorted by length, shortest first:

The Comparator tells the set to use string length as the ordering key. Pen and Mug both have length 3, but Pen was inserted first and the comparator never reports them as equal-by-length-but-different-strings cleanly, so the one with the smaller character ordering ends up first by tie-break. The takeaway is that TreeSet accepts a Comparator whenever a non-default order is needed.

Internally, a TreeSet is backed by a TreeMap, which itself is a Red-Black tree. The internals are a topic for a deeper data-structures chapter, but the shape is simple: a self-balancing binary search tree. Every element is a node, smaller values live to the left of a node, and larger values live to the right. The tree rebalances after each insertion or removal so that the longest path from root to leaf stays close to log n.

Consider a TreeSet of unique scores from a leaderboard, inserted in this order: 42, 17, 68, 9, 25. After all five insertions, the tree might look like this:

Reading the tree in left-root-right order (an in-order traversal) gives 9, 17, 25, 42, 68, which is the sorted sequence TreeSet returns during iteration. The tree structure is built for fast lookup, and the in-order traversal produces sorted output automatically.

The practical consequence is the cost model. add, remove, and contains each cost O(log n), because they walk one path from the root to a leaf. Compare that with HashSet, where the same operations are O(1) on average. TreeSet trades some lookup speed for ordering and range queries.

TreeSet.contains(x) is O(log n), not O(1). For a million-element set, that's about 20 comparisons per lookup. Without ordering needs, prefer HashSet.

The data structures course covers Red-Black trees in depth. What matters for using TreeSet is the cost model and the fact that the order it produces matches a sorted in-order walk.

TreeSet implements NavigableSet, which extends SortedSet. Together, those interfaces provide methods for ordering-aware questions about the set. Two are obvious: first() returns the smallest element, and last() returns the largest.

Both calls are O(log n), because the tree finds the leftmost or rightmost node by walking down one side.

The richer methods are ceiling, floor, higher, and lower. They answer questions like "what's the smallest element at least as large as this target?" and are useful for finding the nearest match in a sorted collection.

The difference between ceiling and higher is the equal case. ceiling(42) returns 42 if 42 is in the set, while higher(42) skips past it and returns the next larger element. The same distinction applies to floor and lower.

Here's a worked example. A storefront has a list of approved price points and wants to round a user's typed price to the nearest approved value:

floor(25.00) returns 19.99, the largest approved price that doesn't exceed the target. ceiling(25.00) returns 29.99, the smallest approved price that meets or exceeds the target. Either one might be the right answer depending on whether the round is to the cheaper or more expensive nearby price.

A small diagram showing what each navigation method picks for target = 25.00:

When the target is exactly equal to a value in the set, floor and ceiling both return that value, while lower and higher skip past it. With target = 19.99, floor returns 19.99 and lower returns 9.99.

If no element satisfies the query, the method returns null. floor(5.00) on the set above returns null, because every approved price exceeds 5.

The navigation methods return single elements. The range methods return views of multiple elements. They're useful for queries like "everything between $20 and $50" without writing a loop and a manual filter.

The defaults are half-open: the lower bound is inclusive, the upper bound is exclusive. There are overloaded versions on NavigableSet that set inclusivity explicitly, but the default versions match the common case for range scans.

A storefront wants to show all products in a given price range:

headSet(20.00) includes everything below 20.00. The price 19.99 makes it in; 20.00 would be excluded if it existed. tailSet(30.00) starts at 30.00 inclusive. Since 30.00 isn't in the set, the result starts at the next available value, 45.00. subSet(20.00, 50.00) is the intersection: greater than or equal to 20.00, strictly less than 50.00.

The result of these range methods is a view, not a copy. That has two consequences. First, changes to the underlying TreeSet show up in the view, and changes to the view (where the view supports them) show up in the underlying set. Second, the view doesn't cost O(n) memory to construct, which makes range scans cheap even on a large set.

The tailSet view was created once, but adding 1099 to the underlying set made it visible through the view immediately. That's because recent doesn't hold its own copy of the elements. It holds a reference to the parent set plus the range boundary, and walks the parent on demand.

For an actual snapshot that won't change, copy the view into a new collection: new TreeSet<>(orderIds.tailSet(1040)).

TreeSet needs to compare every element it stores, because comparison is what decides where the element goes in the tree. Comparing null against any non-null value isn't defined, so a TreeSet that uses natural ordering throws NullPointerException the moment null is added.

The first add works because there's nothing yet to compare "Books" against. The second one fails because Java needs to call null.compareTo("Books") to decide where null belongs, and null can't be dereferenced.

There's one case where TreeSet accepts null: a Comparator that explicitly defines how null compares against other values. That's uncommon and usually a sign of a deeper data model problem. A better pattern is to validate inputs before they reach the set.

This is a behavior difference to file away. HashSet and LinkedHashSet both accept a single null element, because they use hashCode and equals rather than compareTo. TreeSet rejects null because comparison is at the core of how it works.

A TreeSet calls compareTo on every insert and every lookup, so an expensive comparator runs many times. Cache anything heavy that would otherwise be computed repeatedly during a comparison.

Use TreeSet when sorted iteration or range queries are part of the requirements. For uniqueness and fast membership checks alone, HashSet is faster and uses less memory. For insertion-order iteration, LinkedHashSet is a better match. The table below summarizes the trade-offs across the three Set implementations from this section.

Use TreeSet when at least one of these is true:

A small, end-to-end example pulls these together. A storefront keeps the set of unique scores from a leaderboard. It needs to show the leaderboard sorted, find the top score, and report how many scores fall within a given range:

Every operation here uses something TreeSet provides natively: sorted iteration, first/last, a range view sized at O(1) per element walked, and a navigation lookup. Building the same report on a HashSet would mean sorting on demand and writing a manual loop for the range, both of which cost more than the equivalent TreeSet calls.

The same principle applies to most container choices in Java: pick the implementation whose guarantees match the workload. TreeSet pays for sorted ordering and range queries with a step up in per-operation cost. When those features are used, the cost is well spent. Otherwise, a different Set is a better fit.