TreeSet In Java: Tutorial With Programming Examples

This Tutorial Explains all about TreeSet Class, Implementation, Iteration, TreeSet Vs HashSet, Java TreeSet Examples, etc.:

TreeSet in Java implements the Set interface (more specifically SortedSet). The TreeSet uses a TreeMap internally for storing data. By default, the objects or elements of the TreeSet are stored according to the natural ordering in ascending order.

The TreeSet class that implements TreeSet in Java implements the ‘NavigableSet’ interface and also inherits AbstractSet class.

=> Check Here To See A-Z Of Java Training Tutorials Here.

TreeSet in Java

TreeSet In Java

Note that the TreeSet elements can also be explicitly ordered by providing the customized Comparator at the time of creating a TreeSet object using the specific constructor prototype.

Given below are some of the important characteristics of TreeSet:

  1. TreeSet class implements the SortedSet interface. It doesn’t allow duplicate elements.
  2. TreeSet class is not synchronized.
  3. TreeSet does not preserve the insertion order but the elements in TreeSet are sorted as per the natural ordering.
  4. TreeSet can be ordered by using a custom comparator while creating a TreeSet object.
  5. TreeSet is normally used for storing huge amounts of information that is naturally sorted. This aids in easy and faster access.

TreeSet Class Declaration

Java provides a class called “TreeSet” that contains the functionality of TreeSet data structure. The TreeSet class is a part of java.util package.

To include the TreeSet class in the Java program, we should use the import statement as given below:

import java.util.TreeSet;

or

import java.util.*;

A general declaration of TreeSet class is:

public class TreeSet<E> extends AbstractSet<E>
   implements NavigableSet<E>, Cloneable, Serializable

As seen from the class declaration, TreeSet class extends AbstractSet and implements NavigableSet, Cloneable, and Serializable interfaces.

A class hierarchy for TreeSet class is given below:

class hiearachy for TreeSet

Internal Implementation

We know that TreeSet implements the NavigableSet interface and extends the SortedSet class.

Internally, the TreeSet constructor is defined as follows:

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

As seen in the above constructor definition of TreeSet, a TreeMap object is invoked. Thus internally, it is a TreeMap object that is implemented for a TreeSet. Hence while adding an element to TreeSet, a key is added to TreeMap in which the keys are sorted by default.

As per Oracle documentation on TreeSet,

“A TreeSet is a NavigableSet implementation based on a TreeMap.”

Java TreeSet Example

The following Java program shows a simple example that demonstrates TreeSet. In this program, we have defined a simple Color TreeSet. We add elements to it and then display it. Note that the elements are displayed as per the natural ordering.

 import java.util.*;  
class Main{  
 public static void main(String args[]){  
  //Create and add elements to TreeSet 
  TreeSet<String> color_TreeSet=new TreeSet<String>();  
  color_TreeSet.add("Red");  
  color_TreeSet.add("Green");  
  color_TreeSet.add("Blue");  
  color_TreeSet.add("Yellow");  
  //Traverse the TreeSet and print elements one by one
  System.out.println("TreeSet Contents:");
  Iterator<String> iter=color_TreeSet.iterator();  
  while(iter.hasNext()){  
   System.out.print(iter.next() + "\t");  
  }  
 }  
}  

Output:

TreeSet Contents:
Blue Green Red Yellow

output - TreeSet Implementation

Iterate Through TreeSet

To access the individual elements of TreeSet, we need to iterate through the TreeSet or in other words, traverse through the TreeSet.

We do this by declaring an Iterator for the TreeSet and then use this Iterator to access each element. For this, we use the next () method of an iterator that returns the next element in the TreeSet.

The following Java program demonstrates the use of the Iterator to iterate through TreeSet.

import java.util.TreeSet;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {
        //create and initialize TreeSet
        TreeSet<Integer> num_Treeset = new TreeSet<>();
        num_Treeset.add(20);
        num_Treeset.add(5);
        num_Treeset.add(15);
        num_Treeset.add(25);
        num_Treeset.add(10);
        System.out.println("TreeSet: " + num_Treeset);

        // Call iterator() method to define Iterator for TreeSet
        Iterator<Integer> iter_set = num_Treeset.iterator();
        System.out.print("TreeSet using Iterator: ");
        // Access TreeSet elements using Iterator
        while(iter_set.hasNext()) {
            System.out.print(iter_set.next());
            System.out.print(", ");
        }
    }
}

Output:

TreeSet: [5, 10, 15, 20, 25]
TreeSet using Iterator: 5, 10, 15, 20, 25,

use of the Iterator output

TreeSet Comparator In Java

By default, the TreeSet is naturally ordered. We can also sort TreeSet in a customized order by defining a new comparator class. In this comparator class, we need to override the ‘compare’ method to sort the elements of the TreeSet. This comparator object is then passed to the TreeSet constructor.

