Skip to main content

TreeSet in Java

TreeSet in Java

In this article, we are going to learn about what is TreeSet in Java. Also, we look at the upper hierarchy of TreeSet in Java. We will look at the methods provided by TreeSet.

Content of the Article


What is TreeSet in Java?

TreeSet in java is an implementation of Set interface i.e., duplicate elements are not allowed, Set interface provides the facility to store and retrieve elements.
TreeSet internally maintains a TreeMap as its internal data structure, so that all the operation made on the TreeSet transparently done on the TreeMap.
Declaration of TreeMap within the TreeSet in Java
public class TreeSet<E>{
        private transient TreeMap<E,Object> map; 
        private static final Object PRESENT = new Object();
}
The type of TreeSet is same as the key type of TreeMap i.e., all the elements added to the TreeSet will become the Keys of TreeMap and a constant value of Object type is associated with each key of the TreeMap named as PRESENT.
Note : To understand TreeSet in java properly, first we should understand what is TreeMap in java.

TreeMap maintains a sorting order, so that TreeSet also maintains a sorting order. To provide sorting order to the TreeSet, we can use one of the two options :
  • Sort in the order specified by the Comparator<T>, if the Comparator<T> has been provided at the time of the creation of TreeSet, or
  • Sort in the natural order of its elements (order provided by the Comparable<T> Interface). In this case, the elements added to the TreeSet must implement the Comparable<T> Interface
Note : We must have to provide an implementation of one of them. If we provide the implementation of both then the implementation of the Comparator will have higher priority.
TreeSet in Java is the part of Java Collection Framework. It is defined in java.util package and implements Set interface which provides standard method declaration to perform basic operation like store, retrieve elements from the TreeSet and etc.

Important point to remember about the TreeSet in Java

  • TreeSet in java is an implementation of Set Interface i.e., duplicate elements are not allowed.
  • TreeSet in Java internally maintains a TreeMap data structure. All the methods provided by the TreeSet internally works upon the TreeMap.
  • TreeSet in a generic class i.e., It can store any type of elements. It cannot store any primitive type elements, for that we can use wrapper classes as the type of TreeSet. For example Integer class instead of int primitive.
  • The insertion order is not maintained by the TreeSet as elements are placed in the sorted order.
  • No null value can be stored in the TreeSet.
  • TreeSet in java, is not synchronized among the threads, it must be synchronized externally in a multi-threaded environment.

Time complexity of TreeSet in Java?

Time complexity to store and retrieve data from the TreeSet in Java is same as of the TreeMap which is O(log n).

Hierarchy of the TreeSet in java?

Declaration of TreeSet
public class TreeSet<E>
    extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
     ----------------
}

AbstractSet<E>

The AbstractSet<E> provides a basic and abstract implementation of the Set Interface to the TreeSet. Also, AbstractSet<E> extends the AbstractCollection<E> which provides the abstract implementation of the Collection Interface.

NavigableSet<K, V>

TreeSet in java also implements NavigableSet<K, V>, which is an extension of SortedSet<K, V>. NavigableSet provides standard methods to navigate throughout the Map, methods like lower(), floor(), ceiling() and higher() and many more.
Also, this interface provides the functionality to retrieve the sub-set from the actual set. The headSet(), tailSet() and subSet() methods are used to fetch sub-set.

Why Cloneable?

Cloneable is a marker interface and it is a part of java.lang package. A class implements this interface if it wants to call the clone() method of Object class using super keyword i.e., super.clone(); through any method or any constructor. If that class does not implement this marker interface and invoke the i.e., super.clone(); then java.lang.CloneNotSupportedException will be raised.
TreeSet in Java, provides overrode clone() method that internally calls the actual clone() method of Object class. So, TreeSet needs to implement this marker interface.
Note : The clone() method of Object class is used to create a cloned object.

Why Serializable?

Serializable is a marker interface and it is a part of java.io package. If Any class implements this interface then the class can be serialized or deserialized. Serialization is a process in which an object is converted into the byte stream and Deserialization is the reverse of serialization i.e., byte stream to java object. Serialization helps us to store and retrieve objects from and to files, databases, networks, etc. The only class marked with the Serializable interface can be serialized or deserialized.
TreeSet in Java often needs to store and retrieve the object from the files, databases, etc. That's why TreeSet is implemented as Serializable.

