1. Introduction to TreeSet

The insertion sequence is not preserved. TreeSet determines the correct sorted position for each new value.

Example: string ordering

The strings appear in their natural lexicographic order. This is not always identical to dictionary sorting in every language: Java's String.compareTo() compares character values, and uppercase/lowercase letters can sort differently than a human might expect.

Duplicates are determined by comparison

TreeSet does not decide uniqueness only by calling equals(). Its ordering comparison is central: if comparison returns 0, TreeSet treats the two values as equivalent for set membership and does not retain both.

This matters when a custom Comparator is used. If the comparator compares only string length, "Pen" and "Mug" compare as equal because both have length three. Only one of them will be kept. If both should remain, the comparator needs a tie-breaker, such as comparing the strings alphabetically after comparing their lengths.

3. Using a Comparator for Custom Ordering

A Comparator lets an application define an order different from the element type's natural order. For example, product names can be ordered by length and then alphabetically.

With this comparator, shorter names appear first. Names with the same length are ordered alphabetically, so they are not accidentally treated as duplicates merely because their lengths match.

A comparator should be consistent with the intended notion of equality. If compare(a, b) returns 0, TreeSet treats a and b as the same set entry even if a.equals(b) is false. This is allowed by the API, but it can surprise users if the comparator collapses values that the application considers distinct.

Choosing the ordering rule

Use natural ordering when the type's standard order matches the requirement. Use a comparator when the application needs a different order, such as sorting by price, priority, date, name length, or multiple fields.

A custom comparator should be deterministic and should not depend on mutable external state. Changing the effective ordering while elements are already in the tree can make lookups and iteration behave incorrectly.

4. What Happens Internally?

TreeSet is backed by a TreeMap. The map stores each set element as a key, while the set abstraction hides the associated map values. TreeMap uses a Red-Black tree, which is a self-balancing binary search tree.

In a binary search tree, values ordered below a node belong on its left side, while larger values belong on its right side. A Red-Black tree maintains balancing rules after insertions and removals so that the tree height remains proportional to \(\log n\), rather than degrading into a long chain under ordinary operation.

The tree's sorted structure is why TreeSet can perform both membership checks and ordering-aware operations efficiently. It does not need to sort the entire collection every time the elements are displayed.

5. Time Complexity and Performance

The core TreeSet operations take logarithmic time in the number of stored elements:

Here, \(n\) is the number of elements in the set. Exact implementation details can affect constant factors, so use these complexities as the main guide rather than as a promise about every individual runtime.

HashSet usually offers average \(O(1)\) membership operations, while TreeSet provides ordering and navigation at \(O(\log n)\). The TreeSet trade-off is worthwhile when sorted traversal or range operations are important. If neither is needed, the extra tree bookkeeping may not provide a benefit.

6. First and Last Elements

TreeSet provides methods for retrieving the smallest and largest values:

• first() returns the smallest element.
• last() returns the largest element.

These methods are useful for tasks such as finding the lowest approved price, the earliest date, or the highest score. They throw NoSuchElementException when the set is empty, so check isEmpty() first when emptiness is possible.

7. Navigation Methods: ceiling, floor, higher, and lower

TreeSet implements NavigableSet, which adds methods for finding elements relative to a target.

If no matching element exists, these methods return null.

Consider the set of approved prices 9.99, 19.99, 29.99, 49.99, 99.99 and a target price of 25.00:

• floor(25.00) returns 19.99, the largest value not exceeding the target.
• lower(25.00) also returns 19.99, because it is strictly below the target.
• ceiling(25.00) returns 29.99, the smallest value not below the target.
• higher(25.00) also returns 29.99, because it is strictly above the target.

The distinction becomes visible when the target itself is present. For a target of 19.99, both floor() and ceiling() return 19.99, while lower() returns 9.99 and higher() returns 29.99.

These methods are useful for price matching, nearest available time slots, scheduling, ranking, threshold checks, and other problems where the closest value on one side of a target matters.

8. Range Views: headSet, tailSet, and subSet

TreeSet can expose a range of its elements without requiring a manual loop and filter.

The default subSet(from, to) range is lower-inclusive and upper-exclusive: \([from, to)\). The NavigableSet overloads allow the caller to specify whether each boundary is inclusive.

Range operations are useful for retrieving orders within an ID interval, prices within a budget, dates within a period, or scores within a band.

Range methods return views, not independent copies

A range returned by headSet(), tailSet(), or subSet() is backed by the original TreeSet. Changes to the parent set can appear in the view when the changed values are within its range. Supported modifications through the view also affect the parent collection.

This means a range view is not a frozen snapshot. If an independent collection is required, copy the view:

