TreeSet internal working

We have learned a lot of things about TreeSet in recent posts. TreeSet stores only unique elements and also sorts the elements. It sorts the elements in natural order or custom order by providing a comparator. In this post, we will learn the TreeSet internal implementation in java and TreeSet internal working.

Here is the table content of the article will we will cover this topic.
1. TreeSet internal working?
2. How TreeSet sorts the elements?
3. Why TreeSet doesn’t accept null?

TreeSet internal working

The TreeSet internally uses the TreeMap to store the elements. The SortedSet interface provides functionality to keep the elements in sorted order and the NavigableSet interface provides functionality to navigate through the SortedSet. A TreeSet implements the interface and NavigableSet interface, that why TreeSet maintains the order of elements.

Whenever we create a TreeSet, The JVM internally creates a TreeMap and perform all the operations on TreeMap. It works like HashSet, only the difference is that instead of HashMap here we have TreeMap object in the constructor. Let’s have a look at JDK.

public TreeSet() {
        this(new TreeMap<>());
    }

If we look a bit more in JDK code, the object of TreeMap internally assigned to reference of NavigableMap.

private transient NavigableMap<E,Object> m;

TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

Like HashMap, TreeMap doesn’t contain duplicate keys. So, when we add any element in TreeSet, it internally performs put operation on TreeMap and store value as a key with Dummy value in TreeMap. If you are not familiar with the internal working of HashSet, then please read it first.
TreeSet sorts the elements in natural order by default or we can provide comparator if we want to sort in any order. The TreeMap internally uses the comparable or comparator to sort the element. Let’s discuss it in detail.

How TreeSet sorts the elements?

We have known, A TreeSet internally uses the TreeMap and perform all the operation on TreeMap. A TreeMap sorts the elements either in natural order or in the custom order. TreeMap uses either Comparable or Comparator to sort the elements. Now let’s see how TreeSet maintaining the natural order even we don’t provide any comparator.

When we create an object of TreeSet without any comparator(default constructor of TreeSet), it internally creates an object of TreeMap and TreeMap assign comparator is null.

public TreeMap() {
        comparator = null;
    }

The TreeMap compares each element during insertion in TreeMap. In this case, TreeMap uses comparable to compare the objects during an insert operation. When we will add any element in TreeSet it internally put in TreeMap. The put method checks if the object of the comparator is null then it compares the element based on comparable.

NOTE: The class must implement the Comparable interface, all the wrapper classes and String class already implements the Comparable interface by default.

Why TreeSet doesn’t accept null?

A TreeSet compares each element either by comparable or comparator. If TreeSet allows null, then it will throw NullPointerException.