TreeSet in Java

TreeSet is one of the most important classes in Java Collections Framework.

It is part of the java.util package and implements the NavigableSet and SortedSet interfaces.

TreeSet is used when you need:

• Unique elements
• Sorted order
• Fast searching
• Range-based operations (ceiling, floor, higher, lower)

What is TreeSet in Java?

A TreeSet is a collection that:

• Stores unique elements (no duplicates)
• Maintains sorted order (ascending by default)
• Stores elements in a Red-Black Tree (self-balancing BST)
• Does not allow null (NullPointerException)
• Supports fast range operations
• Offers O(log n) performance for operations

Where TreeSet Fits in Collection Hierarchy

Iterable
   └── Collection
          └── Set
               └── SortedSet
                      └── NavigableSet
                             └── TreeSet

Interfaces Implemented By TreeSet:

• Set
• SortedSet
• NavigableSet
• Cloneable
• Serializable

Internal Working of TreeSet (IMPORTANT for interviews)

TreeSet uses a Red-Black Tree (self-balancing binary search tree).

Each element becomes a node in the tree.

The tree stays balanced after every insertion and deletion.

Internal Diagram

          (20)
        /      \\
     (10)      (30)
       \\       /   \\
       (15) (25)  (40)

• Left subtree < root
• Right subtree > root
• Always balanced → height = O(log n)

Key Features of TreeSet

• Stores unique elements (no duplicates)
• Keeps elements sorted automatically
• Based on Red-Black Tree
• Allows range operations (ceiling, floor, higher, lower)
• Does NOT allow null
• Slower than HashSet & LinkedHashSet
• Provides subSet(), headSet(), tailSet()

Default Sorting in TreeSet

• Natural ordering → For integers, it is ascending
• You can use a custom Comparator

Example:

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

Custom Sorting Example (Descending)

TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a);

Constructors of TreeSet

1. Default constructor (Natural Ordering)

Creates an empty TreeSet that sorts elements in natural order.

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

2. Constructors With Comparator

Creates a TreeSet with a custom sorting order.

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

3. Create from another Collection

Creates a TreeSet containing elements from another collection and sorts them.

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

4. Create from SortedSet

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

Commonly Used TreeSet Methods

1. Add Methods

add(E e)

Adds an element. TreeSet automatically sorts elements and ignores duplicates.

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

set.add(50);
set.add(10);
set.add(30);

System.out.println(set);

Output:

[10, 30, 50]

addAll(Collection c)

Adds all elements from another collection and sorts them.

set.addAll(list);

2. Search / Check Methods

contains(Object o)

Checks if an element exists.

set.contains("Java");

isEmpty()

Checks if TreeSet is empty.

set.isEmpty();

size()

Returns total elements.

set.size();

3. Remove Methods

remove(Object o)

Removes a specific element.

set.remove("Python");

clear()

Removes all elements.

set.clear();

4. Navigation Methods (TreeSet Special Feature)

ceiling(E e)

Smallest element ≥ given value.

set.ceiling(40);

floor(E e)

Largest element ≤ given value.

set.floor(40);

higher(E e)

Next higher element (strictly > element).

set.higher(30);

lower(E e)

Next lower element (strictly < element).

set.lower(30);

5. Boundary Elements

first()

Returns smallest element.

set.first();

last()

Returns largest element.

set.last();

6. Remove Boundary Elements

pollFirst()

Removes + returns smallest element.

set.pollFirst();

pollLast()

Removes + returns largest element.

set.pollLast();

7. Range Views (Important)

subSet(a, b)

Elements from a (inclusive) to b (exclusive).

set.subSet(10, 40);

More precise variant:

set.subSet(10, true, 40, false);

headSet(x)

All elements less than x.

set.headSet(30);

tailSet(x)

All elements greater than or equal to x.

set.tailSet(30);

8. descendingSet() — Reverse Order

System.out.println(set.descendingSet());

Output:

[50, 30, 10]

9. descendingIterator()

Iterator<Integer> itr = set.descendingIterator();
while (itr.hasNext()) {
    System.out.println(itr.next());
}

10. Iteration

Using Iterator

Iterator<String> itr = set.iterator();
while (itr.hasNext()) {
    System.out.println(itr.next());
}

Using Enhanced For Loop

for (String s : set) {
    System.out.println(s);
}

Example Program: TreeSet Basic

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();

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

        System.out.println(set);
    }
}

Output:

[10, 20, 30, 40]

Time Complexity of TreeSet

TreeSet vs HashSet vs LinkedHashSet

Advantages of TreeSet

• Maintains sorted order
• Unique elements
• Range-query methods (ceiling, floor, higher, lower)
• Ideal for sorted data
• Custom sorting supported via Comparator

Disadvantages of TreeSet

• Slower than HashSet
• No null values
• Insertion and deletion cost is O(log n)
• Higher memory usage

Best Use Cases of TreeSet

TreeSet is ideal when you need:

• Automatic sorting
• Unique + sorted elements
• Range-based searches
• Leaderboards
• Sorted employee records
• Unique sorted names
• Autocomplete suggestions

Examples:

• Sorted names list
• Student ranks
• Auto-suggestions
• Unique sorted product IDs

Real-World Example

Autocomplete Search

Search results need to be sorted.

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

dictionary.add("car");
dictionary.add("carbon");
dictionary.add("cat");
dictionary.add("dog");

System.out.println(dictionary.tailSet("ca"));

Output:

[car, carbon, cat, dog]

Points to Remember

• TreeSet → Unique + Sorted Set
• Backed by Red-Black Tree
• No duplicates, no nulls
• Great for sorted data, range queries, and fast search
• Slower than HashSet/LinkedHashSet
• Supports ceiling(), floor(), higher(), lower()