Course contentsShow
← Java
Lesson 995 of 2,87023. Collections Framework OverviewFree lesson

TreeSet: Sorted Set with Red-Black Tree

Learn how TreeSet maintains elements in sorted order using a balanced tree with log(n) operations.

TreeSet: Sorted Set with Red-Black Tree

What you'll learn: How TreeSet maintains elements in sorted order automatically using a balanced tree structure for efficient operations.


What Is TreeSet?

TreeSet is a Set implementation that keeps its elements automatically sorted at all times. Unlike HashSet, which stores elements in no particular order, TreeSet organizes elements in their natural ordering (or by a custom comparator you provide).

Under the hood, TreeSet uses a red-black tree—a self-balancing binary search tree. This structure ensures that even as you add or remove elements, the tree stays balanced and operations remain efficient.

How It Works

Think of TreeSet like a library that alphabetizes books as you shelve them. Each time you add a new book, it's automatically placed in the correct sorted position. You don't need to sort the collection later—it's always maintained in order.

The red-black tree structure guarantees that searching, adding, and removing elements all take logarithmic time (O(log n)). This is slower than HashSet's average O(1) operations, but the trade-off is that your elements are always sorted.

TreeSet Requirements

Elements in a TreeSet must be comparable. They need to either:

  • Implement the Comparable interface (like String, Integer, etc.)
  • Or you provide a Comparator when creating the TreeSet

Without a way to compare elements, TreeSet can't maintain sorted order.

When to Choose TreeSet

Use TreeSet when you need a collection that:

  • Contains no duplicates (it's a Set)
  • Must always be sorted
  • Requires efficient ordered operations (finding smallest/largest element, range queries)

Key Takeaway: TreeSet maintains unique elements in sorted order using a red-black tree, providing O(log n) performance for add, remove, and search operations—ideal when you need both uniqueness and automatic ordering.