Java TreeSet

Java TreeSet Tutorial With Example

Java TreeSet class is part of Java’s collections framework. It implements the NavigableSet interface, which in turn extends the SortedSet interface.

The TreeSet class internally uses a TreeMap to store elements. The elements in a TreeSet are sorted according to their natural ordering. You may also provide a custom Comparator to the TreeSet at the time of creation to let it sort the elements based on the supplied comparator.

The SortedSet interface provides functionalities to keep the elements sorted. And the NavigableSet interface provides functionalities to navigate through the SortedSet. For example, finding the element just greater than or just less than a given element, finding the first and last element in the SortedSet etc.

Since the TreeSet class implements NavigableSet interface, it has the functionalities of both – the NavigableSet as well as the SortedSet.

Following are few key points to note about TreeSet in Java 

The Under Lying data structure of TreeSet is balanced tree.

In TreeSet duplicates objects are not allowed.

Insertion order not preserved , but all object will be inserted according to some sorted order.

Heterogeneous objects are not allowed . if we trying to insert Heterogeneous object into TreeSet then we will get run time exception saying ClassCastException.

Null insertion is not allowed.

Modifier and Type Method and Description
boolean add(E e):Adds the specified element to this set if it is not already present.
boolean addAll(Collection<? extends E> c):Adds all of the elements in the specified collection to this set.
E ceiling(E e):Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
void clear():Removes all of the elements from this set.
Object clone():Returns a shallow copy of this TreeSet instance.
Comparator<? super E> comparator():Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
boolean contains(Object o):Returns true if this set contains the specified element.
Iterator<E> descendingIterator():Returns an iterator over the elements in this set in descending order.
NavigableSet<E> descendingSet():Returns a reverse order view of the elements contained in this set.
E first():Returns the first (lowest) element currently in this set.
E floor(E e):Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
SortedSet<E> headSet(E toElement):Returns a view of the portion of this set whose elements are strictly less than toElement.
NavigableSet<E> headSet(E toElement, boolean inclusive):Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
E higher(E e):Returns the least element in this set strictly greater than the given element, or null if there is no such element.
boolean isEmpty():Returns true if this set contains no elements.
Iterator<E> iterator():Returns an iterator over the elements in this set in ascending order.
E last():Returns the last (highest) element currently in this set.
E lower(E e):Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
E pollFirst():Retrieves and removes the first (lowest) element, or returns null if this set is empty.
E pollLast():Retrieves and removes the last (highest) element, or returns null if this set is empty.
boolean remove(Object o):Removes the specified element from this set if it is present.
int size():Returns the number of elements in this set (its cardinality).
Spliterator<E> spliterator():Creates a late-binding and fail-fast Spliterator over the elements in this set.
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive):Returns a view of the portion of this set whose elements range from fromElement to toElement.
SortedSet<E> subSet(E fromElement, E toElement):Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet<E> tailSet(E fromElement):Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
NavigableSet<E> tailSet(E fromElement, boolean inclusive):Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

TreeSet Constructors:

TreeSet treeSet=new TreeSet();

Create an empty TreeSet object where elements will be inserted according to default natural sorting order .

TreeSet treeSet=new TreeSet(Comparator c);

Create an empty TreeSet object where elements will be inserted according to customized sorting order .

TreeSet treeSet=new TreeSet(Collection c);

you can pass any Collection object equivalent TreeSet object are created using this constructor.

TreeSet treeSet=new TreeSet(SortedSet c);

you can convert SortedSet object to TreeSet object using this constructor.

The following example shows how to create a TreeSet and add new elements to it. The TreeSet will be sorted based on the natural ordering of the elements

import java.util.*;

public class TreeSetDemo {

public static void main(String args[]) {

  TreeSet t= new TreeSet();

  t.add(“a”);

  t.add(“A”);

  t.add(“B”);

  t.add(“Z”);

  t.add(“L”);

 // t.add(new Integer(10)); //throws ClassCastException

  System.out.println(“Elements of TreeSet= ” + t);

 // Duplicate elements are ignored

        t.add(“A”);

        System.out.println(“After adding duplicate element \”A\” : ” + t);

        // This will be allowed because it’s in lowercase.

        t.add(“b”);

        System.out.println(“After adding \”b\” : ” + t);

}

}

output:

Elements of TreeSet= [A, B, L, Z, a] 
After adding duplicate element "A" : [A, B, L, Z, a]
After adding duplicate element "A" : [A, B, L, Z, a] 
After adding "b" : [A, B, L, Z, a, b] 
  