The following Java program shows the use of a Comparator to sort the TreeSet.

import java.util.TreeSet;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {
        // Create a TreeSet with user-defined comparator
        TreeSet<String> cities = new TreeSet<>(new cities_Comparator());
        //add elements to the comparator
        cities.add("Pune");
        cities.add("Hyderabad");
        cities.add("Indore");
        cities.add("Bangaluru");
        //print the contents of TreeSet
        System.out.println("TreeSet: " + cities);
    }
    // Create a comparator class
    public static class cities_Comparator implements Comparator<String> {
        //override compare method to compare two elements of the TreeSet
        @Override
        public int compare(String cities_one, String cities_two) {
            int value =  cities_one.compareTo(cities_two);
            // sort elements in reverse order
            if (value > 0) {
                return -1;
            }
            else if (value < 0) {
                return 1;
            }
            else {
                return 0;
            }
        }
    }
}

Output:

TreeSet: [Pune, Indore, Hyderabad, Bangaluru]

program shows the use of a Comparator output

The above program implements a Comparator class to sort the given TreeSet alphabetically in reverse order.

TreeSet API/Methods & Constructors

In this section, we will discuss the API of the TreeSet class. Here we will discuss the constructors and methods provided by the TreeSet class.

TreeSet class provides overloaded constructors to construct a TreeSet object.

We have tabularized these constructors as follows:

Constructors

Constructor PrototypeDescription
TreeSet ()Default constructor to create a new, empty TreeSet object.
TreeSet (Collection < ? extends E > c )Creates a new TreeSet object containing the elements from given collection c, sorted as per natural ordering.
TreeSet
( Comparator < ? super E > comparator )
Constructs a new TreeSet object which is empty and will be sorted as per specified comparator.
TreeSet ( SortedSet < E > s )Creates a new TreeSet object that contains elements from given sortedSet s.

Methods

Next, let’s tabularize the various methods provided by the TreeSet class.

MethodMethod PrototypeDescription
addboolean add ( E e)Adds given element to the TreeSet if it’s not already there.
addAllboolean addAll ( Collection < ? extends E > c )Adds all the elements in the given collection c to the set.
ceilingE ceiling ( E e )Returns element greater than or equal to e (least element); or null if no element is present.
clearvoid clear ( )Deletes all the elements from the TreeSet.
cloneObject clone ( )Returns a shallow copy of TreeSet object.
comparatorComparator < ? super E > comparator ( )Returns the comparator for the TreeSet or null if natural ordering is used.
containsboolean contains ( Object o )Checks if TreeSet contains given element; true if present.
descendingIteratorIterator < E > descendingIterator ( )Returns descending iterator over the elements in the TreeSet.
descendingSetNavigableSet < E > descendingSet ( )Returns a view of elements in the TreeSet in reverse order.
firstE first ( )Returns first or lowest element in the TreeSet.
floorE floor ( E e )Returns the element that is less than or equal to the given element e in the TreeSet. Returns null if no such element.
headSetSortedSet < E > headSet ( E toElement )returns a set of elements that are strictly less than the given toElement
NavigableSet < E > headSet ( E toElement, boolean inclusive )Returns a set of elements that are equal to (if inclusive = true) or less than given toElement.
higherE higher ( E e )Returns the least element in this set strictly greater than the given element, or null if there is no such element.
isEmptyboolean isEmpty ( )Checks if the TreeSet is empty. Returns true if empty.
iteratorIterator < E > iterator ( )Returns an iterator (in ascending order) for the TreeSet.
lastE last ( )Returns the highest or last element in the TreeSet.
lowerE lower ( E e )Returns the element (greatest element) that is strictly less than given element e in the TreeSet.
pollFirstE pollFirst ( )Removes and returns the first (lowest) element in the set; null if the set is empty.
pollLastE pollLast ( )Removes and returns the last (greatest) element in the set; null if set empty.
removeboolean remove ( Object o )Removes the given element from the set.
sizeint size ( )Returns the size or number of elements present in the TreeSet.
subSetNavigableSet < E > subset ( E fromElement, boolean fromInclusive, E toElement, boolean toInclusive )
Returns a view of elements ranging from fromElement to toElement.
SortedSet < E > subSet ( E fromElement, E toElement )Returns a view elements ranging from fromElement (inclusive), to toElement (exclusive).
tailSetSortedSet < E > tailSet ( E fromElement )Returns a view containing elements that are greater than or equal to the given fromElement.
NavigableSet < E > tailSet ( E fromElement, boolean inclusive )Returns a view of the elements are equal to (if inclusive is true) or greater than fromElement.

TreeSet In Java 8

Please note that for TreeSet, there are no major changes in the Java 8 version. All methods and constructors work in Java 8 and the later versions.

TreeSet Implementation In Java

The following Java program implements most of the TreeSet methods discussed above.

