☕ JavaCollections Framework

TreeSet

TreeSet is a NavigableSet implementation backed by a red-black tree that stores elements in sorted order. It provides O(log n) time for add, remove, and contains operations. Every element must either implement Comparable or a Comparator must be supplied at construction. The sorted order enables a rich set of range and navigation operations: finding the element just greater or lesser than a target, extracting subsets over a range, and iterating in ascending or descending order — operations that HashSet and LinkedHashSet cannot support. TreeSet implements both SortedSet and NavigableSet, and understanding these interfaces is inseparable from understanding TreeSet's full capability. This entry covers the red-black tree structure, the ordering contract, all navigation and range operations, performance trade-offs, and the practical scenarios where sorted order justifies the O(log n) cost.

Red-Black Tree — Structure and Order

TreeSet is backed by a TreeMap, which implements a red-black tree — a self-balancing binary search tree. In a binary search tree, every node's left subtree contains only smaller elements and every right subtree contains only larger elements. A search traverses from root to leaf, going left when the target is smaller and right when it is larger. Balanced trees guarantee this path is at most O(log n) nodes, ensuring O(log n) operations. Red-black trees maintain balance by colouring each node red or black and enforcing four invariants: the root is black; red nodes have only black children (no two consecutive red nodes); every path from root to leaf has the same number of black nodes; leaves (nulls) are black. These invariants guarantee that the longest path is at most twice the shortest path, bounding tree height at 2 log n and guaranteeing O(log n) operations. When an element is inserted, it is placed in the correct sorted position, then the tree is rebalanced via rotations and recolouring to restore the red-black invariants. Deletion is similarly followed by rebalancing. Both operations are O(log n) including the rebalancing work. The critical implication of tree-based storage: TreeSet uses the ordering defined by compareTo (or the Comparator) for all operations, including equality testing. Two elements are considered equal if and only if compareTo returns 0 — the equals() method is not consulted. This means the Comparator must be consistent with equals (return 0 for objects that are equals() to each other) for TreeSet to behave correctly as a Set. If the Comparator considers two distinct objects equal, only one will be stored (TreeSet has no duplicates by the Set contract). If the Comparator considers two equal objects unequal, they can both be stored — violating Set semantics.

Java

// ── TreeSet construction and ordering ────────────────────────────────
// Natural ordering — elements must implement Comparable
TreeSet<Integer> natural = new TreeSet<>();
natural.add(5); natural.add(3); natural.add(8); natural.add(1); natural.add(7);
System.out.println(natural);   // [1, 3, 5, 7, 8] — always sorted ascending

// Custom comparator — reverse order
TreeSet<Integer> reversed = new TreeSet<>(Comparator.reverseOrder());
reversed.addAll(natural);
System.out.println(reversed);  // [8, 7, 5, 3, 1] — descending

// Custom comparator for domain objects
record Person(String name, int age) {}
TreeSet<Person> byAge = new TreeSet<>(
    Comparator.comparingInt(Person::age)
              .thenComparing(Person::name));
byAge.add(new Person("Bob",   30));
byAge.add(new Person("Alice", 25));
byAge.add(new Person("Carol", 25));

for (Person p : byAge) System.out.println(p.name() + " " + p.age());
// Alice 25, Carol 25, Bob 30 — sorted by age then name

// ── Consistency with equals — the critical contract ───────────────────
// CORRECT: Comparator consistent with equals
TreeSet<String> correct = new TreeSet<>();
correct.add("apple");
correct.add("apple");   // duplicate — compareTo returns 0 — not added
System.out.println(correct.size());   // 1 — correct Set behaviour

// DANGEROUS: Comparator inconsistent with equals
TreeSet<String> inconsistent = new TreeSet<>(
    Comparator.comparingInt(String::length));  // only compares by length
inconsistent.add("cat");
inconsistent.add("dog");   // same length as "cat" → compareTo returns 0 → NOT added!
inconsistent.add("horse");
System.out.println(inconsistent);   // [cat, horse] — "dog" silently dropped!
// "cat" and "dog" are not equals() to each other, but the comparator treats them equal
// This violates Set contract: multiple non-equal objects appear as one

