TreeSet

TreeSet is one of the most important implementations of the SortedSet interface in Java that uses a Tree for storage. The ordering of the elements is maintained by a set using their natural ordering whether or not an explicit comparator is provided. This must be consistent with equals if it is to correctly implement the Set interface.

How TreeSet works? #

• TreeSet is basically an implementation of a self-balancing binary search tree like a Red-Black Tree.

• Therefore operations like add, remove, and search takes O(log(N)) time.

• The reason is that in a self-balancing tree, it is made sure that the height of the tree is always O(log(N)) for all the operations.

• Therefore, this is considered as one of the most efficient data structures in order to store the huge sorted data and perform operations on it.

• However, operations like printing N elements in the sorted order take O(N) time.

Features #

• TreeSet implements the SortedSet interface. So, duplicate values are not allowed.

• Objects in a TreeSet are stored in a sorted and ascending order.

• TreeSet does not preserve the insertion order of elements but elements are sorted by keys.

• If we are depending on the default natural sorting order, the objects that are being inserted into the tree should be homogeneous and comparable.

• TreeSet does not allow the insertion of heterogeneous objects. It will throw a classCastException at Runtime if we try to add heterogeneous objects.

• The TreeSet can only accept generic types which are comparable.

• For example, the StringBuffer class implements the Comparable interface

Constructors #

TreeSet() #

This constructor is used to build an empty TreeSet object in which elements will get stored in default natural sorting order. Syntax:

If we wish to create an empty TreeSet with the name ts, then, it can be created as:

TreeSet ts = new TreeSet(); 

TreeSet(Comparator) #

This constructor is used to build an empty TreeSet object in which elements will need an external specification of the sorting order. Syntax: If we wish to create an empty TreeSet with the name ts with an external sorting phenomenon, then, it can be created as:

TreeSet ts = new TreeSet(Comparator comp); 

TreeSet(Collection) #

This constructor is used to build a TreeSet object containing all the elements from the given collection in which elements will get stored in default natural sorting order. In short, this constructor is used when any conversion is needed from any Collection object to TreeSet object.

Syntax: If we wish to create a TreeSet with the name ts, then, it can be created as follows:

TreeSet t = new TreeSet(Collection col);  

TreeSet(SortedSet) #

This constructor is used to build a TreeSet object containing all the elements from the given sortedset in which elements will get stored in default natural sorting order. In short, this constructor is used to convert the SortedSet object to the TreeSet object.

Syntax: If we wish to create a TreeSet with the name ts, then, it can be created as follows:

TreeSet t = new TreeSet(SortedSet s);

Methods #

Operations #

Adding Elements #

In order to add an element to the TreeSet, we can use the add() method. However, the insertion order is not retained in the TreeSet. Internally, for every element, the values are compared and sorted in ascending order. We need to keep a note that duplicate elements are not allowed and all the duplicate elements are ignored. And also, Null values are not accepted by the TreeSet.

// Java code to Illustrate Addition of Elements to TreeSet

// Importing utility classes
import java.util.*;

// Main class
class TFT {

	// Main driver method
	public static void main(String[] args)
	{
		// Creating a Set interface with
		// reference to TreeSet class
		// Declaring object of string type
		Set<String> ts = new TreeSet<>();

		// Elements are added using add() method
		ts.add("Tit");
		ts.add("For");
		ts.add("Tat");

		// Print all elements inside object
		System.out.println(ts);
	}
}

Output

[For, Tit, Tat]

Accessing the Elements #

After adding the elements, if we wish to access the elements, we can use inbuilt methods like contains(), first(), last(), etc.

// Java code to Illustrate Working of TreeSet by
// Accessing the Element of TreeSet

// Importing utility classes
import java.util.*;

// Main class
class TFT {

    // Main driver method
    public static void main(String[] args)
    {
        // Creating a NavigableSet object with
        // reference to TreeSet class
        NavigableSet<String> ts = new TreeSet<>();

        // Elements are added using add() method
        ts.add("Tit");
        ts.add("For");
        ts.add("Tat");

        // Printing the elements inside the TreeSet object
        System.out.println("Tree Set is " + ts);

        String check = "Tat";

        // Check if the above string exists in
        // the treeset or not
        System.out.println("Contains " + check + " "
                + ts.contains(check));

        // Print the first element in
        // the TreeSet
        System.out.println("First Value " + ts.first());

        // Print the last element in
        // the TreeSet
        System.out.println("Last Value " + ts.last());

        String val = "Tit";

        // Find the values just greater
        // and smaller than the above string
        System.out.println("Higher " + ts.higher(val));
        System.out.println("Lower " + ts.lower(val));
    }
}

Output

Tree Set is [For, Tat, Tit]
Contains Tat true
First Value For
Last Value Tit
Higher null
Lower Tat

Removing the Values #

The values can be removed from the TreeSet using the remove() method. There are various other methods that are used to remove the first value or the last value.

// Java Program to Illustrate Removal of Elements
// in a TreeSet

// Importing utility classes
import java.util.*;

// Main class
class TFT {

    // Main driver method
    public static void main(String[] args)
    {
        // Creating an object of NavigableSet
        // with reference to TreeSet class
        // Declaring object of string type
        NavigableSet<String> ts = new TreeSet<>();

        // Elements are added
        // using add() method
        ts.add("Tit");
        ts.add("For");
        ts.add("Tat");
        ts.add("A");
        ts.add("B");
        ts.add("Z");

        // Print and display initial elements of TreeSet
        System.out.println("Initial TreeSet " + ts);

        // Removing a specific existing element inserted
        // above
        ts.remove("B");

        // Printing the updated TreeSet
        System.out.println("After removing element " + ts);

        // Now removing the first element
        // using pollFirst() method
        ts.pollFirst();

        // Again printing the updated TreeSet
        System.out.println("After removing first " + ts);

        // Removing the last element
        // using pollLast() method
        ts.pollLast();

        // Lastly printing the elements of TreeSet remaining
        // to figure out pollLast() method
        System.out.println("After removing last " + ts);
    }
}

Output

Initial TreeSet [A, B, For, Tat, Tit, Z]
After removing element [A, For, Tat, Tit, Z]
After removing first [For, Tat, Tit, Z]
After removing last [For, Tat, Tit]

Iterating through the TreeSet #

There are various ways to iterate through the TreeSet. The most famous one is to use the enhanced for loop. and mostly you would be iterating the elements with this approach while practicing questions over TreeSet as this is most frequently used when it comes to tree, maps, and graphs problems.

// Java Program to Illustrate Working of TreeSet

// Importing utility classes
import java.util.*;

// Main class
class TFT {

    // Main driver method
    public static void main(String[] args)
    {
        // Creating an object of Set with reference to
        // TreeSet class

        // Note: You can refer above media if Tit
        // is confused in programs why we are not
        // directly creating TreeSet object
        Set<String> ts = new TreeSet<>();

        // Adding elements in above object
        // using add() method
        ts.add("Tit");
        ts.add("For");
        ts.add("Tat");
        ts.add("A");
        ts.add("B");
        ts.add("Z");

        // Now we will be using for each loop in order
        // to iterate through the TreeSet
        for (String value : ts)

            // Printing the values inside the object
            System.out.print(value + ", ");

        System.out.println();
    }
}

Output

A, B, For, Tat, Tit, Z,