Java TreeSet class extends AbstractSet and implements NavigableSet
interface. It is very similar to HashSet class, except it stores the element in sorted order.
The sort order is either natural order or by a Comparator provided at treeset creation time, depending on which constructor is used.
Table of Contents 1. TreeSet Hierarchy 2. TreeSet Features 3. TreeSet Constructors 4. TreeSet Methods 5. TreeSet Example 6. TreeSet Usecases 7. TreeSet Performance 8. Conclusion
1. TreeSet Hierarchy
The TreeSet class extends AbstractSet
class and implements NavigableSet
interface. The NavigableSet interface extends SortedSet
in hierarchical order.
class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable { //implementation }

2. TreeSet Features
- It extends
AbstractSet
class which extendsAbstractCollection
class. - It implements
NavigableSet
interface which extendsSortedSet
interface. - Duplicate values are not allowed in TreeSet.
- NULL is not allowed in TreeSet.
- It is an ordered collection which store the elements in sorted order.
- Like HashSet, this class offers constant time performance for the basic operations(add, remove, contains and size).
- TreeSet does not allow to insert heterogeneous objects because it must compare objects to determine sort order.
- TreeSet is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
- Use Collections.synchronizedSortedSet(new TreeSet()) method to get the synchronized TreeSet.
- The iterators returned by this class’s iterator method are fail-fast and may throw
ConcurrentModificationException
if the set is modified at any time after the iterator is created, in any way except through the iterator’s ownremove()
method. - TreeSet also implements Searlizable and Cloneable interfaces.
3. TreeSet Constructors
The TreeSet has four possible constructors:
- TreeSet(): creates a new, empty tree set, sorted according to the natural ordering of its elements.
- TreeSet(Comparator c): creates a new, empty tree set, sorted according to the specified comparator.
- TreeSet(SortedSet s): creates a new tree set containing the same elements and using the same ordering as the specified sorted set.
- TreeSet(Collection c): creates a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
4. TreeSet Methods
- boolean add(E e) : adds the specified element to the Set if not already present.
- Comparator comparator() : returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
- Object first() : returns the first (lowest) element currently in this set.
- Object last() : returns the last (greatest) element currently in this set.
- void clear() : removes all the elements from the TreeSet.
- boolean contains(Object o) : returns
true
if the TreeSet contains the specified element, othrwisefalse
. - boolean isEmpty() : returns
true
if TreeSet contains no element, otherwisefalse
. - int size() : returns the number of elements in the TreeSet.
- Iterator<E> iterator() : returns an iterator over the elements in this set in ascending order.
- Iterator<E> descendingIterator() : returns an iterator over the elements in this set in descending order.
- NavigableSet<E> descendingSet() : returns a reverse order view of the elements contained in this set.
- boolean remove(Object o) : removes the specified element from the TreeSet if it is present and return
true
, else returnsfalse
. - Object clone() : returns a shallow copy of the TreeSet.
- Spliterator<E> spliterator() : creates a late-binding and fail-fast Spliterator over the elements in this TreeSet. It has same ordering as treeset provides.
5. TreeSet Example
5.1. TreeSet add, remove, iterator example
//1. Create TreeSet TreeSet<String> TreeSet = new TreeSet<>(); //2. Add elements to TreeSet TreeSet.add("A"); TreeSet.add("B"); TreeSet.add("C"); TreeSet.add("D"); TreeSet.add("E"); System.out.println(TreeSet); //3. Check if element exists boolean found = TreeSet.contains("A"); //true System.out.println(found); //4. Remove an element TreeSet.remove("D"); //5. Iterate over values Iterator<String> itr = TreeSet.iterator(); while(itr.hasNext()) { String value = itr.next(); System.out.println("Value: " + value); }
Program Output.
[A, B, C, D, E] true Value: A Value: B Value: C Value: E
5.2. Convert TreeSet to Array Example
Java example to convert a TreeSet to array using toArrray() method.
TreeSet<String> TreeSet = new TreeSet<>(); TreeSet.add("A"); TreeSet.add("B"); TreeSet.add("C"); TreeSet.add("D"); TreeSet.add("E"); String[] values = new String[TreeSet.size()]; TreeSet.toArray(values); System.out.println(Arrays.toString(values));
Program Output.
[A, B, C, D, E]
5.3. Convert TreeSet to ArrayList Example
Java example to convert a TreeSet to arraylist using Java 8 stream API.
TreeSet<String> TreeSet = new TreeSet<>(); TreeSet.add("A"); TreeSet.add("B"); TreeSet.add("C"); TreeSet.add("D"); TreeSet.add("E"); List<String> valuesList = TreeSet.stream().collect(Collectors.toList()); System.out.println(valuesList);
Program Output.
[A, B, C, D, E]
6. TreeSet Usecases
TreeSet is very much like HashSet (unique elements) and provides predictable iteration order (sorted). Sorted order can overridden using custom comparator.
TreeSet uses Red-Black tree under the hood. So the set could be thought as a dynamic search tree. When you need a structure which is operated read/write frequently and also should keep order, the TreeSet is a good choice.
If you want to keep a collection sorted and you are mostly appending the elements, TreeSet with a Comparator is your best bet.
7. TreeSet Performance
- TreeSet provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
- The operations like iterating the elements in sorted order takes O(n) time.
8. Conclusion
From above discussion, it is evident that TreeSet is very useful collection class in cases where we want to handle duplicate records in sorted manner. It also provide predictable performance for basic operations.
If sorted order of elements is not needed then it is recommended to use the lighter-weight HashSet and HashMap instead.
Drop me your questions related to TreeSet in Java in comments.
Happy Learning !!
Reference:
Comments