Java TreeSet

A TreeSet is a NavigableSet implementation that keeps elements sorted using a Red-Black tree. All operations are O(log n), making it ideal when you need sorted unique elements.

How TreeSet Works

TreeSet uses a self-balancing Red-Black tree internally:

• Elements are sorted using natural ordering or a custom Comparator
• The tree stays balanced, ensuring O(log n) operations
• In-order traversal gives sorted output

Key Characteristics

Creating a TreeSet

import java.util.TreeSet;
import java.util.Set;
import java.util.Comparator;

// Natural ordering (elements must implement Comparable)
TreeSet<Integer> numbers = new TreeSet<>();
TreeSet<String> names = new TreeSet<>();

// Custom comparator (reverse order)
TreeSet<Integer> descending = new TreeSet<>(Comparator.reverseOrder());

// Custom comparator for objects
TreeSet<String> byLength = new TreeSet<>(
    Comparator.comparingInt(String::length)
);

// From existing collection (sorts automatically)
List<Integer> list = Arrays.asList(5, 2, 8, 1, 9);
TreeSet<Integer> sorted = new TreeSet<>(list); // {1, 2, 5, 8, 9}

Click Run to execute your code

NavigableSet Methods

TreeSet implements NavigableSet, providing powerful navigation operations:

TreeSet<Integer> set = new TreeSet<>();
set.addAll(Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100));

// Boundary elements
Integer first = set.first();   // 10 (smallest)
Integer last = set.last();     // 100 (largest)

// Floor/Ceiling (closest elements)
Integer floor = set.floor(35);     // 30 (<=35)
Integer ceiling = set.ceiling(35); // 40 (>=35)
Integer lower = set.lower(40);     // 30 (<40)
Integer higher = set.higher(40);   // 50 (>40)

// Polling (retrieve and remove)
Integer pollFirst = set.pollFirst(); // 10 (removes it)
Integer pollLast = set.pollLast();   // 100 (removes it)

// Subsets (views, not copies!)
SortedSet<Integer> head = set.headSet(50);      // [20, 30, 40]
SortedSet<Integer> tail = set.tailSet(50);      // [50, 60, 70, 80, 90]
SortedSet<Integer> sub = set.subSet(30, 70);    // [30, 40, 50, 60]

// Inclusive bounds (NavigableSet)
NavigableSet<Integer> inclusive = set.subSet(30, true, 70, true); // [30...70]

// Descending view
NavigableSet<Integer> desc = set.descendingSet(); // [90, 80, 70...]

Using Custom Objects

// Option 1: Implement Comparable
class Student implements Comparable<Student> {
    String name;
    int grade;

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.grade, other.grade);
    }
}
TreeSet<Student> byGrade = new TreeSet<>();

// Option 2: Use Comparator
class Employee {
    String name;
    double salary;
}
TreeSet<Employee> bySalary = new TreeSet<>(
    Comparator.comparingDouble(e -> e.salary)
);

// Multi-level sorting
TreeSet<Employee> sorted = new TreeSet<>(
    Comparator.comparing((Employee e) -> e.name)
              .thenComparingDouble(e -> e.salary)
);

Common Use Cases

// 1. Finding k-th smallest/largest element
TreeSet<Integer> nums = new TreeSet<>(Arrays.asList(5, 2, 8, 1, 9, 3));
// Get 3rd smallest
Iterator<Integer> it = nums.iterator();
for (int i = 0; i < 2; i++) it.next();
int thirdSmallest = it.next(); // 3

// 2. Range queries
TreeSet<Integer> scores = new TreeSet<>();
// ... add scores
SortedSet<Integer> passing = scores.tailSet(60); // All >= 60

// 3. Finding closest values
TreeSet<Integer> prices = new TreeSet<>();
// Find price closest to budget
int budget = 150;
Integer lower = prices.floor(budget);
Integer higher = prices.ceiling(budget);

// 4. Maintaining sorted leaderboard
TreeSet<Player> leaderboard = new TreeSet<>(
    Comparator.comparingInt(Player::getScore).reversed()
);

Summary