The java.util.TreeSet is a NavigableSet implementation based on a TreeMap. It ensures that the set is always in ascending order, according to the natural ordering of its elements or by a Comparator provided at creation time.
While HashSet uses buckets and hash codes, TreeSet uses a Self-Balancing Binary Search Tree known as a Red-Black Tree. This ensures that the tree never becomes "lopsided," keeping the height of the tree minimal for faster searching.
Every time you add an element, Java compares it to the existing nodes. If it's smaller, it goes left; if larger, it goes right. It then "re-balances" itself to stay efficient.
Search, Add, and Remove operations take O(log n) time. While slower than HashSet's O(1), it stays consistently fast even as the dataset grows into the millions.
Because the data is sorted, TreeSet provides powerful "Navigation" methods that are impossible in a HashSet. You can "peek" at neighbors or find the closest match to a value.
| Method | Functionality |
|---|---|
first() / last() |
Returns the lowest and highest elements. |
lower(e) / higher(e) |
Returns the element strictly less than or greater than 'e'. |
floor(e) / ceiling(e) |
Returns the element less than/equal to or greater than/equal to 'e'. |
pollFirst() / pollLast() |
Retrieves and removes the first/last element (Great for priority tasks). |
A TreeSet cannot function if it doesn't know how to compare two objects. If you try to add a custom object that doesn't implement the Comparable interface, Java will throw a ClassCastException.
HashSet, a TreeSet does not use hashCode() or equals() to detect duplicates. It uses the compareTo() (or compare()) method. If compareTo returns 0, the TreeSet considers the elements identical and won't add the new one.
You should only use TreeSet when the order is a requirement. If you just need uniqueness, HashSet is nearly 5-10 times faster.
This example shows how a TreeSet can be used to track stock prices and quickly find "the highest price below $100."
A TreeSet is memory-intensive. Every element is wrapped in a TreeMap.Entry object, which contains four references (left, right, parent, and value) and a boolean for the color (Red or Black). If memory is a tight constraint, consider using a sorted array or ArrayList and Collections.sort() only when needed.
A TreeSet does not allow null elements. Because it needs to call compareTo() on every element to find its position, adding a null will result in a NullPointerException immediately. This is a major difference compared to HashSet.
Q: How does TreeSet handle duplicates?
A: It uses the return value of compare() or compareTo(). If the method returns 0, the element is considered a duplicate and is discarded.
Q: Is TreeSet thread-safe?
A: No. Like most of the Collections Framework, it is not synchronized. For thread-safety, use Collections.synchronizedSortedSet(new TreeSet(...)) or ConcurrentSkipListSet.
Q: What is the time complexity of the contains() method in TreeSet?
A: It is $O(\log n)$ because it follows a path from the root to a leaf in a balanced tree.
The TreeSet is the professional’s choice for maintaining sorted, unique datasets. While it carries more memory and performance overhead than a HashSet, the added power of the NavigableSet interface makes it indispensable for applications like scheduling, ranking systems, and range-based data analysis. Use it when order isn't just a preference, but a requirement.