The copied set has its own membership structure and will not automatically reflect later changes to orderIds.

9. TreeSet and null

With natural ordering, TreeSet does not support null elements. It needs to compare values to determine where they belong, and a null reference cannot be compared using an element's compareTo() method. In current standard Java implementations, attempting to add null to an empty naturally ordered TreeSet throws NullPointerException as well; do not rely on a null being accepted merely because the set has no existing elements.

A custom comparator can define an explicit ordering for null values, but this should be used only when null is a meaningful part of the data model. In many applications, rejecting or validating null before insertion is clearer.

This differs from HashSet and LinkedHashSet, which permit one null element because their membership behavior does not require ordering comparisons.

10. TreeSet Compared with HashSet and LinkedHashSet

All three classes implement Set, but their ordering guarantees and performance characteristics differ.

Use the implementation whose guarantees match the actual requirement:

• Choose HashSet when only uniqueness and membership checks matter.
• Choose LinkedHashSet when unique elements must remain in first-insertion order.
• Choose TreeSet when sorted iteration, nearest-value navigation, or range views are required.

• Whiteboard

  Loading diagram...

  
  

11. Practical Example: A Sorted Leaderboard

Suppose an application stores unique scores and needs to display them in order, find the highest score, and inspect a score range. TreeSet supports all these operations directly.

The duplicate score is ignored. Iteration is already sorted, first() and last() expose the extremes, tailSet() provides a range view, and ceiling() finds the smallest stored score at least as large as the target.

A HashSet could store the unique scores, but the application would need extra work to sort them and manually implement range selection. TreeSet is a natural fit because its built-in guarantees directly match the job.

12. Common Mistakes to Avoid

Assuming TreeSet preserves insertion order

It does not. It uses its ordering rule. If the input order must be preserved, use LinkedHashSet.

Expecting constant-time membership checks

contains() is \(O(\log n)\) in TreeSet, not average \(O(1)\) as in HashSet.

Using a comparator that collapses distinct values

If a comparator returns 0 for two objects, TreeSet treats them as the same set element. Add a tie-breaker when distinct values must both be retained.

Assuming range methods make copies

Range methods return backed views. Copy a range into a new TreeSet if an independent snapshot is needed.

Adding null under natural ordering

A naturally ordered TreeSet rejects null with NullPointerException. Validate inputs or define an intentional null-aware comparator when appropriate.

Changing fields used by comparison while an object is stored

If a stored element's comparison behavior changes, the tree's structure may no longer correspond to the new ordering. Prefer stable comparison keys while elements are in the set; remove and reinsert an element if its ordering key must change.

13. Best Practices

1. Choose TreeSet for a reason. Use it when sorted iteration or navigation is part of the requirement, not simply because it is another Set implementation.
2. Keep ordering consistent. Implement Comparable or provide a Comparator that defines a stable, transitive ordering.
3. Use tie-breakers thoughtfully. If the primary sort field can match for different objects, compare additional fields to preserve distinct values.
4. Remember range boundaries. The default subSet(from, to) includes from and excludes to.
5. Treat views as live. Do not assume a range view is an immutable snapshot.
6. Avoid mutable sort keys. Changing fields that affect comparison while an element is stored can undermine lookup behavior.
7. Handle empty sets. Check isEmpty() before calling first() or last() if the collection may be empty.
8. Validate nulls. Natural ordering requires comparable, non-null elements.
9. Use complexity to guide choices. TreeSet trades logarithmic operations for sorted order and navigation features.

14. Quick Revision

• TreeSet stores unique elements in sorted order.
• It is backed by TreeMap, which uses a Red-Black tree.
• Natural ordering comes from Comparable; custom ordering comes from Comparator.
• add(), remove(), and contains() take \(O(\log n)\) time.
• first() and last() return the smallest and largest elements.
• ceiling() and floor() include equality; higher() and lower() are strict.
• headSet(), tailSet(), and subSet() provide backed range views.
• A comparison result of 0 means TreeSet treats the values as equivalent for membership.
• Null is not accepted under natural ordering.
• Choose HashSet for unordered membership, LinkedHashSet for insertion order, and TreeSet for sorted order and range queries.

15. Conclusion

TreeSet is a powerful Java collection when sorted uniqueness is a real requirement. Its balanced-tree structure keeps values ordered and supports navigation and range operations without repeatedly sorting or scanning the entire collection. These benefits come with \(O(\log n)\) core operations and comparison requirements, so the best implementation depends on the workload.

Use HashSet for fast average membership checks without an ordering requirement, LinkedHashSet when insertion order matters, and TreeSet when values need to stay sorted or when the application must efficiently locate nearby values and ranges. Understanding those trade-offs makes choosing the right Java Set implementation much easier.