If we are depending on default natural sorting order then objects should be homogeneous and comparable . Otherwise we will get runtime Exception ClassCastException

Following program throws ClassCastException because for predefined non comparable classes like StringBuffer, Default natural sorting is not available.

  import java.util.*;

  public class TreeSetDemo {

     public static void main(String args[]) {

     TreeSet t= new TreeSet();

      t.add(new StringBuffer(“A”));

      t.add(new StringBuffer(“Z”));

      t.add(new StringBuffer(“L”));

      t.add(new StringBuffer(“B”));

      t.add(new StringBuffer(“G”));

   // t.add(new Integer(10)); //throws ClassCastException

      System.out.println(“Elements of TreeSet= ” + t);//ClassCastException

}

}

output:

 Exception in thread "main" java.lang.ClassCastException: java.lang.StringBuffer cannot be cast to java.lang.Comparable
        at java.util.TreeMap.compare(TreeMap.java:1290)
        at java.util.TreeMap.put(TreeMap.java:538)
        at java.util.TreeSet.add(TreeSet.java:255)
        at TreeSetDemo.main(TreeSetDemo.java:5) 

An object said to be comparable if and only if corresponding class implements java.lang.Comparable interface.

String class and all wrapper classes are already implements Comparable interface but StringBuffer doesn’t comparable interface.

Hence the above program we get ClassCastException

To overcome this problem we used customized sorting using comparator interface .

Customized sorting :

Comparator interface:

We can use comparator to define our own sorting (customized sorting )

comparator interface presents in java.util package.

comparator interface defines two methods campare and equals.

public int compare(Object obj1, Object obj2)

{

returns -ve if obj1 has to come before obj2.

returns +ve if obj1 has to come after obj2

returns 0 if obj1 & obj2 are equal.

}

public boolean equals();

We saw above StringBuffer class is non comparable not support natural sorting to overcome this problem we can used comparator interface in java in following way.

import java.util.*;

   public class TreeSetDemo {

      public static void main(String args[]) {

      TreeSet t= new TreeSet(new Mycom());

       t.add(new StringBuffer(“A”));

       t.add(new StringBuffer(“Z”));

       t.add(new StringBuffer(“L”));

       t.add(new StringBuffer(“B”));

       t.add(new StringBuffer(“G”));

       System.out.println(“Elements of TreeSet= ” + t);//ClassCastException

 }

 }

 class Mycom implements Comparator{

     public int compare(Object obj1, Object obj2)

     {

         String s1=obj1.toString();

         String s2=obj2.toString();

         return s1.compareTo(s2);

 }

 }

Output:

Elements
of TreeSet= [A, B, G, L, Z]

The example below demonstrates how to create a TreeSet with a custom comparator that sorts the elements in descending order –

import java.util.*;

public class TreeSetDemo {

public static void main(String args[]) {

  SortedSet<String> t= new TreeSet<>(Comparator.reverseOrder());

  /*

            The above TreeSet with the custom Comparator is the concise form of the following:

            SortedSet<String> t = new TreeSet<>(new Comparator<String>() {

                @Override

                public int compare(String s1, String s2) {

                    return s2.compareTo(s1);

                }

            });

        */

  t.add(“a”);

  t.add(“A”);

  t.add(“B”);

  t.add(“Z”);

  t.add(“L”);

 // t.add(new Integer(10)); //throws ClassCastException

  System.out.println(“Elements of TreeSet= ” + t);

}

}

OutPut:

Elements of TreeSet= [a, Z, L, B, A]

import java.util.*;

 public class MyClass  {

     public static void main(String args[]) {

       TreeSet t= new TreeSet(new MyComparator()); 

        t.add(10);

        t.add(0);

        t.add(20);

        t.add(15);

        t.add(20);

       System.out.println(“Elements of TreeSet= ” + t);

}

}

Following program demonstrare all possibilities of comparing object using compare method

class MyComparator implements Comparator{

  public int compare(Object obj1, Object obj2)

  {

      Integer I1=(Integer)obj1;

      Integer I2=(Integer)obj2;

      //return I1.compareTo(I2);//[0, 10, 15, 20]

      // return -I1.compareTo(I2);// [20, 15, 10, 0]

      //return I2.compareTo(I1);//[20, 15, 10, 0]

       //return -I2.compareTo(I1);//[0, 10, 15, 20]

      //return +1;// [10, 0, 20, 15, 20]

     // return -1;//[20, 15, 20, 0, 10]

      return 0;// [10]

     /* if(I1<I2)

      return -1;

      else

      return 0;*/

}

}

