TreeSet in Java

Internship at OpenGenus

Get FREE domain for 1st year and build your brand new site

TreeSet is created using the implementations of the SortedSet interface in Java and it uses Tree for storage. Objects that are stored in a TreeSet are in sorted and ascending order, this is done by ethier using set's natural ordering or by explicitly providing a comparator.

Hierarchy of TreeSet class

Java TreeSet class implements the NavigableSet interface,Furthur NavigableSet interface extends SortedSet, Set, Collection and Iterable interfaces in hierarchical order.

Screenshot-from-2021-03-07-14-36-20

Creating a TreeSet

Below is an implementation on how to create and use a TreeSet.

  import java.util.*;  
    class TreeSet1{  
     public static void main(String args[]){  
      //Creating TreeSet
      TreeSet<String> al=new TreeSet<String>();  
     
      //Adding elements to it.
      al.add("Ravi");  
      al.add("Vijay");  
      al.add("Ravi");  
      al.add("Ajay");  
      
      //Traversing elements  
      Iterator<String> itr=al.iterator();  
      while(itr.hasNext()){  
       System.out.println(itr.next());  
      }  
     }  
    }  

Output:

Ajay 
Ravi
Vijay

We get this following output even though we added 'Ravi' twice this is because in TreeSet only unique elements can be stored and as in the ouput is in ascending order.

Various operation on TreeSet

Below are a few of different operation that can be performed using a TreeSet.

1.Adding Elements in the TreeSet
To add an element in a TreeSet, we use the add() method. The order of insertion is not retained in the TreeSet as internally values of each and every element is sorted in ascending order. As well as no duplicate elements are allowed if a user tries to add duplicate element, they are ignored by the TreeSet. Null values are also not allowed.

import java.util.*; 
  
class TreeSetClass { 
  
    public static void main(String[] args) 
    { 
        TreeSet<String> ts = new TreeSet<String>(); 
  
        // Adding elements using add() method 
        ts.add("Ronaldo"); 
        ts.add("Cris"); 
        ts.add("Elena"); 
  
        System.out.println(ts); 
    } 
} 

Output

Cris
Elena
Ronaldo

2.Printing elements in descending order
Elements inside a TreeSet can be printed in descending order using an iterator.

    import java.util.*;  
    class TreeSetClass{  
     public static void main(String args[]){  
     TreeSet<String> ts=new TreeSet<String>();  
             ts.add("Ronaldo");  
             ts.add("Cris");  
             ts.add("Elena");  
             System.out.println("Traversing element in descending order");  
             Iterator i=set.descendingIterator();  
             while(i.hasNext())  
             {  
                 System.out.println(i.next());  
             }  
               
     }  
    }  

Output

Ronaldo
Elena
Cris

3. Accessing the Elements
If we want to access the elements which we stored in TreeSet, we can use inbuilt methods like contains(), first(), last(), etc.

import java.util.*; 
class TreeSetClass { 
  
    public static void main(String[] args) 
    { 
        TreeSet<String> ts = new TreeSet<String>(); 
  
        // Elements are added using add() method 
        ts.add("Ronaldo"); 
        ts.add("Cris"); 
        ts.add("Elena"); 
    
        String checkString = "Ronaldo"; 
  
        // Checking if string exists in TreeSet
        System.out.println("Contains " + checkString + ts.contains(check)); 
  
        // Printing the first element from the TreeSet 
        System.out.println("First Value " + ts.first()); 
  
        // Printing the last element from the TreeSet 
        System.out.println("Last Value " + ts.last()); 
   
    } 
} 

Output

Contains Ronaldo true
First Value Cris
Last Value Ronaldo

4. Removing values
The values stored in TreeSet can be removed using remove() method.Other methods are also there to remove fist value or last value.

import java.util.*; 
class TreeSetClass { 
  
