TreeSet in Java
Introduction
While HashSet (unordered) and LinkedHashSet (insertion-ordered) offer fast performance, they do not sort elements.
To store elements in sorted order, Java provides TreeSet. A TreeSet implements the NavigableSet interface (which extends SortedMap/SortedSet) and is backed by a TreeMap instance. It automatically sorts elements as they are inserted.
Why TreeSet?
If you are building an application where elements must remain unique and be sorted automatically—such as a High Score Leaderboard, a Case-Insensitive Glossary, or a Price Catalog—TreeSet is the ideal collection:
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Set<Integer> scores = new TreeSet<>();
scores.add(95);
scores.add(80);
scores.add(90);
System.out.println(scores); // Output is sorted automatically: [80, 90, 95]
}
}
Features of TreeSet
- No Duplicates: Duplicate elements are rejected automatically.
- Auto-Sorted: Elements are sorted in ascending natural order (or custom order using a
Comparator). - No Null Elements: Does not allow null elements (throws
NullPointerExceptionbecause it must compare elements to sort them). - Guaranteed Complexity: backed by a Red-Black Tree, basic operations (
add,remove,contains) run inO(log N)logarithmic time.
Creating a TreeSet
Basic Initialization (Natural Order)
Initialization with Custom Comparator (Descending Order)
import java.util.Collections;
import java.util.SortedSet;
import java.util.TreeSet;
SortedSet<Integer> descendingScores = new TreeSet<>(Collections.reverseOrder());
Common and Navigable Methods
Since TreeSet implements NavigableSet, it provides several utility methods for range queries:
| Method | Description | Time Complexity |
|---|---|---|
first() | Returns the lowest element currently in the set. | O(1) or O(log N) |
last() | Returns the highest element currently in the set. | O(log N) |
floor(E e) | Returns the greatest element \(\le\) the target. | O(log N) |
ceiling(E e) | Returns the least element \(\ge\) the target. | O(log N) |
subSet(from, to) | Returns a view of the portion of the set between the bounds. | O(log N) |
Iterating Through a TreeSet
Iterating through a TreeSet returns elements in ascending sorted order:
Complete Programs
Example: Sorted Registry and Range Slicing
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Integer> ages = new TreeSet<>();
ages.add(25);
ages.add(40);
ages.add(18);
ages.add(30);
// 1. Sorted output check
System.out.println("Sorted Ages: " + ages); // [18, 25, 30, 40]
// 2. Navigable methods
System.out.println("Lowest Age: " + ages.first()); // 18
System.out.println("Highest Age: " + ages.last()); // 40
System.out.println("Age floor for 29: " + ages.floor(29)); // 25 (nearest low)
System.out.println("Age ceiling for 29: " + ages.ceiling(29)); // 30 (nearest high)
// 3. Sub-Set range slicing
System.out.println("Ages between 20 and 35: " + ages.subSet(20, 35)); // [25, 30]
}
}
Best Practices
- Override
Comparable: Any custom class stored in aTreeSet(e.g.,Student) must implement theComparableinterface (or you must provide an externalComparatorto the constructor). If you do not, inserting the object will throw aClassCastException. - Prefer HashSet by default: Use
HashSetinstead ofTreeSetunless sorting is required, asHashSethas faster operations (O(1)vsO(log N)).
Common Mistakes
- Adding Nulls: Inserting a
nullvalue into aTreeSetthrows aNullPointerExceptionbecausenullcannot be compared to other elements. - Inconsistent Comparator: Ensure your custom
ComparatororcompareTo()implementation is consistent withequals(). Ifcompare(a, b) == 0buta.equals(b) == false, the set will rejectbas a duplicate, violating the set interface contract.
Key Takeaways
TreeSetkeeps elements sorted automatically.- backed by a Red-Black Tree, providing guaranteed
O(log N)performance. - Does not permit null elements.
Back to Sets Home: Sets Index