Java program to insert String and StringBuffer object into the TreeSet where sorting order is increasing lenth order if two objects have the same length then consder their alphabetical order.

import java.util.*;

 public class TreeSetDemo {

 public static void main(String args[]) {

 SortedSet t= new TreeSet<>(new mycom());

 t.add(“A”);

   t.add(“AA”);

   t.add(“B”);

   t.add(new StringBuffer(“J”));

    t.add(new StringBuffer(“zJ”));

   t.add(“Zxy”);

   t.add(“abcd”);

  // t.add(new Integer(10)); //throws ClassCastException

   System.out.println(“Elements of TreeSet= ” + t);

 }

 }

 class mycom implements Comparator{

     public int compare(Object obj1, Object obj2)

     {

         String s1=obj1.toString();

         String s2=obj2.toString();

         Integer I1=s1.length();

         Integer I2=s2.length();

         if(I1<I2)

         return 1;

         else

         return s1.compareTo(s2);

 }

 }

Output:

Elements of TreeSet= [A, B, J, AA,
zJ, Zxy, abcd]

Accessing the elements of a TreeSet

The example below shows how to

  • size():Find the size of a TreeSet.
  • contains(name):Check if an element exists in a TreeSet.
  • first():Find the first element in the TreeSet.
  • last():Find the last element in the TreeSet.
  • higher(name):Find the element just higher than the given element in the TreeSet.
  • lower(name):Find the element just lower than the given element in the TreeSet.

import java.util.*;

   public class MyClass  {

      public static void main(String args[]) {

        TreeSet friends = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

        friends .add(“Raja”);

        friends .add(“Sudha”);

        friends .add(“Nandu”);

        friends .add(“Vaibhav”);

        friends .add(“Anil”);

        System.out.println(“Elements of TreeSet= ” + friends);

        // Finding size of treeset

        System.out.println(“Size of TreeSet:-“+friends.size());

        // Check if an element exists in the TreeSet

        String s=”Uday”;

        if(friends.contains(s))

        System.out.println(s+”is pressent into TreeSet”);

        else

        System.out.println(s+” is not present into TreeSet”);

        //Find the first element in the TreeSet.

        System.out.println(“First element in treeset is:-“+friends.first());

        //Find the last element in the TreeSet.

        System.out.println(“First element in treeset is:-“+friends.last());

        //:Find the element just higher than the given element in the TreeSet.

        s=”Nandu”;

        System.out.println(“The element just higher than the::” +s+” in the TreeSet is:-“+friends.higher(s));

       //Find the element just lower than the given element in the TreeSet.

      System.out.println(“The element just lower than the::” +s+” in the TreeSet is:-“+friends.lower(s));

 }

 }

output

Elements
of TreeSet= [Anil, Nandu, Raja, Sudha, Vaibhav]
Size of TreeSet:-5
Uday is not present into TreeSet 
First element in treeset is:-Anil
First element in treeset is:-Vaibhav
The element just higher than the::Nandu in the TreeSet is:-Raja
 The element just lower than the::Nandu in the TreeSet is:-Anil    
 

Removing elements from a TreeSet

This example shows how to

  • Remove an element from a TreeSet.
  • Remove all elements that satisfy a given predicate.
  • Remove the first element of the TreeSet.
  • Remove the last element of the TreeSet.

import java.util.TreeSet;

import java.util.*;  

public class RemoveTreeSetElementsDemo {

     public static void main(String[] args) {

         TreeSet numbers = new TreeSet<>();

    numbers.add(10);

    numbers.add(15);

    numbers.add(20);

    numbers.add(21);

    numbers.add(25);

    numbers.add(30);

    numbers.add(42);

    numbers.add(45);

    numbers.add(49);

    numbers.add(50);

    System.out.println(“numbers TreeSet : ” + numbers);

    //romove Elements FROM SET

    boolean isRemoved=numbers.remove(45);

    if(isRemoved)

    System.out.println(“After Removing 45 : ” + numbers);

    // Remove all elements divisible by 5

    numbers.removeIf(number -> number % 5 == 0);

    System.out.println(“After removeIf() : ” + numbers);

    // Retrieve and remove the first element from the TreeSet

    Integer num = numbers.pollFirst();

    System.out.println(“Removed first element ” + num + ” from the TreeSet : ” + numbers);

    // Retrieve and remove the last element from the TreeSet

    num = numbers.pollLast();

    System.out.println(“Removed last element ” + num + ” from the TreeSet : ” + numbers);

}

}