    public static void main(String[] args) 
    { 
        TreeSet<String> ts = new TreeSet<String>(); 
  
        // Elements are added using add() method
        ts.add("A"); 
        ts.add("B"); 
        ts.add("C"); 
        ts.add("D");
   
        // Removing the element b 
        ts.remove("B"); 
  
        System.out.println("After removing element " + ts); 
  
        // Removing the first element 
        ts.pollFirst(); 
  
        System.out.println("After removing first " + ts); 
  
        // Removing the last element 
        ts.pollLast(); 
  
        System.out.println("After removing last " + ts); 
    } 
} 

Output

After removing element [A,C,D]
After removing first [C,D]
After removing last [C]

Internal Working of TreeSet Class

TreeSet uses the implementation of a self-balancing binary search tree(BST) example Red-Black Tree.The operations performed in like add, remove,pollFirst etc. require only O(log(N)) of time. This happens because in a Red-Black Tree also know as self-balancing tree height of tree is always O(log(N)). Operations such as printing all elements inside the TreeSet takes O(N) time.

Constructors present in TreeSet class

1. TreeSet()
The TreeSet() constructor is used to create an empty TreeSet object in which elements will get stored in default ascending order.

2. TreeSet(Comparator)
This constructor is used to create an empty TreeSet object in which elements will be stored by order specified by Comparator.

3. TreeSet(Collection)
This constructor is used when a conversion is needed from a given Collection object to a TreeSet object.

4. TreeSet(SortedSet)
This constructor is used to convert the given SortedSet object to the TreeSet Object.

Features of TreeSet

  • TreeSet cannot contain duplicate elements.

  • The elements in a TreeSet are sorted as per their natural ordering, or based on a custom Comparator that is supplied at the time of creation of the TreeSet.

  • TreeSet cannot contain null value.

  • TreeSet internally uses a TreeMap to store elements.

  • TreeSet class is not thread-safe. You must explicitly synchronize concurrent access to a TreeSet in a multi-threaded environment.

Other Methods TreeSet class

TreeSet implements SortedSet so it has availability of all methods in Collection, Set and SortedSet interfaces.

  • addAll(Collection c):this method appends all the elements from a given collection of existing set. The elements are added randomnly without following any specific order. eg:
  TreeSet<String> tree = new TreeSet<String>();
       //Another TreeSet 
       TreeSet<String> tree_two = new TreeSet<String>(); 
       // Using addAll() method to Append 
       tree.addAll(tree_two); 
       System.out.println("TreeSet: " + tree); 
  • clear():Removes all of the elements from this set. The set will be empty after this call returns.

      TreeSet<String> tree = new TreeSet<String>(); 
          tree.add("Welcome"); 
          tree.add("To"); 
          // Clearing the TreeSet using clear() method 
          tree.clear();
    
  • isEmpty():Returns true if this set contains no elements or is empty and false for the opposite case.

      TreeSet<String> tree = new TreeSet<String>(); 
          tree.add("Welcome"); 
          tree.add("To"); 
          // Checking if Set is empty
          tree.isEmpty();
    
  • size():Returns the size of the set or the number of elements present in the set.

      TreeSet<String> tree = new TreeSet<String>(); 
          tree.add("Welcome"); 
          tree.add("To"); 
          // Checking size of Set
          tree.size();
    
  • contains(Object o): Return true if given element is present in TreeSet else it will return false.

   TreeSet<String> tree = new TreeSet<String>(); 
       tree.add("Welcome"); 
       tree.add("To"); 
       // Checking if element is in the Set
       tree.contains("To");
  • clone() : The method is used to return a shallow copy of the set, which is just a simple copied set.
   TreeSet<String> tree = new TreeSet<String>(); 
       tree.add("Welcome"); 
       tree.add("To"); 
   
       // Creating a new cloned set 
       TreeSet cloned_set = new TreeSet(); 
 
       // Cloning the set using clone() method 
       cloned_set = (TreeSet)tree.clone(); 

With this article at OPENGENUS, you must have the complete knowledge of TreeSet in Java.