TreeSet

TreeSet is an implementation of the SortedSet interface, introduced in JDK 1.2. It is used to store unique elements in a sorted order.

Features

The elements in the TreeSet are sorted by default in ascending order.
We can add only the objects that are comparable type to TreeSet otherwise TreeSet throws ClassCastException.
The TreeSet doesn't support heterogeneous collection.
Null cannot be inserted in TreeSet.
The Elements of the TreeSet compare themselves based on the comparable interface. Such comparison is known as mutual comparison.
The TreeSet works on the Binary data structure.
When you add an object into TreeSet internally calls compareTo() method.

TreeSet Constructors

1. No-argument Constructor

Example:

TreeSet s1 = new TreeSet();

Creates an empty TreeSet which arranges the element in natural sorting order.
The TreeSet allows only mutually comparable objects otherwise it throws ClassCastException.

2. Comparable Type Constructor

Example:

TreeSet s1 = new TreeSet(Comparator c);

Let's say 'c1' is the object of comparable type.
Creates an empty TreeSet where the elements are not arranged in a natural sorting order but they arranged as per the implementation of comparator type.

3. SorteSet Type Constructor

Example:

TreeSet s1 = new TreeSet(SortedSet x);

Let's say 'x' is an object of type sorted set.
Creates an element of a specified sorted set.

4. Collection Type Constructor

Example:

TreeSet s1 = new TreeSet(Collection c);

Let's say 's1' is the collection of n elements.
Creates a TreeSet with elements of collection type the elements must be mutually comparable type otherwise it throws ClassCastException.

Example: Storing Interger Values

package quipoin;

import java.util.TreeSet;

public class Demo {
	public static void main(String[] args) {
		TreeSet<Integer> treeSet = new TreeSet<>();
		treeSet.add(30);
		treeSet.add(10);
		treeSet.add(50);
		treeSet.add(20);
		treeSet.add(60);
		treeSet.add(40);

		System.out.println("The elemens of TreeSet are:");
		for (int num : treeSet) { // foreach loop
			System.out.println(num);
		}
	}
}

Output:

The elemens of TreeSet are:
10
20
30
40
50
60

Explanation

We can observe that elements are randomly inserted into TreeSet but the output is in order wise. TreeSet internally calls the compareTo() method.
CompareTo () method returns ‘-1’ when the value is lesser than, ‘+1’ when the value is greater than and returns ‘0’ when the value is equal.

Example 2: Storing String Values

package quipoin;

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

public class Sample {
	public static void main(String[] args) {

		TreeSet<String> ts = new TreeSet<>();
		ts.add("Banana");
		ts.add("Cat");
		ts.add("Apple");

		System.out.println("Elements of TreeSet are:");
		Iterator<String> t = (Iterator<String>) ts.iterator();
		// traversing elements using iterator() method;
		while (t.hasNext()) {
			System.out.println(t.next());
		}
	}
}

Output:

Elements of TreeSet are:
Apple
Banana
Cat

Explanation

In the above example, String types of objects are sorted based on the ASCII values.
All the wrapper class implements comparable interface and the compareTo() method is overridden by those respective class.

Comparison: HashSet Vs LinkedHashSet Vs TreeSet

Feature	HashSet	LinkedHashSet	TreeSet
Underlying DS	HashTable	HashTable + LinkedList	Red-Black Tree
Order Maintained ?	No order	Insertion order	Sorted order (ascending)
Allows Duplicates ?	No	No	No
Allows Null ?	Yes (one)	Yes (one)	No
Sorting	No Sorting	No Sorting	Sorted
When to use ?	Fastest for search & insert	When insertion order matters	When sorting is required

Two Minute Drill

TreeSet is best suited when you need sorted unique elements.
It automatically arranges elements in ascending order.
Null values are not allowed due to the sorting mechanism.
It provides O(log n) time complexity for basic operations like add(), remove(), and contains().