import java.util.Iterator; 
import java.util.TreeSet;
import java.util.ArrayList;
  
public class Main { 
    public static void main(String[] args) { 
        //create a TreeSet of numbers
        TreeSet<Integer> numSet = new TreeSet<Integer>(); 
        //add () method
        numSet.add(30); 
        numSet.add(10); 
        //declare and initialize an ArrayList
        ArrayList<Integer> myList = new ArrayList<Integer>();
        myList.add(15);
        myList.add(25);
        myList.add(35);
        //addAll () method : add ArrayList elements to TreeSet
        numSet.addAll(myList);
        //define an iterator on TreeSet
        Iterator<Integer> iterator = numSet.iterator(); 
        System.out.print("Tree set contents: "); 
        while (iterator.hasNext()) 
            System.out.print(iterator.next() + " "); 
        System.out.println(); 
        //ceiling () 
        System.out.println("ceiling(25):" + numSet.ceiling(25));
        //floor ()
        System.out.println("floor(25):" + numSet.floor(25));
        //contains ()
        System.out.println("TreeSet contains(15):" + numSet.contains(15));
  
        // isEmpty () 
        if (numSet.isEmpty()) 
            System.out.print("Tree Set is empty."); 
        else
            System.out.println("Tree Set size: " + numSet.size()); 
  
        
       // first ()  
        System.out.println("TreeSet First element: " + numSet.first()); 
  
        // last ()
        System.out.println("TreeSet Last element: " + numSet.last()); 
  
        // remove () 
        if (numSet.remove(30)) 
            System.out.println("Element 30 removed from TreeSet"); 
        else
            System.out.println("Element 30 doesn't exist!"); 
  
        System.out.print("TreeSet after remove (): "); 
        iterator = numSet.iterator(); 
        while (iterator.hasNext()) 
            System.out.print(iterator.next() + " "); 
        System.out.println(); 
        //size ()
        System.out.println("TreeSet size after remove (): " + numSet.size()); 
        //Headset ()
        System.out.println("Headset : " + numSet.headSet(35));
        // clear () 
        numSet.clear(); 
        System.out.println("Tree Set size after clear (): " + numSet.size());
    } 
}

Output:

Tree set contents: 10 15 25 30 35
ceiling(25):25
floor(25):25
TreeSet contains(15):true
Tree Set size: 5
TreeSet First element: 10
TreeSet Last element: 35
Element 30 removed from TreeSet
TreeSet after remove (): 10 15 25 35
TreeSet size after remove (): 4
Headset : [10, 15, 25]
Tree Set size after clear (): 0

Java program implements most of the TreeSet methods - Output

In the above program, we define a TreeSet object and then add elements to it using the ‘add’ method. Next, we define an ArrayList. Then we add elements of ArrayList to TreeSet using the ‘addAll’ method. Later, we demonstrate various TreeSet methods like Iterator, ceiling, floor, first, last, contains, size, isEmpty, etc.

TreeSet Vs HashSet

Let’s check out some of the differences between TreeSet and HashSet.

TreeSetHashSet
Elements are ordered as per natural ordering.Elements are not ordered.
Takes O ( log N ) time for operations like insert, delete and search thus making it slower than TreeSet.Takes constant time for basic operations like insert, delete and search making it faster than TreeSet.
Doesn’t allow null objects.Allows null object.
Uses the compareTo ( ) method to compare two objects.Uses compare () and equals () method to compare two objects.
Internally implemented using Navigable TreeMap.Internally implemented using HashMap.
Has rich functionality API that can perform various manipulations.The functionality API of HashSet is rather limited.

Frequently Asked Questions

Q #1) What is a TreeSet?

Answer: TreeSet is an implementation of SortedSet that does not allow duplicate values. The elements in the TreeSet are by default sorted in ascending order.

Q #2) How do you add elements to TreeSet in Java?

Answer: TreeSet class provides an add method that is used to add a specific element to the TreeSet. It also provides the ‘addAll’ method. This method accepts any other collection as an argument and then adds all the elements of this collection to the TreeSet.

Q #3) Is TreeSet thread-safe?

Answer: No. TreeSet is not thread-safe. Thus we should take care of how we operate TreeSet in a multi-threaded environment.

Q #4) Can TreeSet have duplicates?

Answer: No. TreeSet does not allow duplicates.

Q #5) Does TreeSet allow null in Java?

Answer: Yes. We can have null elements in TreeSet.

Conclusion

This completes our tutorial on TreeSet. TreeSet is a SortedSet implementation that does not allow duplicates but allows null values. The elements in the TreeSet are by default sorted according to natural ordering in ascending order.

We have seen the basics of the TreeSet class along with its declaration and various constructors & methods.

In our subsequent tutorials, we discuss the remaining Java collection classes.

=> Watch Out The Simple Java Training Series Here.