How to create an object of TreeSet in java?

Till now, we have learned what is TreeSet in Java and its hierarchy, now let's have a look at the different ways to create objects of TreeSet.

Using Default Constructor

Default Constructor of TreeSet, creates a new TreeSet. The type defined of the TreeSet must implement the Comparable Interface otherwise java.lang.ClassCastException will be raised at the time of adding elements to the TreeSet in Java.
If the TreeSet is constructed using the default constructor, the elements are sorted in its natural order. The order defined by the Comparable interface known as Natural Order.
TreeSet<String> treeSet = new TreeSet<>();
Above, the type declared as String and String class implement Comparable interface. If we want to use any user-defined class as the key to the TreeSet, it must implement the Comparable interface.

Using Constructor which requires Comparator

This constructor takes an argument of the Comparator and constructs an empty TreeSet. If we want to store elements that do not implement the Comparable interface then we can use this constructor to create a TreeSet in Java. Let's first create a user-defined class that does not implement the Comparable interface.
class Book{
     private String name;
     private int price;

     public Book(String name, int price){
          this.name = name;
          this.price = price;
     }

     public String getName() {
          return name;
     }

     public void setName(String name) {
          this.name = name;
     }

     public int getPrice() {
          return price;
     }

     public void setPrice(int price) {
          this.price = price;
     }

     @Override
     public String toString(){  
          return "[ " + name + " : " + price + " ]";
     }   
}
Create a TreeSet using Comparator that store elements of Book class.
Comparator<Book> bookComparator = (o1, o2) -> o1.getPrice() - o2.getPrice();
TreeSet<Book> bookSet = new TreeSet<>(bookComparator);
Note : Type declaration of Comparator and Type declaration of TreeMap must be same. As we can see in the above case, Book class is used type declaration of both Comparator and TreeSet.

How to create an object of Comparator?

To create an object of Comparator, we have two options using Anonymous class and Lambda Expression.
Using Anonymous class
Comparator<Book> bookComparator = new Comparator<Book>() {
     @Override
     public int compare(Book o1, Book o2) {
          return o1.getPrice() - o2.getPrice();
     }
};
Using Lambda Expression
Comparator<Book> bookComparator = (o1, o2) -> o1.getPrice() - o2.getPrice();
To know more about the Lambda Expression, read this article: Lambda Expression in java

How to add elements to the TreeSet in java?

The add() method is used to add elements into the TreeSet one at a time. This method takes one argument and store into the TreeSet in java.
Syntax of add() method
boolean result = treeSet.add(element);
This method returns true if a new element is added to the TreeSet, Otherwise false which states TreeSet has not modified. In most of the case, we don't use the boolean value returned by the add() as it only signifies that the element is new or not.
Internal Definition of add() method
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}
The above expression map.put(e, PRESENT)==null; returns true, because the put() method returned null if a new key is added to the TreeMap.

When the TreeSet is constructed using default Constructor

Java TreeSet Example 1: Create a set of books using default constructor

TreeSet<String> bookSet = new TreeSet<>();
bookSet.add("Programming In Java");
bookSet.add("Computer Networks");
bookSet.add("Introduction to Algorithms");
bookSet.add("Data Structures");
for (String book : bookSet) {
       System.out.println(book);
}
Output
Computer Networks
Data Structures
Introduction to Algorithms
Programming In Java
As we can see the book names are sorted into alphabetical order. This is because of the natural order provided by the Comparable interface to the strings.

When the TreeSet is constructed with Comparator

Java TreeSet Example 2: Create a set of books using the constructor which take Comparator

Comparator<Book> bookComparator = (o1, o2) -> o1.getPrice() - o2.getPrice();
TreeSet<Book> bookSet = new TreeSet<>(bookComparator);
bookSet.add(new Book("Programming In Java", 400));
bookSet.add(new Book("Introduction to Algorithms", 600));
bookSet.add(new Book("Data Structures", 500));
bookSet.add(new Book("Learn C++", 300));
for (Book book : bookSet) {
       System.out.println(book);
}
Output
[ Learn C++ : 300 ]
[ Programming In Java : 400 ]
[ Data Structures : 500 ]
[ Introduction to Algorithms : 600 ]
Now the books are sorted into ascending order w.r.t price, because of the order provided by the Comparator.