// ── Red-black tree structure (simplified) ─────────────────────────────
//
// TreeSet {1, 3, 5, 7, 8, 9, 11}:
//
//           7 (black)
//          / //         3   9 (red)
//        /  / //       1  5 8 11 (black)
//
// contains(8): 7→right→9→left→8 — 3 comparisons, O(log n)
// contains(6): 7→left→3→right→5→right→null — 4 comparisons, not found

Navigation Operations — first, last, floor, ceiling, higher, lower

TreeSet's navigation methods are its distinguishing feature. Because elements are stored in sorted order, TreeSet can efficiently answer questions that require knowing the relative position of elements: what is the greatest element less than or equal to x? What is the smallest element strictly greater than x? These questions require O(log n) traversal of the tree and cannot be answered by HashSet without a full O(n) scan. floor(e) returns the greatest element less than or equal to e, or null if no such element exists. ceiling(e) returns the smallest element greater than or equal to e, or null if no such element exists. lower(e) returns the greatest element strictly less than e (excluding equals). higher(e) returns the smallest element strictly greater than e. These four methods are the core of the navigation API and appear constantly in interval queries, range queries, and rank-finding algorithms. first() and last() return the minimum and maximum elements in O(log n) time (actually O(log n) for the balanced tree traversal to reach the leftmost or rightmost leaf). pollFirst() and pollLast() remove and return the minimum and maximum elements respectively, combining retrieval and deletion in one O(log n) operation. These navigation methods are the building blocks for interval problems. Finding the closest previous appointment in a calendar, finding the highest price at or below a threshold in a price list, finding the next available ID in a sparse sequence — all are O(log n) with TreeSet navigation, versus O(n) with linear collection scanning.

Java

// ── Navigation method semantics ──────────────────────────────────────
TreeSet<Integer> set = new TreeSet<>(Set.of(1, 3, 5, 7, 9, 11));

// floor: greatest element <= target
System.out.println(set.floor(6));    // 5  (6 not in set, largest ≤ 6 is 5)
System.out.println(set.floor(5));    // 5  (5 is in set, exact match)
System.out.println(set.floor(0));    // null (nothing ≤ 0)

// ceiling: smallest element >= target
System.out.println(set.ceiling(6));   // 7  (6 not in set, smallest ≥ 6 is 7)
System.out.println(set.ceiling(7));   // 7  (exact match)
System.out.println(set.ceiling(12));  // null (nothing ≥ 12)

// lower: greatest element STRICTLY < target
System.out.println(set.lower(5));    // 3  (strictly less than 5)
System.out.println(set.lower(1));    // null (nothing < 1)

// higher: smallest element STRICTLY > target
System.out.println(set.higher(5));   // 7  (strictly greater than 5)
System.out.println(set.higher(11));  // null (nothing > 11)

// first and last
System.out.println(set.first());  // 1  — minimum element
System.out.println(set.last());   // 11 — maximum element

// pollFirst / pollLast — remove and return extremes
System.out.println(set.pollFirst());  // 1 — removed
System.out.println(set.pollLast());   // 11 — removed
System.out.println(set);             // [3, 5, 7, 9]

// ── Real-world navigation patterns ───────────────────────────────────
// Find the next available appointment slot after a given time
TreeSet<LocalTime> available = new TreeSet<>(Set.of(
    LocalTime.of(9, 0), LocalTime.of(10, 30),
    LocalTime.of(14, 0), LocalTime.of(16, 30)));

LocalTime desired  = LocalTime.of(11, 0);
LocalTime nextSlot = available.ceiling(desired);  // 14:00 — next slot at or after 11:00
LocalTime prevSlot = available.floor(desired);    // 10:30 — last slot at or before 11:00

// Stock price: highest price at or below $50
TreeSet<BigDecimal> prices = new TreeSet<>(Set.of(
    new BigDecimal("45.00"), new BigDecimal("48.50"),
    new BigDecimal("52.00"), new BigDecimal("55.00")));
