ReviseAlgo Logo

Collections Framework

TreeSet

Analyze TreeSet sorted structures, TreeMap backing, Red-Black tree navigation, and sorted complexity bounds.

Interview: Focuses on TreeSet backing TreeMap, Red-Black tree O(log N) complexity, sorted contracts, and Comparator usage.

Last Updated: June 13, 2026 • 10 min read

A TreeSet is a NavigableSet implementation backed by a TreeMap. Elements are sorted by their natural ordering or by a custom Comparator provided at instantiation.

Red-Black Tree

Backed by a self-balancing binary search tree. Ensures operations remain balanced and performant.

Logarithmic Cost

Guarantees O(log N) time complexity for basic operations (add, remove, contains).

Range Queries

Provides range query methods like subSet, headSet, tailSet, higher, and lower.

The Sorting Contract & Null Handling

TreeSet features strict rules regarding element comparison:

  • Elements must implement Comparable (or a Comparator must be supplied), otherwise adding elements triggers a ClassCastException at runtime.
  • Null Rejection: Since Java 7, TreeSet rejects null elements, raising a NullPointerException because null values cannot be compared to determine sorting coordinates.

Common Pitfalls

  • Comparable mismatch with equals: Implementing a compareTo method that returns 0 for two elements that are not equal according to equals(). This can cause TreeSet to silently reject elements as duplicates, violating the Set interface contract.
  • Unsorted custom classes: Attempting to insert a custom class object that lacks Comparable implementation into a default TreeSet.

Best Practices

  • Consistent contracts: Ensure compareTo is consistent with equals(): (x.compareTo(y) == 0) == x.equals(y).
  • Supply a Comparator: Use custom comparators for external structures (like database entities) where natural sorting makes no sense.

Interview-Relevant Information

Q1: What backing structure is used by TreeSet?
Answer: TreeSet is backed by a TreeMap, which uses a self-balancing Red-Black binary search tree to store elements as keys.

Q2: Why does TreeSet throw ClassCastException?
Answer: It throws this exception if the elements being inserted do not implement Comparable (or if no Comparator is provided), preventing elements from being compared.

Quick Checklist

Can you state the complexity of TreeSet operations, identify the self-balancing tree type, and explain why compareTo must align with equals? If yes, you understand TreeSet.

Use Cases

Maintaining sorted database caches that require frequent range queries.

Implementing leadership boards where positions are dynamically queried.

Common Mistakes

Failing to implement Comparable on elements inserted into TreeSet.

Writing compareTo methods that violate equals equivalence contracts.