TreeSet

#Introduction

TreeSet is the Set implementation to know when the requirement is:

Unique elements + sorted order + range/navigation operations

Unlike HashSet and LinkedHashSet, TreeSet does not use hashing. Its core is a balanced Red-Black Tree.

#What is TreeSet?

TreeSet is a sorted implementation of the Set interface.

Package:

java.util.TreeSet

Declaration:

public class TreeSet<E>
        extends AbstractSet<E>
        implements NavigableSet<E>,
                   Cloneable,
                   Serializable

#Key Characteristics

#The Main Difference from HashSet

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

set.add(50);
set.add(10);
set.add(40);
set.add(20);

10
20
40
50

The elements are automatically ordered.

#How Does TreeSet Maintain Order?

This is the key internal concept. TreeSet uses a tree-based structure backed by TreeMap.

Why a Red-Black Tree?

A normal Binary Search Tree can become unbalanced. Inserting 10, 20, 30, 40 in order makes it effectively a linked list, and search becomes O(n):

A Red-Black Tree automatically maintains approximate balance, so the height remains O(log n):

Therefore search, insert and delete are all O(log n).

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing Binary Search Tree with additional colour information. Each node conceptually holds:

The colouring rules ensure the tree doesn't become excessively unbalanced. You don't need to memorize the complete balancing algorithm unless specifically asked, but you should understand why it exists.

#TreeSet Ordering

There are two ways to define ordering.

1. Natural ordering — Comparable

TreeSet<Integer> set = new TreeSet<>();

Integer already implements Comparable.

2. Custom ordering — Comparator

TreeSet<Integer> set = new TreeSet<>(Comparator.reverseOrder());

50
40
30
20
10

Comparable vs Comparator

This is a major interview topic.

Comparable — the class defines its own natural ordering:

class Employee implements Comparable<Employee> {

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);
    }
}

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

Comparator — ordering is supplied externally:

Comparator<Employee> byName = Comparator.comparing(Employee::getName);

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

Natural Ordering Example

TreeSet<String> set = new TreeSet<>();

set.add("Zebra");
set.add("Apple");
set.add("Mango");
set.add("Banana");

Apple
Banana
Mango
Zebra

Strings use their natural ordering.

#How TreeSet Detects Duplicates

TreeSet Doesn't Use equals() to Determine Uniqueness

This is one of the most important TreeSet interview questions. For ordering and duplicate determination, TreeSet uses compareTo() or Comparator.compare().

If compare(a, b) == 0, TreeSet treats them as equivalent for Set purposes, so the element is not added as a separate entry.

TreeSet<Integer> set = new TreeSet<>();

set.add(10);
set.add(10);

The second 10 isn't added because compare(10, 10) == 0.

The Big Difference: HashSet vs TreeSet

This distinction explains most TreeSet interview questions.

Dangerous Comparator Example

class Employee {
    int id;
    String name;
}

Comparator<Employee> comparator = Comparator.comparing(Employee::getName);

Now Employee 101 → John and Employee 102 → John: the comparator returns 0, so TreeSet considers them equivalent. Only one may be stored — even though their IDs differ.

#NavigableSet Methods

TreeSet implements NavigableSet, which gives us powerful navigation methods. These are frequently asked in interviews.

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(10, 20, 30, 40));

lower()

Returns the greatest element strictly less than the given element.

set.lower(30);   // 20

floor()

Returns the greatest element less than or equal to the given element.

set.floor(30);   // 30
set.floor(35);   // 30

higher()

Returns the smallest element strictly greater than the given element.

set.higher(30);   // 40

ceiling()

Returns the smallest element greater than or equal to the given element.

set.ceiling(30);   // 30
set.ceiling(35);   // 40

Easy Way to Remember

For 10 20 30 40, around 30:

first() and last()

Return the smallest and largest elements. For 10, 20, 30, 40: first() → 10, last() → 40. Complexity: O(log n).

pollFirst() and pollLast()

Unlike first() and last(), these remove the element. set.pollFirst() removes the smallest; set.pollLast() removes the largest.

#Range Views

One of TreeSet's biggest advantages over HashSet: subSet(), headSet(), tailSet().

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));

subSet()

set.subSet(20, 50);   // 20, 30, 40

By default: from → inclusive, to → exclusive. You can control the boundaries explicitly:

set.subSet(20, true, 50, true);   // 20, 30, 40, 50

headSet()

Returns elements before a specified point. By default the point is excluded:

set.headSet(30);         // 10, 20
set.headSet(30, true);   // 10, 20, 30

tailSet()

Returns elements from a specified point onward. By default the point is included:

set.tailSet(30);   // 30, 40, 50

Range Methods Return Views

This is an excellent interview question.

NavigableSet<Integer> subset = set.subSet(20, 50);

The subset is generally a view backed by the original TreeSet, not an independent copy. Changes to the view can affect the original Set, subject to the range restrictions.

#Null Handling

Generally, TreeSet does not allow null when using natural ordering.

TreeSet<Integer> set = new TreeSet<>();

set.add(null);

NullPointerException

Why? The tree needs to compare elements to determine their position. There is no natural ordering between null and an Integer.

Can TreeSet Store Null with a Comparator?

Potentially yes, if the supplied comparator explicitly defines how null should be ordered:

TreeSet<String> set = new TreeSet<>(
        Comparator.nullsFirst(Comparator.naturalOrder())
);

Now null can be ordered before non-null values.

#Custom Objects

class Employee {
    int id;
    String name;
}

This will not work automatically:

TreeSet<Employee> set = new TreeSet<>();

set.add(new Employee());

unless Employee provides natural ordering or the TreeSet has a Comparator. Otherwise Java cannot compare Employee A vs Employee B, and a comparison-related exception (ClassCastException) can occur.

Using Comparable

class Employee implements Comparable<Employee> {

    int id;

    Employee(int id) {
        this.id = id;
    }

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);
    }
}

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

employees.add(new Employee(103));
employees.add(new Employee(101));
employees.add(new Employee(102));

101
102
103

Using Comparator

You don't need to modify Employee:

TreeSet<Employee> employees = new TreeSet<>(Comparator.comparingInt(e -> e.id));

This is often preferable when you need different sorting strategies — by ID, by name, by salary, by joining date — each with a different Comparator.

TreeSet and Mutable Objects

Another advanced interview trap. Suppose the ordering depends on employee.salary. You insert the Employee, then later:

employee.salary = 900000;

The object's ordering key changed, but the tree structure wasn't automatically rebuilt. Now operations may behave unexpectedly.

#Thread Safety and Performance

Thread Safety

TreeSet is not thread-safe. For synchronized access:

SortedSet<Integer> set = Collections.synchronizedSortedSet(new TreeSet<>());

For concurrent sorted collections, Java provides specialized options such as ConcurrentSkipListSet.

Performance

TreeSet sacrifices HashSet's average O(1) lookup in exchange for sorted order and navigation.

HashSet vs LinkedHashSet vs TreeSet

#When to Use TreeSet

Use TreeSet when you need unique elements + sorted order + navigation/range queries.

When NOT to Use TreeSet

#Decision Framework

Final Mental Model