BigDecimal threshold = new BigDecimal("50.00");
BigDecimal bestPrice = prices.floor(threshold);   // 48.50

Range Views — subSet, headSet, tailSet

TreeSet provides three range-view methods that return live views of portions of the set. A live view means that changes to the original set are reflected in the view and changes to the view (add, remove) are reflected in the original set. These views are backed by the same tree; they are not copies. subSet(fromElement, fromInclusive, toElement, toInclusive) returns a view of the portion of the set whose elements range from fromElement to toElement, with inclusivity controlled by the boolean parameters. The four-argument version is the most flexible; a two-argument shorthand subSet(from, to) is equivalent to subSet(from, true, to, false) — inclusive on the left, exclusive on the right (half-open interval, consistent with most range conventions). headSet(toElement) returns a view of all elements strictly less than toElement. headSet(toElement, inclusive) adds control over the boundary. tailSet(fromElement) returns all elements greater than or equal to fromElement. All range views throw IllegalArgumentException if you attempt to add an element outside the view's range — enforcing that the view's contract is not violated. The views also support all NavigableSet operations (floor, ceiling, lower, higher, subSet, headSet, tailSet) — you can chain range views. Range views are particularly powerful in combination with the iteration guarantee: iterating a subSet produces elements in sorted order within the range, which is exactly what is needed for range-based queries in scheduling, pricing, and event processing applications.

Java

// ── subSet — range view inclusive/exclusive control ──────────────────
TreeSet<Integer> set = new TreeSet<>(
    Set.of(1, 3, 5, 7, 9, 11, 13, 15));

// subSet(from, to) — [from, to)  left-inclusive, right-exclusive
NavigableSet<Integer> middle = set.subSet(5, 11);
System.out.println(middle);   // [5, 7, 9]

// subSet with full inclusivity control
NavigableSet<Integer> closed = set.subSet(5, true, 11, true);
System.out.println(closed);   // [5, 7, 9, 11]

// subSet exclusive both ends
NavigableSet<Integer> open = set.subSet(5, false, 11, false);
System.out.println(open);    // [7, 9]

// ── headSet and tailSet ───────────────────────────────────────────────
NavigableSet<Integer> head = set.headSet(7);         // [1, 3, 5] — strictly < 7
NavigableSet<Integer> headInc = set.headSet(7, true); // [1, 3, 5, 7] — <= 7
NavigableSet<Integer> tail = set.tailSet(7);          // [7, 9, 11, 13, 15] — >= 7
NavigableSet<Integer> tailExc = set.tailSet(7, false); // [9, 11, 13, 15] — > 7

// ── Live views — modifications reflected in original ──────────────────
NavigableSet<Integer> view = set.subSet(5, true, 11, true);
view.add(6);    // adds 6 to the ORIGINAL set
view.remove(7); // removes 7 from the ORIGINAL set
System.out.println(set);   // [1, 3, 5, 6, 9, 11, 13, 15] — 6 added, 7 removed

// Attempting to add outside range throws IllegalArgumentException:
view.add(12);  // throws IllegalArgumentException — 12 > 11 (upper bound)
view.add(4);   // throws IllegalArgumentException — 4 < 5 (lower bound)

// ── Practical range queries ───────────────────────────────────────────
// Tasks scheduled between two times:
TreeSet<Task> schedule = new TreeSet<>(
    Comparator.comparing(Task::scheduledTime));

LocalDateTime from = LocalDateTime.now();
LocalDateTime to   = from.plusHours(2);

// Live view of tasks in the next 2 hours:
SortedSet<Task> upcoming = schedule.subSet(
    new Task(from), true,
    new Task(to),   false);

// Count tasks in range without materialising a copy:
System.out.println("Tasks in next 2h: " + upcoming.size());

// Descending view of range:
NavigableSet<Integer> descending = set.subSet(5, true, 11, true)
    .descendingSet();
System.out.println(descending);   // [11, 9, 6, 5]

TreeSet Performance and When to Use It

