Java

TreeSet and NavigableSet

June 10, 2026 at 07:19 AM
19 min reading
3 views

Master sorted set operations with TreeSet and NavigableSet. Learn when logarithmic time complexity beats constant time, how Red-Black trees maintain balance, and when to use ceiling, floor, and range queries for elegant solutions.

📋 At a Glance

AspectDetails
TopicTreeSet, NavigableSet, SortedSet, Red-Black Trees
ComplexityIntermediate to Advanced
PrerequisitesPart 3 (equals/hashCode), Part 9 (HashSet)
Time to Master3-4 hours
Interview FrequencyHigh (tree operations, NavigableSet methods)

🎯 What You'll Learn

After completing this article, you will be able to:

  1. Understand TreeSet's Red-Black tree implementation
  2. Use NavigableSet operations (ceiling, floor, higher, lower) effectively
  3. Create efficient range queries with subset views
  4. Choose between TreeSet and HashSet for different use cases
  5. Avoid ClassCastException with proper Comparable/Comparator usage

Interactive Visualizer

Explore how TreeSet maintains a Binary Search Tree structure - watch as elements are inserted and searched with O(log n) complexity:

Loading visualizer...

Production Story: The Range Query Performance Disaster

The Incident

Our analytics dashboard was timing out. The query to find all events between two timestamps was taking 30+ seconds for power users with millions of events.

The problematic code:

JAVA(15 lines)
Code
Loading syntax highlighter...

For a user with 2 million events, this method:

  1. Iterated through all 2M events: O(n)
  2. Sorted the results: O(k log k) where k is result size
  3. Total time: ~30 seconds

The Fix: TreeSet with Range Query

JAVA(18 lines)
Code
Loading syntax highlighter...
Performance improvement:
  • Before: O(n) iteration + O(k log k) sort = 30 seconds
  • After: O(log n) range lookup + O(k) iteration = 50 milliseconds
  • 600x faster!

Why TreeSet Wins for Range Queries

TEXT(21 lines)
Code
Loading syntax highlighter...

Lessons Learned

  1. HashSet is O(1) for exact match, but O(n) for range queries
  2. TreeSet is O(log n) for everything, including range queries
  3. NavigableSet's subSet() is a view, not a copy - very efficient
  4. Choose data structure based on query patterns, not just insert/lookup

Mental Model: The Library Card Catalog

Think of TreeSet as an old-school library card catalog:

TEXT(25 lines)
Code
Loading syntax highlighter...

Deep Dive: TreeSet Internals

Red-Black Tree Basics

TreeSet is backed by TreeMap, which uses a Red-Black Tree - a self-balancing binary search tree:
TEXT(20 lines)
Code
Loading syntax highlighter...

TreeSet Construction

JAVA(24 lines)
Code
Loading syntax highlighter...

Comparable vs Comparator

JAVA(29 lines)
Code
Loading syntax highlighter...

ClassCastException Deep Dive

JAVA(26 lines)
Code
Loading syntax highlighter...

Deep Dive: NavigableSet Operations

Core Navigation Methods

JAVA(22 lines)
Code
Loading syntax highlighter...

Visual Guide to Navigation

TEXT(18 lines)
Code
Loading syntax highlighter...

Polling Operations

JAVA(20 lines)
Code
Loading syntax highlighter...

Deep Dive: Subset Views

subSet(), headSet(), tailSet()

JAVA(19 lines)
Code
Loading syntax highlighter...

Views Are Live!

JAVA(19 lines)
Code
Loading syntax highlighter...

Descending Views

JAVA(22 lines)
Code
Loading syntax highlighter...

Deep Dive: Performance Characteristics

Operation Complexity

OperationTreeSetHashSet
add(e)O(log n)O(1)
remove(e)O(log n)O(1)
contains(e)O(log n)O(1)
first()/last()O(log n)N/A
ceiling()/floor()O(log n)N/A
higher()/lower()O(log n)N/A
subSet()O(log n)N/A
IterationO(n) sortedO(n) unsorted