output:

numbers
TreeSet : [10, 15, 20, 21, 25, 30, 42, 45, 49, 50]
After Removing 45 : [10, 15, 20, 21, 25, 30, 42, 49, 50]
After removeIf() : [21, 42, 49]  
Removed first element 21 from the TreeSet : [42, 49] 
Removed last element 49 from the TreeSet : [42] 



Java TreeSet with user defined objects

The example in this section shows how to create a TreeSet of user defined objects.

Since the TreeSet needs to keep the objects sorted, you must either implement the Comparable interface in the user defined class and provide the implementation for the compareTo() method, or provide a custom  Comparator at the time of creation of the TreeSet.

import java.util.Comparator;

import java.util.Objects;

import java.util.SortedSet;

import java.util.TreeSet;

class Employee implements Comparable<Employee> {

    private int id;

    private String name;

    public Employee(int id, String name) {

        this.id = id;

        this.name = name;

    }

    public int getId() {

        return id;

    }

    public void setId(int id) {

        this.id = id;

    }

    public String getName() {

        return name;

    }

    public void setName(String name) {

        this.name = name;

    }

    // Two Employees are equal if their IDs are equal

    @Override

    public boolean equals(Object o) {

        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;

        Employee employee = (Employee) o;

        return id == employee.id;

    }

    @Override

    public int hashCode() {

        return Objects.hash(id);

    }

    // Compare employees based on their IDs

    @Override

    public int compareTo(Employee employee) {

        return this.getId() – employee.getId();

    }

    @Override

    public String toString() {

        return “Employee{” +

                “id=” + id +

                “, name='” + name + ‘\” +

                ‘}’;

    }

}

public class TreeSetUserDefinedObjectExample {

    public static void main(String[] args) {

        // Creating a TreeSet of User Defined Objects.

        /*

           The requirement for a TreeSet of user defined objects is that

           1. Either the class should implement the Comparable interface and provide

              the implementation for the compareTo() method.

           2. Or you should provide a custom Comparator while creating the TreeSet.

        */

        SortedSet<Employee> employees = new TreeSet<>();

        // TreeSet uses the compareTo() method of the Employee class to compare two employees and sort them

        employees.add(new Employee(1010, “Rajeev”));

        employees.add(new Employee(1005, “Sachin”));

        employees.add(new Employee(1008, “Shahid”));

        System.out.println(“Employees (sorted based on Employee class’s compareTo() function)”);

        System.out.println(employees);

        // Providing a Custom Comparator (This comparator compares the employees based on their Name)

        employees = new TreeSet<>(Comparator.comparing(Employee::getName));

        employees.add(new Employee(1010, “Rajeev”));

        employees.add(new Employee(1005, “Sachin”));

        employees.add(new Employee(1008, “Shahid”));

        System.out.println(“\nEmployees (sorted based on the supplied Comparator)”);

        System.out.println(employees);

    }

}

Java TreeSet Example: Movie

Let’s see a TreeSet example where we are adding movies to set and printing all the movies. The elements in TreeSet must be of a Comparable type. String and Wrapper classes are Comparable by default. To add user-defined objects in TreeSet, you need to implement the Comparable interface.

          import java.util.*; 

          class Movie implements Comparable<Movie>{ 

          int id; 

          String name,director;

          public Movie(int id, String name, String director) { 

              this.id = id; 

              this.name = name; 

              this. director = director; 

          }  

          public int compareTo(Movie b) { 

              if(id>b.id){ 

        return 1; 

    }else if(id<b.id){ 

                  return -1; 

              }else{ 

              return 0; 

              } 

          } 

          } 

          public class TreeSetExample { 

          public static void main(String[] args) { 

              Set<Movie> set=new TreeSet<Movie>(); 

              //Creating Movies 

        Movie b1=new Movie(121,”Two State”,”Abhishek Verman”); 

              Movie b2=new Movie(231,”uri “,”Aditya Dhar”);  

              Movie b3=new Movie(241,”3 idiots “,”Rajkumar Hirani”); 

              //Adding Movies to TreeSet 

              set.add(b1); 

              set.add(b2); 

        set.add(b3); 

              //Traversing TreeSet 

              for(Movie b:set){ 

              System.out.println(b.id+” “+b.name+” “+b.director); 

              } 

          } 

          } 

Output:

121 Two State Abhishek Verman
231 uri  Aditya Dhar 
241 3 idiots  Rajkumar Hirani 

Leave a Reply