TreeSet's O(log n) performance is the correct trade-off when sorted order or range operations are needed. For pure membership testing without ordering requirements, HashSet's O(1) average case is faster — there is no reason to pay the log-n cost for sorted storage if the application never uses the sorting. The decision is always driven by whether the application needs: sorted iteration, range queries, navigation operations (floor, ceiling), or min/max retrieval with removal. The absolute performance of O(log n) is still very fast in practice. For a set of 1,000,000 elements, log₂(1,000,000) ≈ 20 comparisons per operation. For 1,000,000,000 elements, it is ≈ 30 comparisons. The constant factor in each comparison depends on the compareTo implementation — comparing integers is faster than comparing strings. For well-implemented comparators, TreeSet operations complete in nanoseconds to microseconds for any practical set size. TreeSet is not thread-safe. Concurrent structural modification (add, remove) without external synchronisation will corrupt the tree structure. ConcurrentSkipListSet from java.util.concurrent provides a thread-safe sorted set with O(log n) operations and non-blocking reads, making it the correct replacement for TreeSet in concurrent applications. The natural use cases for TreeSet: event schedulers that need the next event after a given time, price ladders that need the best bid at or below a given price, routing tables that need the longest prefix match, timeline annotations that need all annotations in a time range, and leaderboards that need rank-based queries.

Java

// ── TreeSet vs HashSet: choosing based on need ───────────────────────
// Need membership testing only, no ordering:
Set<String> membership = new HashSet<>();    // O(1) — correct choice

// Need sorted iteration:
Set<String> sorted = new TreeSet<>();        // O(log n) — justified

// Need range queries:
TreeSet<Integer> range = new TreeSet<>();    // only TreeSet can do this efficiently

// ── TreeSet as leaderboard ────────────────────────────────────────────
record Score(String player, int points) {}

TreeSet<Score> leaderboard = new TreeSet<>(
    Comparator.comparingInt(Score::points).reversed()
              .thenComparing(Score::player));

leaderboard.add(new Score("Alice", 1500));
leaderboard.add(new Score("Bob",   2300));
leaderboard.add(new Score("Carol", 1500));
leaderboard.add(new Score("Dave",  3100));

// Top 3:
leaderboard.stream().limit(3).forEach(s ->
    System.out.println(s.player() + ": " + s.points()));
// Dave: 3100, Bob: 2300, Alice: 1500

// Who is just below 2000 points?
Score justBelow = leaderboard.higher(new Score("", 2000));
// Uses comparator: find score just above 2000 in descending order

// ── ConcurrentSkipListSet — thread-safe TreeSet replacement ───────────
NavigableSet<Integer> concurrent = new ConcurrentSkipListSet<>();
concurrent.add(5);
concurrent.add(3);
concurrent.add(7);
// Thread-safe: O(log n) add/remove/contains
// Non-blocking reads: multiple threads can read simultaneously
System.out.println(concurrent.floor(6));    // 5 — thread-safe navigation
System.out.println(concurrent.ceiling(4));  // 5 — thread-safe navigation

// ── Performance summary ───────────────────────────────────────────────
// Operation      HashSet    LinkedHashSet   TreeSet   ConcurrentSkipListSet
// ──────────────────────────────────────────────────────────────────────
// add            O(1)*      O(1)*           O(log n)  O(log n)
// remove         O(1)*      O(1)*           O(log n)  O(log n)
// contains       O(1)*      O(1)*           O(log n)  O(log n)
// first/last     O(n)       O(n)            O(log n)  O(log n)
// floor/ceiling  O(n)       O(n)            O(log n)  O(log n)
// subSet         O(n)       O(n)            O(log n)  O(log n)
// iteration      O(cap)     O(size)         O(size)   O(size)
// thread-safe    NO         NO              NO        YES

TreeSet

Red-Black Tree — Structure and Order

Navigation Operations — first, last, floor, ceiling, higher, lower

Range Views — subSet, headSet, tailSet

TreeSet Performance and When to Use It

Related Topics in Collections Framework