When to Use TreeSet

JAVA(25 lines)
Code
Loading syntax highlighter...

When to Use HashSet

JAVA(18 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Missing Comparable/Comparator

JAVA(21 lines)
Code
Loading syntax highlighter...

Mistake 2: Inconsistent compareTo and equals

JAVA(35 lines)
Code
Loading syntax highlighter...

Mistake 3: Modifying Elements After Adding

JAVA(21 lines)
Code
Loading syntax highlighter...

Mistake 4: subSet() Range Violations

JAVA(10 lines)
Code
Loading syntax highlighter...

Mistake 5: Null Handling

JAVA(18 lines)
Code
Loading syntax highlighter...

🐛 Debug This

Challenge 1: The Missing Element

JAVA(8 lines)
Code
Loading syntax highlighter...
✅ Answer:
Output is unpredictable! Double.NaN violates comparison contract because NaN.compareTo(x) is inconsistent.
NaN is not equal to anything, not even itself, which breaks TreeSet's assumptions. The tree structure becomes corrupted.
Fix: Never add NaN to TreeSet:
JAVA(3 lines)
Code
Loading syntax highlighter...

Challenge 2: The Duplicate Elements

JAVA(16 lines)
Code
Loading syntax highlighter...
✅ Answer:
Output: 2
Items "A" and "B" have the same priority, so compareTo returns 0. TreeSet considers them equal and only keeps one.
Fix: Add tiebreaker to compareTo:
JAVA(6 lines)
Code
Loading syntax highlighter...

Challenge 3: The Infinite Loop

JAVA(8 lines)
Code
Loading syntax highlighter...
✅ Answer:
Throws ConcurrentModificationException.

Even though we add outside the subSet range, the subSet is a view backed by the original set. Modifying the original set during iteration of the view triggers the fail-fast mechanism.

Fix: Collect modifications and apply after iteration:
JAVA(7 lines)
Code
Loading syntax highlighter...

💻 Exercises

Exercise 1: Find Closest Value

Implement a method that finds the closest value to a target:

JAVA(8 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(12 lines)
Code
Loading syntax highlighter...

Exercise 2: Range Count

Implement efficient range counting:

JAVA(7 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(14 lines)
Code
Loading syntax highlighter...

Exercise 3: Top K Elements

Implement efficient top-K retrieval:

JAVA(7 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(15 lines)
Code
Loading syntax highlighter...

Exercise 4: Scheduling System

Create a scheduling system using TreeSet:

JAVA(10 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(46 lines)
Code
Loading syntax highlighter...

Exercise 5: Leaderboard

Implement a game leaderboard with efficient ranking:

JAVA(13 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(58 lines)
Code
Loading syntax highlighter...

🎤 Senior-Level Interview Questions

Question 1: TreeSet vs HashSet Performance

Q: When would TreeSet outperform HashSet?
A:

TreeSet can outperform HashSet in these scenarios:

  1. Range queries: Finding elements between X and Y is O(log n + k) for TreeSet vs O(n) for HashSet.
  2. Sorted iteration: TreeSet iterates in order naturally. HashSet requires collecting and sorting: O(n log n).
  3. Min/Max access: TreeSet provides O(log n) first()/last(). HashSet requires O(n) scan.
  4. Navigation queries: ceiling(), floor(), higher(), lower() are O(log n) in TreeSet, impossible efficiently in HashSet.
JAVA(5 lines)
Code
Loading syntax highlighter...

Question 2: Red-Black Tree Properties

Q: Why does TreeSet use a Red-Black tree instead of a simple BST?
A:

A simple BST can degenerate to O(n) operations if elements are inserted in sorted order (becomes a linked list). Red-Black trees guarantee O(log n) by maintaining these properties:

  1. Self-balancing through rotations
  2. Maximum height of 2 * log(n+1)
  3. Rebalancing is O(log n) worst case
TEXT(17 lines)
Code
Loading syntax highlighter...

Question 3: Comparable Consistency

Q: Why should compareTo() be consistent with equals()?
A:

TreeSet uses compareTo() for both ordering AND equality checking. If compareTo() returns 0 for two objects that aren't equal(), you get unexpected behavior:

JAVA(12 lines)
Code
Loading syntax highlighter...

The Java documentation explicitly warns: "The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface."

Question 4: subSet View Behavior

Q: What happens when you modify a TreeSet while iterating over its subSet view?
A:

The subSet is a live view backed by the original TreeSet. Modifications to either affect both:

  1. Modifying original: Changes visible in subSet (if in range). Triggers ConcurrentModificationException during iteration.
  2. Modifying subSet: Changes visible in original. Subject to range restrictions.
JAVA(10 lines)
Code
Loading syntax highlighter...

Question 5: Custom Comparator with Natural Ordering

Q: How would you create a TreeSet that sorts by one field primarily but uses natural ordering as a tiebreaker?
A:
Use Comparator.comparing().thenComparing():
JAVA(21 lines)
Code
Loading syntax highlighter...

Question 6: NavigableSet ceiling vs higher

Q: What's the difference between ceiling() and higher()? When would you use each?
A:
  • ceiling(e): Returns smallest element >= e (inclusive)
  • higher(e): Returns smallest element > e (exclusive)
JAVA(9 lines)
Code
Loading syntax highlighter...

Use cases:

  • ceiling(): "What's the cheapest option at or above $X?"
  • higher(): "What's the next item after this one?"

📝 Summary & Key Takeaways

TreeSet Fundamentals

  • Backed by Red-Black tree: O(log n) for all operations
  • Elements must be Comparable or use Comparator
  • No null elements allowed (can't compare null)
  • compareTo() determines both ordering AND equality
  • ceiling(e) / floor(e): Closest >= / <=
  • higher(e) / lower(e): Strictly > / <
  • pollFirst() / pollLast(): Remove and return extremes
  • descendingSet(): Reversed view

Subset Views

  • subSet(), headSet(), tailSet(): Live views
  • Changes in view affect original (and vice versa)
  • Range restrictions enforced on views
  • ConcurrentModificationException during iteration with modifications

When to Use TreeSet

  • Need sorted iteration
  • Range queries (find between X and Y)
  • Closest match queries (ceiling/floor)
  • Min/Max access needed
  • O(log n) is acceptable for add/remove/contains

🏁 Conclusion

TreeSet is more than just a sorted set - it's a powerful tool for range-based queries and navigation operations. The NavigableSet interface provides methods that can replace complex loops with elegant, efficient single calls.

Key takeaways:

  1. TreeSet uses Red-Black tree for guaranteed O(log n) operations
  2. Range queries are TreeSet's superpower - O(log n) vs O(n) for HashSet
  3. Subset views are live - changes propagate bidirectionally
  4. compareTo() must be consistent with equals() to avoid surprises
  5. NavigableSet navigation methods (ceiling, floor, higher, lower) enable elegant solutions

In the next article, we'll explore specialized sets like EnumSet and CopyOnWriteArraySet, and when they outperform general-purpose implementations.

📅 Review Schedule

To solidify your understanding, review this material:

  • Tomorrow: Re-read NavigableSet operations (ceiling, floor, etc.)
  • In 3 days: Implement Exercise 4 (Scheduler) again
  • In 1 week: Explain TreeSet vs HashSet tradeoffs to a colleague
  • In 2 weeks: Review the production story and common mistakes
Next in Series: Part 11: EnumSet & Specialized Sets
Series Navigation: Part 0: How to Use This Series | Full Index

Tags:

JavaTreesetNavigablesetSortedsetRed-black Tree
Last updated: June 10, 2026 at 11:12 AM