TreeSet
Suppose you need a collection that stores unique elements and automatically keeps them in sorted order. HashSet gives you uniqueness but no ordering guarantee. LinkedHashSet gives you uniqueness with insertion order. But when sorted order itself is part of the requirement, Java provides TreeSet.
TreeSet is a Set implementation based on a tree structure. It stores unique elements according to their natural ordering or according to a Comparator supplied when the TreeSet is created.
Core Idea: TreeSet gives you a collection of unique elements that remains sorted automatically.
Why Does TreeSet Exist?
Imagine an application maintaining a list of employee ages. You do not want duplicate ages, and you also want the values available from smallest to largest without manually sorting them every time.
Set<Integer> ages = new TreeSet<>(); ages.add(35); ages.add(22); ages.add(29); ages.add(22); ages.add(41); System.out.println(ages);
The duplicate 22 is ignored, and the remaining values are maintained in ascending order.
Simple analogy: Think of TreeSet as a receptionist who keeps a unique guest register and automatically rearranges the names according to a defined sorting rule.
TreeSet Hierarchy
TreeSet implements the NavigableSet interface, which extends SortedSet and Set.
Collection
|
+-- Set
|
+-- SortedSet
|
+-- NavigableSet
|
+-- TreeSet
This hierarchy explains why TreeSet provides more than basic Set operations. It also provides methods for navigating around sorted values.
Creating a TreeSet
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Set<Integer> numbers =
new TreeSet<>();
numbers.add(40);
numbers.add(10);
numbers.add(30);
numbers.add(20);
System.out.println(numbers);
}
}
The output is maintained in ascending order according to Integer's natural ordering.
Natural Ordering
When no Comparator is supplied, TreeSet uses the natural ordering of its elements. For numbers, this means ascending numerical order. For Strings, it generally follows their natural lexicographical ordering.
Set<String> languages =
new TreeSet<>();
languages.add("Python");
languages.add("Java");
languages.add("C#");
languages.add("JavaScript");
System.out.println(languages);
The elements are returned according to String's natural ordering rather than their insertion order.
Important: TreeSet does not preserve insertion order. Its ordering comes from natural ordering or the Comparator supplied to the Set.
Adding Elements
TreeSet uses the familiar add() method.
Set<Integer> numbers =
new TreeSet<>();
numbers.add(50);
numbers.add(20);
numbers.add(40);
numbers.add(10);
System.out.println(numbers);
You can insert values in any order. TreeSet maintains the required sorted arrangement internally.
Duplicate Elements
TreeSet follows Set semantics, so duplicate elements are not stored.
Set<Integer> numbers =
new TreeSet<>();
System.out.println(numbers.add(10));
System.out.println(numbers.add(10));
The first add() returns true. The second returns false because the Set already contains an element considered equivalent according to the TreeSet's ordering rules.
Important Difference: For TreeSet, the ordering mechanism is central to determining whether two elements occupy the same sorted-set position. With natural ordering, compareTo() returning zero is treated as equivalent for Set purposes.
Removing Elements
Set<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.remove(20);
System.out.println(numbers);
The remove() method searches according to the TreeSet's ordering mechanism and removes the matching element when present.
Checking for an Element
Set<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
if (numbers.contains(20)) {
System.out.println("20 exists");
}
Because TreeSet maintains a balanced search-tree structure, fundamental search operations are typically O(log n).
TreeSet Performance
| Operation | Typical Complexity | Purpose |
|---|---|---|
| add() | O(log n) | Add an element while maintaining sorted order. |
| remove() | O(log n) | Remove an element while preserving tree ordering. |
| contains() | O(log n) | Search for an element. |
| first() | O(1) typically | Retrieve the smallest element. |
| last() | O(1) typically | Retrieve the largest element. |
| Iteration | O(n) | Traverse elements in sorted order. |
TreeSet generally provides logarithmic-time basic modification and search operations because it is based on a balanced tree structure.
first() and last()
TreeSet makes it easy to access the smallest and largest elements.
TreeSet<Integer> numbers =
new TreeSet<>();
numbers.add(40);
numbers.add(10);
numbers.add(30);
numbers.add(20);
System.out.println(numbers.first());
System.out.println(numbers.last());
first() returns the smallest element, while last() returns the largest element according to the Set's ordering.
pollFirst() and pollLast()
Because TreeSet implements NavigableSet, you can also remove and return the smallest or largest element.
TreeSet<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
System.out.println(numbers.pollFirst());
System.out.println(numbers.pollLast());
System.out.println(numbers);
pollFirst() removes the smallest element, while pollLast() removes the largest element.
lower(), floor(), ceiling(), and higher()
These four methods are among the most useful features of TreeSet. They allow you to navigate around a target value without manually scanning the Set.
| Method | Meaning |
|---|---|
| lower(value) | Greatest element strictly less than the given value. |
| floor(value) | Greatest element less than or equal to the given value. |
| ceiling(value) | Smallest element greater than or equal to the given value. |
| higher(value) | Smallest element strictly greater than the given value. |
TreeSet<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
System.out.println(numbers.lower(30));
System.out.println(numbers.floor(30));
System.out.println(numbers.ceiling(30));
System.out.println(numbers.higher(30));
For the value 30, lower() returns 20, floor() returns 30, ceiling() returns 30, and higher() returns 40.
Memory Trick: Lower and higher are strict. Floor and ceiling can include the target value itself.
Descending Order
TreeSet can provide a reverse-order view using descendingSet().
TreeSet<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
NavigableSet<Integer> descending =
numbers.descendingSet();
System.out.println(descending);
The original TreeSet remains ordered according to its normal comparator, while the returned view provides descending traversal.
Descending Iterator
You can also iterate through the TreeSet in reverse order.
TreeSet<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
Iterator<Integer> iterator =
numbers.descendingIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
This is useful when an algorithm needs values from largest to smallest.
headSet(), tailSet(), and subSet()
TreeSet can create sorted views over ranges of elements. These operations are extremely useful when working with intervals and boundaries.
headSet()
TreeSet<Integer> numbers =
new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
SortedSet<Integer> result =
numbers.headSet(30);
System.out.println(result);
The normal headSet(value) view contains elements strictly less than the specified value.
tailSet()
SortedSet<Integer> result =
numbers.tailSet(30);
System.out.println(result);
The normal tailSet(value) view contains elements greater than or equal to the specified value.
subSet()
SortedSet<Integer> result =
numbers.subSet(20, 40);
System.out.println(result);
The standard SortedSet subSet(from, to) range includes the lower boundary and excludes the upper boundary.
Boundary Rule: For the traditional SortedSet range methods, the lower endpoint is inclusive and the upper endpoint is exclusive.
NavigableSet Range Methods
NavigableSet provides overloaded range methods that allow you to explicitly control whether each boundary is inclusive.
NavigableSet<Integer> result =
numbers.subSet(
20,
true,
40,
true
);
System.out.println(result);
Here, both 20 and 40 are included because both boundary flags are true.
| Method | Purpose |
|---|---|
| headSet(value) | Elements less than value. |
| headSet(value, inclusive) | Elements less than value, optionally including value. |
| tailSet(value) | Elements greater than or equal to value. |
| tailSet(value, inclusive) | Elements greater than value, optionally including value. |
| subSet(from, to) | Range with lower bound inclusive and upper bound exclusive. |
| subSet(from, fromInclusive, to, toInclusive) | Range with explicit boundary control. |
Using a Comparator
Natural ordering is not always what your application needs. TreeSet allows you to provide a Comparator to define a custom ordering.
TreeSet<String> languages =
new TreeSet<>(
Comparator.reverseOrder()
);
languages.add("Java");
languages.add("C#");
languages.add("Python");
System.out.println(languages);
Now the elements are maintained in descending natural order.
Custom Sorting with Comparator
You can define more specific ordering rules as well.
TreeSet<String> languages =
new TreeSet<>(
(a, b) -> b.compareTo(a)
);
languages.add("Java");
languages.add("Spring");
languages.add("SQL");
System.out.println(languages);
The Comparator determines the ordering used by the tree.
Design Insight: A Comparator does more than control display order in TreeSet. Its comparison result also influences which elements the Set considers equivalent.
TreeSet and Custom Objects
When storing custom objects, TreeSet needs a way to determine their ordering. You can either make the class implement Comparable or provide a Comparator to the TreeSet.
Using Comparable
class Employee implements Comparable<Employee> {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int compareTo(Employee other) {
return Integer.compare(this.id, other.id);
}
@Override
public String toString() {
return id + " - " + name;
}
}
The compareTo() method defines the natural ordering of Employee objects by ID.
Set<Employee> employees =
new TreeSet<>();
employees.add(new Employee(103, "Priya"));
employees.add(new Employee(101, "Bibhu"));
employees.add(new Employee(102, "Rahul"));
System.out.println(employees);
The employees are maintained according to their IDs.
Using Comparator
If you do not want the class itself to define the ordering, provide a Comparator when creating the TreeSet.
TreeSet<Employee> employees =
new TreeSet<>(
Comparator.comparing(
Employee::getName
)
);
This approach is useful when the same domain object needs to be sorted in different ways in different parts of an application.
Comparable vs Comparator
| Aspect | Comparable | Comparator |
|---|---|---|
| Method | compareTo() | compare() |
| Where ordering is defined | Inside the class | Outside the class |
| Primary purpose | Natural ordering | Custom or alternative ordering |
| Multiple sorting strategies | Usually one natural ordering | Many Comparator strategies possible |
| TreeSet usage | Can be used when elements implement Comparable | Can be supplied directly to TreeSet |
TreeSet and Equality
One of the most important differences between TreeSet and HashSet is how uniqueness is determined.
HashSet primarily relies on hashCode() and equals(). TreeSet relies on its ordering comparison, using compareTo() for natural ordering or compare() for a supplied Comparator.
TreeSet<String> names =
new TreeSet<>(
String.CASE_INSENSITIVE_ORDER
);
names.add("Java");
names.add("java");
System.out.println(names.size());
Because the Comparator treats Java and java as equivalent for ordering purposes, the TreeSet does not keep both values.
Critical Rule: For a SortedSet, the ordering should generally be consistent with equals when possible. If it is not, the Set can consider two objects equivalent even though equals() says they are different.
TreeSet and Null Values
A TreeSet using natural ordering generally cannot store null because null cannot be naturally compared with normal non-null elements.
TreeSet<String> names =
new TreeSet<>();
// Avoid adding null when natural
// ordering is being used.
// names.add(null);
With a custom Comparator that explicitly handles null, behavior can differ, but allowing null in a sorted collection should be a deliberate design decision.
TreeSet and Duplicate Custom Objects
Suppose employees are ordered only by department. If two employees belong to the same department, a Comparator that returns zero for them may cause TreeSet to treat them as equivalent and retain only one.
Comparator<Employee> byDepartment =
Comparator.comparing(
Employee::getDepartment
);
TreeSet<Employee> employees =
new TreeSet<>(byDepartment);
This can be surprising if the business requirement is to keep every employee. The Comparator must distinguish elements sufficiently for the intended Set semantics.
Practical Warning: Never choose a Comparator only because it sorts nicely. In TreeSet, compare() returning zero means the elements are treated as duplicates for Set purposes.
TreeSet vs HashSet vs LinkedHashSet
| Feature | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| Duplicates | Not allowed | Not allowed | Not allowed |
| Insertion order | Not guaranteed | Maintained | Not its ordering model |
| Sorted order | No | No | Yes |
| Average/basic add | O(1) | O(1) | O(log n) |
| Average/basic contains | O(1) | O(1) | O(log n) |
| Ordering mechanism | Hashing | Hashing plus insertion links | Comparable or Comparator |
| Typical use | Unique elements | Unique elements in insertion order | Unique elements in sorted order |
When Should You Use TreeSet?
TreeSet is a strong choice when sorted uniqueness is a core requirement rather than something you want to perform as a separate operation.
- Maintain unique numbers in ascending or descending order.
- Maintain unique names according to a defined alphabetical ordering.
- Quickly find the smallest or largest value.
- Find values immediately below or above a target using lower(), floor(), ceiling(), or higher().
- Work with sorted ranges using headSet(), tailSet(), or subSet().
- Maintain custom objects according to a domain-specific ordering.
When Should You Not Use TreeSet?
- Use HashSet when you only need uniqueness and do not need ordering.
- Use LinkedHashSet when insertion order matters but sorting does not.
- Use ArrayList when duplicate values and index-based access are important.
- Do not use TreeSet simply because you can sort later; its O(log n) operations may be unnecessary when ordering is not continuously required.
Real-World Example: Unique Scores
Imagine a leaderboard system that needs the unique scores currently achieved by players and must always access them in sorted order.
TreeSet<Integer> scores =
new TreeSet<>();
scores.add(850);
scores.add(920);
scores.add(780);
scores.add(920);
scores.add(990);
System.out.println(scores);
System.out.println(
"Lowest: " + scores.first()
);
System.out.println(
"Highest: " + scores.last()
);
The duplicate score is removed automatically, while first() and last() provide immediate access to the smallest and largest scores.
Real-World Example: Finding Nearby Values
TreeSet becomes especially powerful when you need values close to a target.
TreeSet<Integer> prices =
new TreeSet<>();
prices.add(100);
prices.add(200);
prices.add(300);
prices.add(400);
int target = 250;
System.out.println(
"Lower: " + prices.lower(target)
);
System.out.println(
"Higher: " + prices.higher(target)
);
For the target 250, TreeSet can immediately provide the closest lower and higher values according to the sorted ordering.
This kind of navigation is useful in scheduling, pricing, ranking, range queries, and many algorithmic problems.
Common Beginner Mistakes
- Expecting insertion order: TreeSet maintains sorted order, not insertion order.
- Expecting O(1) operations: TreeSet's fundamental search, insertion, and removal operations are typically O(log n).
- Using TreeSet without a valid ordering: Elements must have a compatible natural ordering or a suitable Comparator.
- Ignoring Comparator behavior: compare() returning zero means TreeSet treats the elements as equivalent.
- Assuming compareTo() and equals() are interchangeable: They serve different contracts, although consistent ordering is strongly preferred.
- Adding null with natural ordering: Natural ordering generally cannot compare null with ordinary elements.
- Choosing TreeSet when sorting is rarely needed: HashSet plus a separate sort may sometimes better fit the workload.
- Assuming TreeSet is thread-safe: TreeSet is not inherently synchronized.
Best Practices
- Use TreeSet when maintaining sorted unique elements is a continuous requirement.
- Use the NavigableSet API when you need boundary and neighbor operations.
- Use Comparable for a natural ordering that belongs to the domain type.
- Use Comparator when different sorting strategies are needed.
- Design Comparators carefully so that compare() returning zero matches the intended uniqueness semantics.
- Avoid mutable state that can invalidate the ordering assumptions of elements already stored in the Set.
- Use HashSet or LinkedHashSet instead when sorted ordering provides no value.
Interview Insights
Question: What is TreeSet?
Answer: TreeSet is a NavigableSet implementation that stores unique elements in sorted order using natural ordering or a supplied Comparator.
Question: What is the time complexity of TreeSet operations?
Answer: Basic add(), remove(), and contains() operations are typically O(log n) because TreeSet uses a balanced tree structure.
Question: What is the difference between HashSet and TreeSet?
Answer: HashSet provides hash-based unique storage without a guaranteed order, while TreeSet maintains unique elements according to sorted ordering and typically provides O(log n) basic operations.
Question: What is the difference between LinkedHashSet and TreeSet?
Answer: LinkedHashSet maintains insertion order, while TreeSet maintains sorted order according to natural ordering or a Comparator.
Question: What happens when compareTo() returns zero?
Answer: In a TreeSet using natural ordering, the elements are treated as equivalent for Set purposes, so the second element is not added.
Question: What do lower(), floor(), ceiling(), and higher() do?
Answer: They find neighboring values around a target: lower is strictly smaller, floor is smaller or equal, ceiling is larger or equal, and higher is strictly larger.
Quick Revision
| Concept | Key Point |
|---|---|
| TreeSet | NavigableSet implementation for unique sorted elements. |
| Ordering | Natural ordering or a supplied Comparator. |
| Duplicates | Not allowed. |
| add() | Typically O(log n). |
| contains() | Typically O(log n). |
| remove() | Typically O(log n). |
| first() | Returns the smallest element. |
| last() | Returns the largest element. |
| lower() | Greatest element strictly smaller than the target. |
| floor() | Greatest element smaller than or equal to the target. |
| ceiling() | Smallest element greater than or equal to the target. |
| higher() | Smallest element strictly greater than the target. |
| HashSet alternative | Use when uniqueness matters but sorted order does not. |
| LinkedHashSet alternative | Use when uniqueness plus insertion order is required. |
TreeSet completes an important part of the Set family: HashSet focuses on efficient uniqueness, LinkedHashSet adds predictable insertion order, and TreeSet adds continuous sorted ordering and powerful navigation operations. Once you understand when ordering is a requirement rather than merely a presentation detail, choosing between these Set implementations becomes much easier. In the next chapter, we will move into the Map family and explore HashMap, one of the most frequently used collections in Java applications.