Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to Java TreeSet — Red-Black tree implementation, NavigableSet operations, natural and custom ordering, range queries, ceiling/floor methods, and practical examples.
What is TreeSet?
java.util.TreeSet is a NavigableSet implementation backed by a TreeMap (Red-Black tree). It stores elements in sorted order — either by natural ordering (Comparable) or by a custom Comparator.
java example
public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, SerializableKey characteristics:
- Elements are always sorted (ascending by default)
- No duplicate elements
- No null elements (throws NullPointerException)
- O(log n) for add, remove, contains
- Provides range operations (subSet, headSet, tailSet)
- Provides navigation (ceiling, floor, higher, lower)
Time Complexity
| Operation | Time Complexity |
|---|---|
| ----------- | :-: |
add(E e) | O(log n) |
remove(Object o) | O(log n) |
contains(Object o) | O(log n) |
first() / last() | O(log n) |
ceiling() / floor() | O(log n) |
higher() / lower() | O(log n) |
size() | O(1) |
| Iteration (full) | O(n) |
subSet() creation | O(log n) |
Basic Usage
Example
import java.util.*;
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Integer> numbers = new TreeSet<>();
// Elements are sorted automatically
numbers.add(50);
numbers.add(20);
numbers.add(80);
numbers.add(35);
numbers.add(60);
numbers.add(20); // Duplicate — not added
System.out.println("TreeSet: " + numbers); // [20, 35, 50, 60, 80]
System.out.println("Size: " + numbers.size()); // 5
// First and Last
System.out.println("First: " + numbers.first()); // 20
System.out.println("Last: " + numbers.last()); // 80
// Polling (removes and returns)
System.out.println("Poll first: " + numbers.pollFirst()); // 20 (removed!)
System.out.println("Poll last: " + numbers.pollLast()); // 80 (removed!)
System.out.println("After polling: " + numbers); // [35, 50, 60]
}
}
Output
TreeSet (sorted): [Apple, Banana, Cherry, Mango] First: Apple Last: Mango Ceiling of C: Cherry Floor of C: Cherry Higher than Cherry: Mango Lower than Cherry: Banana SubSet [B, M): [Banana, Cherry]
NavigableSet Methods
Ceiling, Floor, Higher, Lower
java example
TreeSet<Integer> set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50, 60, 70));
// ceiling — smallest element >= value
System.out.println(set.ceiling(25)); // 30
System.out.println(set.ceiling(30)); // 30 (inclusive)
System.out.println(set.ceiling(75)); // null (nothing >= 75)
// floor — largest element <= value
System.out.println(set.floor(25)); // 20
System.out.println(set.floor(30)); // 30 (inclusive)
System.out.println(set.floor(5)); // null (nothing <= 5)
// higher — smallest element STRICTLY > value
System.out.println(set.higher(30)); // 40
System.out.println(set.higher(70)); // null
// lower — largest element STRICTLY < value
System.out.println(set.lower(30)); // 20
System.out.println(set.lower(10)); // nullSubSet, HeadSet, TailSet (Range Views)
Example
TreeSet<Integer> set = new TreeSet<>();
for (int i = 10; i <= 100; i += 10) set.add(i);
// {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
// subSet(fromElement, fromInclusive, toElement, toInclusive)
NavigableSet<Integer> sub = set.subSet(30, true, 70, true);
System.out.println(sub); // [30, 40, 50, 60, 70]
// headSet(toElement, inclusive) — elements < toElement
NavigableSet<Integer> head = set.headSet(50, false);
System.out.println(head); // [10, 20, 30, 40]
// tailSet(fromElement, inclusive) — elements >= fromElement
NavigableSet<Integer> tail = set.tailSet(60, true);
System.out.println(tail); // [60, 70, 80, 90, 100]
Important: These are live views — modifications reflect in the original:
Example
sub.add(55); // Adds 55 to the original set too!
System.out.println(set.contains(55)); // true
// But you can't add elements outside the view's range:
sub.add(100); // IllegalArgumentException! 100 is outside [30, 70]
Descending Order
Example
// Descending view
NavigableSet<Integer> descending = set.descendingSet();
System.out.println(descending); // [100, 90, 80, ..., 10]
// Descending iterator
Iterator<Integer> descIt = set.descendingIterator();
while (descIt.hasNext()) {
System.out.print(descIt.next() + " ");
}
// 100 90 80 70 60 50 40 30 20 10
Custom Comparator
Example
// Sort strings by length, then alphabetically
TreeSet<String> byLength = new TreeSet<>(
Comparator.comparingInt(String::length)
.thenComparing(Comparator.naturalOrder())
);
byLength.addAll(Arrays.asList("banana", "apple", "fig", "cherry", "date", "kiwi"));
System.out.println(byLength);
// [fig, date, kiwi, apple, banana, cherry]
// Reverse natural order
TreeSet<Integer> descending = new TreeSet<>(Comparator.reverseOrder());
descending.addAll(Arrays.asList(3, 1, 4, 1, 5, 9));
System.out.println(descending); // [9, 5, 4, 3, 1]
// Custom objects
TreeSet<Employee> byName = new TreeSet<>(Comparator.comparing(Employee::getName));
TreeSet<Employee> bySalary = new TreeSet<>(
Comparator.comparingDouble(Employee::getSalary).reversed()
);
TreeSet with Custom Objects
java example
// Option 1: Implement Comparable
public class Student implements Comparable<Student> {
private String name;
private int grade;
@Override
public int compareTo(Student other) {
int result = Integer.compare(this.grade, other.grade);
if (result == 0) result = this.name.compareTo(other.name);
return result;
}
// Constructor, getters, toString...
}
TreeSet<Student> students = new TreeSet<>();
students.add(new Student("Alice", 92));
students.add(new Student("Bob", 88));
students.add(new Student("Charlie", 92));
// Sorted by grade, then name: Bob(88), Alice(92), Charlie(92)
// Option 2: Provide Comparator (no Comparable needed)
TreeSet<Student> byNameSet = new TreeSet<>(
Comparator.comparing(Student::getName)
);Critical: compareTo() Must Be Consistent
java example
// BROKEN — if compareTo returns 0, TreeSet treats them as EQUAL (same element)!
public int compareTo(Student other) {
return Integer.compare(this.grade, other.grade);
// Two students with same grade are considered DUPLICATES!
}
// CORRECT — break ties with another field
public int compareTo(Student other) {
int result = Integer.compare(this.grade, other.grade);
if (result == 0) result = this.name.compareTo(other.name);
return result;
}Practical Use Cases
1. Finding Nearest Values
java example
// Find the closest temperature reading to a target
TreeSet<Double> readings = new TreeSet<>(
Arrays.asList(36.1, 36.5, 37.0, 37.5, 38.0, 38.5, 39.0)
);
double target = 37.3;
Double floor = readings.floor(target); // 37.0
Double ceiling = readings.ceiling(target); // 37.5
double closest = (target - floor < ceiling - target) ? floor : ceiling;
System.out.println("Closest to " + target + ": " + closest); // 37.52. Calendar/Scheduling — Finding Next Available Slot
java example
TreeSet<LocalTime> bookedSlots = new TreeSet<>(Arrays.asList(
LocalTime.of(9, 0), LocalTime.of(10, 0), LocalTime.of(11, 0),
LocalTime.of(14, 0), LocalTime.of(15, 0)
));
// Find next available slot after 11:00
LocalTime nextFree = bookedSlots.higher(LocalTime.of(11, 0));
// If nextFree is 14:00, there's a gap between 11:00 and 14:00!3. Maintaining a Sorted Leaderboard
java example
record Score(String player, int points) implements Comparable<Score> {
@Override
public int compareTo(Score other) {
int cmp = Integer.compare(other.points, this.points); // Descending
if (cmp == 0) cmp = this.player.compareTo(other.player);
return cmp;
}
}
TreeSet<Score> leaderboard = new TreeSet<>();
leaderboard.add(new Score("Alice", 1500));
leaderboard.add(new Score("Bob", 2000));
leaderboard.add(new Score("Charlie", 1800));
// Top 2 scores
leaderboard.stream().limit(2).forEach(System.out::println);
// Bob: 2000, Charlie: 18004. Range Queries for Data Analysis
Example
TreeSet<Integer> ages = new TreeSet<>(
Arrays.asList(18, 22, 25, 28, 30, 33, 35, 40, 45, 50, 55, 60)
);
// Count people aged 25-45
int count = ages.subSet(25, true, 45, true).size(); // 7
// People in their 30s
NavigableSet<Integer> thirties = ages.subSet(30, true, 39, true);
System.out.println(thirties); // [30, 33, 35]
TreeSet vs HashSet vs LinkedHashSet
| Feature | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| Ordering | None | Insertion order | Sorted |
| add/remove/contains | O(1) | O(1) | O(log n) |
| Backed by | HashMap | LinkedHashMap | TreeMap |
| Null | One null | One null | ❌ None |
| Navigation methods | No | No | Yes |
| Range views | No | No | Yes |
| Memory | Low | Medium | High |
| Comparable required? | No (uses equals/hashCode) | No | Yes (or Comparator) |
Performance Comparison
| add() | ~150ms ~180ms ~1200ms |
| contains() | ~50ms ~55ms ~600ms |
| iteration | ~60ms ~40ms ~80ms |
TreeSet is ~8-10x slower than HashSet for individual operations, but provides sorting and navigation that hash-based sets cannot.
Thread Safety
java example
// Option 1: Synchronized wrapper
SortedSet<Integer> syncSet = Collections.synchronizedSortedSet(new TreeSet<>());
// Option 2: ConcurrentSkipListSet (concurrent NavigableSet)
NavigableSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
// O(log n) with high concurrency — uses skip list internallyCommon Mistakes
1. Adding Null Elements
java example
TreeSet<String> set = new TreeSet<>();
set.add("Hello");
set.add(null); // NullPointerException! Can't compare null2. Elements Not Comparable
java example
// Without Comparable or Comparator:
TreeSet<Object> set = new TreeSet<>();
set.add(new Object()); // ClassCastException! Can't compare Objects3. Comparator Inconsistent with Equals
java example
// DANGEROUS — comparator considers different objects as "equal"
TreeSet<String> set = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
set.add("Hello");
set.add("HELLO"); // NOT added! Comparator says they're equal!
System.out.println(set.size()); // 1!4. Modifying Elements After Insertion
java example
// TreeSet doesn't detect element mutation
// If an element's sort key changes, tree structure becomes invalid
// ALWAYS use immutable objects as TreeSet elements5. Assuming O(1) Performance
java example
// WRONG assumption — TreeSet is O(log n), not O(1)
// For 1 million elements: ~20 comparisons per operation
// Use HashSet if you don't need sortingInterview Questions
Q1: How does TreeSet maintain sorted order?
A: TreeSet is backed by a TreeMap which uses a Red-Black tree. Elements are stored as tree nodes in sorted order. The tree self-balances after insertions/deletions to maintain O(log n) height.
Q2: What happens if elements don't implement Comparable and no Comparator is provided?
A: TreeSet throws ClassCastException when you try to add the first element that requires comparison (or on the second element when it tries to compare with the first).
Q3: Can TreeSet contain null?
A: No. Since TreeSet needs to compare elements, null throws NullPointerException. (Exception: with a custom Comparator that explicitly handles null.)
Q4: What is the difference between ceiling() and higher()?
A: ceiling(e) returns the smallest element ≥ e (inclusive). higher(e) returns the smallest element > e (exclusive).
Q5: How does TreeSet determine equality?
A: TreeSet uses compareTo() (or Comparator.compare()), NOT equals(). If compareTo returns 0, elements are considered equal. This can differ from equals() behavior!
Q6: What is the time complexity of subSet()?
A: Creating the view is O(log n). It's a live view, not a copy. Iterating the subset is O(k + log n) where k is the number of elements in the range.
Q7: What is ConcurrentSkipListSet?
A: The concurrent equivalent of TreeSet. Uses a skip list (not a tree) for O(log n) sorted set operations with thread safety and high concurrency.
Q8: Why does TreeSet throw ClassCastException for objects without Comparable?
A: TreeSet needs to compare elements for ordering. If no Comparator is provided in the constructor, it casts elements to Comparable and calls compareTo(). If the element's class doesn't implement Comparable, the cast fails with ClassCastException at runtime (on the second add, when comparison first occurs).
Q9: How does TreeSet determine equality?
A: TreeSet uses compareTo() (or Comparator's compare()) — NOT equals(). Two elements are considered equal if compareTo() returns 0. This means if your Comparator considers two different objects as "equal" (returns 0), only one will be stored. This differs from HashSet which uses equals()/hashCode().
Q10: What is the time complexity of TreeSet operations?
A: add(), remove(), contains() are all O(log n) due to the Red-Black tree structure. first(), last(), ceiling(), floor() are also O(log n). Iteration is O(n). This is slower than HashSet's O(1) but provides sorted order and range operations.
Q11: Can you store null in a TreeSet?
A: No. Adding null throws NullPointerException because TreeSet tries to compare null with existing elements using compareTo() or compare(). Even if the tree is empty, Java 7+ explicitly checks and rejects null. (Java 6 allowed null as the first element, but this was considered a bug.)
Q12: How do you get elements in descending order from TreeSet?
A: Use descendingSet() which returns a NavigableSet view in reverse order, or descendingIterator() for reverse iteration. Alternatively, create the TreeSet with Comparator.reverseOrder(): new TreeSet<>(Comparator.reverseOrder()).
Summary
| Aspect | TreeSet |
|---|---|
| Backed by | TreeMap (Red-Black tree) |
| Ordering | Sorted (natural or comparator) |
| Performance | O(log n) all operations |
| Null | Not allowed |
| Navigation | ceiling, floor, higher, lower |
| Range views | subSet, headSet, tailSet |
| Best for | Sorted unique elements, range queries |
| Thread-safe alternative | ConcurrentSkipListSet |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for TreeSet in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, collections, framework, set
Related Java Master Course Topics
Continue learning this concept
Collections FrameworkHashSet in JavaComplete guide to Java HashSet — internal working backed by HashMap, hashing mechanism, duplicate detection, equals/hashCode contract, performance analysis, and practical examples.Collections FrameworkLinkedHashSet in JavaComplete guide to Java LinkedHashSet — insertion-order preservation, internal working backed by LinkedHashMap, comparison with HashSet and TreeSet, and practical use cases.Collections FrameworkCollections Framework OverviewComplete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.Collections FrameworkCollections Practice ProgramsComprehensive Java Collections practice programs covering List, Set, Map, Queue operations with solutions, explanations, and time complexity analysis.Collections FrameworkComparable vs Comparator in JavaDeep dive into Comparable and Comparator interfaces in Java — natural ordering, custom sorting, lambda expressions, method references, and practical comparisons with examples.Collections FrameworkGenerics in JavaComplete guide to Java Generics — type parameters, bounded types, wildcards, type erasure, generic methods, generic classes, and common patterns with practical examples.