o7planning

Java TreeSet Tutorial

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.
  • TODO Link!
  • TODO Link!
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.
  • TODO Link!

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]
Maybe you are interested

These are online courses outside the o7planning website that we introduced, which may include free or discounted courses.