How to iterate TreeSet in java?

In java, there are the number of approaches to iterate TreeSet in Java. Let's look at a few of them which come in day-to-day programming practices.

Using for-each loop

Java TreeSet Example 3 : Iterate the TreeSet in Java using for each loop and print all the name of books

for(String book : bookSet) {
      System.out.println(book);
}
Output
Computer Networks
Programming In Java
Introduction to Algorithms
Data Structures

Using Iterators

Java TreeSet Example 4 : Iterate the TreeSet in Java using iterators and print all the name of books

Iterator<String> iterator = bookSet.iterator();
while(iterator.hasNext()){
      String book = iterator.next();
      System.out.println(book);
}
Output
Computer Networks
Programming In Java
Introduction to Algorithms
Data Structures

Using forEach() method

Java TreeSet Example 5 : Iterate the TreeSet in Java using forEach() method and print all the name of books

bookSet.forEach(book -> System.out.println(book));
Output
Computer Networks
Programming In Java
Introduction to Algorithms
Data Structures

How to check whether an element is stored in the TreeSet in Java?

To check whether an element is present into the TreeSet or not, TreeSet in Java provides a method called contains() method. This method takes an argument and returns true if the TreeSet contains the specified element.
Syntax of contains() method
boolean result = treeSet.contains(element);
Internal Definition of contains() method
public boolean contains(Object o) {
        return map.containsKey(o);
}
Internally, containsKey() method of the TreeMap is invoked and return true if the TreeMap contains that element as the Key.

Java TreeSet Example 6 : Check whether "Computer Networks" is contained within the TreeSet or not

TreeSet<String> bookSet = new TreeSet<>();
bookSet.add("Programming In Java");
bookSet.add("Computer Networks");
bookSet.add("Introduction to Algorithms");
bookSet.add("Data Structures");
if(bookSet.contains("Computer Networks")) {
        System.out.println("TreeSet contains Computer Networks");
}
Output
TreeSet contains Computer Networks

How to remove elements from the TreeSet in java?

Using remove(object) method

The remove(object) method is used to remove the specified element from the TreeSet in Java. This method return true if the element is present and successfully removed.
Syntax of remove() method
boolean result = treeSet.remove(element);
Internal Definition of remove() method
public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
}
Internally, the remove() method of the HashMap is invoked. In-actual, the mapping is removed from the TreeMap and returns the value associated with the key, which will always be PRESENT if exists, otherwise null is returned.

Java TreeSet Example 7 : Remove "Computer Networks" named book from the TreeSet in Java

TreeSet<String> bookSet = new TreeSet<>();
bookSet.add("Programming In Java");
bookSet.add("Computer Networks");
bookSet.add("Introduction to Algorithms");
bookSet.add("Data Structures");
System.out.println("TreeSet values : " + bookSet);
if(bookSet.remove("Computer Networks")) {
        System.out.println("Computer Networks is successfully removed");
}
System.out.println("TreeSet values : " + bookSet);
Output
TreeSet values : [Computer Networks, Data Structures, Introduction to Algorithms, Programming In Java]
Computer Networks is successfully removed
TreeSet values : [Data Structures, Introduction to Algorithms, Programming In Java]

Using removeIf() method

To remove object on the basis of some conditions we can use removeIf() method. The removeIf() method takes an argument of java.util.Predicate type, apply that predicate to each element of TreeSet in Java and remove all those element which satisfies the given predicate.
Note : Predicate is an Functional Interface introduced in Java 8. To know more about Function Interface, visit this article : Functional Interface in Java

Java TreeSet Example 8 : Create a new TreeSet of cities and remove all the cities that is not from India

