o7planning

Java TreeSet Tutorial with Examples

  1. TreeSet
  2. How does TreeSet store data?
  3. Examples
  4. TreeSet with null element ​​​​​​

1. TreeSet

In this article we will explore TreeSet class, which is an implementation of NavigableSet Interface and resides in Java Collection Framework.
public class TreeSet<E> extends AbstractSet<E>
                    implements NavigableSet<E>, Cloneable, java.io.Serializable
Basically, in this article we will learn the characteristics of TreeSet and how it stores elements. You should learn the basics of Set before continuing with this article.
Characteristics of TreeSet:
Set<E>
SortedSet<E>
NavigableSet<E>
TreeSet<E>
Duplicate elements are not allowed. If you intentionally add a duplicate element, this action will be ignored.
At most one null element is allowed.
At most one null element is allowed and null is only allowed if a suitable Comparator is provided.
The order of elements is not guaranteed.
Sort elements ascendingly by their natural order or by a provided Comparator.
Inherits the characteristics of SortedSet interface. All elements of TreeSet must be Comparable type or you must provide a Comparator for TreeSet comparing the elements. Otherwise, ClassCastException will be thrown. Comparator is provided at the time TreeSet object is created through one of its constructors.
TreeSet constructors:
TreeSet​(Comparator<? super E> comparator)   

// Using the same ordering as the specified sortedSet.
TreeSet​(SortedSet<E> sortedSet)    

TreeSet()     

TreeSet​(Collection<? extends E> c)

2. How does TreeSet store data?

TreeSet<E> manages an internal TreeMap<E,Object> object - internalMap. All operations on TreeSet are performed on internalMap. In addition, as we know TreeMap stores its data in a tree structure, which is the reason for the name of TreeSet.
For ease of understanding, look at the source code of java.util.TreeSet class, you'll see that it acts like a delegate of TreeMap object it manages.
java.util.TreeSet class
public class TreeSet<E> extends AbstractSet<E>
                   implements NavigableSet<E>, Cloneable, java.io.Serializable {

    private static final Object PRESENT = new Object();
    
    private transient TreeMap<E,Object> internalMap;
    
    public boolean add(E e) {
        return this.internalMap.put(e, PRESENT)==null;
    }
    
    public boolean remove(Object o) {
        return this.internalMap.remove(o)==PRESENT;
    }
    
    public void clear() {
        this.internalMap.clear();
    }
    
     public E first() {
        return this.internalMap.firstKey();
    }
     
    public E last() {
        return this.internalMap.lastKey();
    }
    // Other methods..
}
TreeMap stores its data in a tree structure, which is explained in my article below. Check it out if you are interested.

3. Examples

As we all know, Integer class implements Comparable interface, so Integer objects can be compared with each other. TreeSet with elements of Integer type is not necessary to provide a Comparator.
TreeSetEx1.java
package org.o7planning.treeset.ex;

import java.util.TreeSet;

public class TreeSetEx1 {

    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        //
        set.add(5);
        set.add(3);
        set.add(9);
        set.add(7);
        set.add(1);
        set.add(11);

        System.out.println(set);
    }
}
Output:
[1, 3, 5, 7, 9, 11]
Example: Use custom Comparator to reverse elements order.
TreeSet_reverseOrder_ex1.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSet_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeSet<Integer> set = new TreeSet<>(reverseOrderComparator);
        //
        set.add(5);
        set.add(3);
        set.add(9);
        set.add(7);
        set.add(1);
        set.add(11);

        System.out.println(set);
    }
}
Output:
[11, 9, 7, 5, 3, 1]
See more examples of using custom Comparator in TreeSet and how to navigate and find elements.

4. TreeSet with null element ​​​​​​

TreeSet allows null element only if it is provided with a Comparator that supports the comparison of null element with other elements.
TreeSet_nullElement_ex1.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet_nullElement_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

        // Create a SortedSet object.
        SortedSet<String> map = new TreeSet<String>(comparator);

        map.add("B");
        map.add("A");
        map.add("F");
        map.add(null);
        map.add("D");
        map.add("E");

        System.out.println(map);
    }
}
Output:
[null, A, B, D, E, F]
Example: Write a custom Comparator that supports comparing null element with other elements:
TreeSet_nullElement_ex2.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet_nullElement_ex2 {

    public static void main(String[] args) {
        Comparator<String> comparator = new StringNullComparator();

        // Create a SortedSet object.
        SortedSet<String> map = new TreeSet<String>(comparator);

        map.add("B");
        map.add("A");
        map.add("F");
        map.add(null);
        map.add("D");
        map.add("E");

        System.out.println(map);
    }
}

// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if (o1 == o2) {
            return 0; // o1 = o2
        }
        if (o1 == null) {
            return -1; // o1 < o2
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}
Output:
[null, A, B, D, E, F]