TreeSet<String> cities = new TreeSet<>();
cities.add("Delhi-India");
cities.add("New York-USA");
cities.add("Mumbai-India");
cities.add("Kolkata-India");
cities.add("London-England");
System.out.println("-------------Cities : Before removing---------------");
System.out.println(cities);
cities.removeIf(city -> !city.contains("India"));
System.out.println("-------------Cities : After removing----------------");
System.out.println(cities);
Output
-------------Cities : Before removing---------------
[Delhi-India, Kolkata-India, London-England, Mumbai-India, New York-USA]
-------------Cities : After removing----------------
[Delhi-India, Kolkata-India, Mumbai-India]
Note : The city -> !city.contains("India") is the lambda representation of the Predicate class. To know more about the Lambda Expression read these article : Lambda Expression in Java.

Reverse order set provided by the TreeSet in Java?

TreeSet provides a method which returns reverse order set of TreeSet i.e., all the element of the TreeSet returned in the reverse order. The descendingSet() method is used to retrieve the reverse order set of TreeSet in Java.

Java TreeSet Example 9 : Using descendingSet() method of TreeSet, retrieve the reverse order set

TreeSet<String> bookSet = new TreeSet<>();
bookSet.add("Programming In Java");
bookSet.add("Introduction to Algorithms");
bookSet.add("Data Structures");
bookSet.add("Learn C++");
  
NavigableSet<String> descendingBookSet = bookSet.descendingSet();
for (String book : descendingBookSet) {
      System.out.println(book);
}
Output
Programming In Java
Learn C++
Introduction to Algorithms
Data Structures

How to get sub-set from the TreeSet in Java?

There are some methods through which we can fetch the sub-set from the TreeSet. The sub-set is also following the same sorted order as the actual TreeSet. These methods are :
  • subSet() : this method takes two arguments: fromElement and toElement and return a sub-set from the one element to the another element of the TreeSet.
    Syntax of subSet()
    SortedSet<K, V> subSet = treeSet.subSet(fromElement, toElement);
  • headSet() : this method takes an toElement argument and return a sub-set from the beginning of the TreeSet to just before the specified element node.
    Syntax of headSet()
    SortedSet<K, V> headSet = treeSet.headSet(toElement);
  • tailSet() : this method takes an fromElement argument and return a sub-set from the specified element to the end of the TreeSet.
    Syntax of tailSet()
    SortedSet<K, V> tailSet = treeSet.tailSet(fromElement);

Java TreeSet Example 10 : Using the above methods of TreeSet, retrieve the sub-sets

TreeSet<String> bookSet = new TreeSet<>();
bookSet.add("Programming In Java");
bookSet.add("Introduction to Algorithms");
bookSet.add("Data Structures");
bookSet.add("Learn C++");
bookSet.add("Computer Networks");

System.out.println("Full TreeSet : " + bookSet);
  
SortedSet<String> subSet = bookSet.subSet("Data Structures", "Learn C++");
System.out.println("Sub Set : " + subSet);

SortedSet<String> headSet = bookSet.headSet("Learn C++");
System.out.println("Head Set : " + headSet);

SortedSet<String> tailSet = bookSet.tailSet("Learn C++");
System.out.println("Tail Set : " + tailSet);

Output
Full TreeSet : [Computer Networks, Data Structures, Introduction to Algorithms, Learn C++, Programming In Java]
Sub Set : [Data Structures, Introduction to Algorithms]
Head Set : [Computer Networks, Data Structures, Introduction to Algorithms]
Tail Set : [Learn C++, Programming In Java]

How to get first and last element from the TreeSet in Java?

As we know TreeSet implements SortedSet i.e., all entries are placed into sorted order. Accordingly, we have methods to access the first and last element of TreeSet. These methods are :
  • first() : Returns the first element of the TreeSet
    Syntax of first()
    T first = treeSet.first();
  • last() : Returns the last element of the TreeSet
    Syntax of last()
    T last = treeSet.last();

Java TreeSet Example 11 : fetch the first and last element of the TreeSet

TreeSet<String> bookSet = new TreeSet<>();
bookSet.add("Programming In Java");
bookSet.add("Introduction to Algorithms");
bookSet.add("Data Structures");
bookSet.add("Learn C++");
bookSet.add("Computer Networks");

System.out.println("Full TreeSet : " + bookSet);
  
String firstElement = bookSet.first();
System.out.println("First Element : " + firstElement);

String lastElement = bookSet.last();
System.out.println("Last Element : " + lastElement);

Output
Full TreeSet : [Computer Networks, Data Structures, Introduction to Algorithms, Learn C++, Programming In Java]
First Element : Computer Networks
Last Element : Programming In Java

Few more methods of TreeSet in java

size() : This method returns the size of TreeSet in Java i.e., how many elements are stored in the TreeSet.
clear() : This method removes all elements from the TreeSet and make it empty.
isEmpty() : This method returns true if the TreeSet is not containing any elements in it otherwise false.

Java TreeSet Example 12 : Different States of TreeSet in Java

TreeSet<String> cities = new TreeSet<>();
cities.add("Delhi-India");
cities.add("New York-USA");
cities.add("Mumbai-India");
cities.add("Kolkata-India");
cities.add("London-England");
System.out.println("How many cities are there in the TreeSet? : " + cities.size());

System.out.println("Removing all elements from the TreeSet.....");
cities.clear();

if(cities.isEmpty()) {
       System.out.println("TreeSet is Empty Now");
}
Output
How many cities are there in the TreeSet? : 5
Removing all elements from the TreeSet.....
TreeSet is Empty Now

Related Articles

Conclusion

In this article, we have learned what is TreeSet in Java, also the related methods of TreeSet. Different ways to create a TreeSet in Java.

Comments

Popular posts from this blog

How HashMap works internally in java

How Hashmap works Internally in Java In this article, we are going to see how HashMap internally works in java. Also, we will have a look at what Java 8 made changes on the internal working of Hashmap to make it faster. What is Hashmap and Hashing in java? How Hashmap works Internally in Java is majorly dependent upon the Hashing Principle. So, Before going to learn how HashMap works internally in java, lets first understand what is HashMap and hashing. HashMap : A HashMap is a map used to store mappings of key-value pairs. Also, it works on the Principle of Hashing. To know more about the HashMap, visit this article: HashMap in Java Hashing Principle : Simply, Hashing is a method used to produce an integer value from an object and this integer value known as the hash value. In HashMap, the key object is used for Hashing.
Internal Struture of the HashMap in java For internal working of HashMap, HashMap maintains an array of bucket, each bucket is a linked-list and linked list is a li…

HashMap in Java

HashMap in Java In this article, we are going to learn about the most important class of Java known as HashMap. HashMap in java is the most used map interface and it is used in our regular or day-to-day programming practices.
What is HashMap in java? Lets first start with basic definition of HashMap,
HashMap is a map which store key-value pair, where each key is mapped with a value.
HashMap defined in java.util package and implements map interface which provides functionalities to perform basic operation like store, retrieve, size of the map etc. It is a part of Java Collection Framework. Time complexity of HashMap in Java? : Time complexity to store and retrieve data from the HashMap is O(1) in the Best Case. But it can be O(n) in the worst case and after the changes made in Java 8 the worst case time complexity can be O(log n) atmost. Internal working of HashMap in java HashMap maintains an array of the buckets, where each bucket is a linked-list and the linked list is a list of…

ArrayList in Java

ArrayList in Java In this article, we are going to discuss ArrayList in Java. ArrayList is a class from the Java Collection Framework and widely in our programs. We use ArrayList as a substitute for the array. So, it is important to know ArrayList in detail. We are going to see what is ArrayList in Java, how we can create the instance of ArrayList and the methods provided by the ArrayList in Java.

If you already familiar to ArrayList, you may learn common programs related to ArrayList.
Table of ContentsWhat is ArrayList in Java?Hierarchy of the ArrayList in java?How to create objects of ArrayList in Java?How to create an ArrayList of Custom Objects?How to iterate ArrayList in Java?How to get the elements by index from ArrayList in Java?How to check whether an elements is stored in the ArrayList in Java?How to remove elements from the ArrayList in Java?Few more methods of ArrayList in Java?
What is ArrayList in Java? ArrayList in Java is a List in which we can store and retrieve elemen…