Java TreeSet | Complete Tutorial with Examples

What is TreeSet in Java?

TreeSet is a class in the java.util package that implements the NavigableSet interface, which extends SortedSet, which extends Set. It is backed internally by a TreeMap, which itself is a Red-Black Tree — a self-balancing binary search tree. This makes TreeSet the go-to choice whenever you need a collection of unique elements in always-sorted order.

TreeSet guarantees that its elements are always stored in ascending order — either the natural order defined by the element's Comparable implementation, or a custom order defined by a Comparator supplied at construction time. Every add(), remove(), and contains() operation runs in O(log n) time — slower than HashSet's O(1) average, but TreeSet offers something HashSet cannot: sorted iteration and powerful range queries.

Three critical rules define TreeSet behavior: (1) No duplicate elements — duplicates are silently ignored. (2) No null elements — adding null throws NullPointerException. (3) Elements must be mutually comparable — adding an incompatible type throws ClassCastException.

TreeSet Class Hierarchy

Understanding the full interface hierarchy of TreeSet explains why it has such a rich API — it inherits methods from multiple interfaces all the way up to Iterable.

java.lang.Iterable
iterator() — root of all Java iteration
java.util.Collection
add()remove()size()contains()isEmpty()clear()toArray()
java.util.Set
No duplicate elements — overrides Collection contract
java.util.SortedSet
comparator()first()last()headSet(toElement)tailSet(fromElement)subSet(from, to)
java.util.NavigableSet
ceiling(e)floor(e)higher(e)lower(e)pollFirst()pollLast()descendingSet()descendingIterator()
java.util.TreeSet (Concrete Class)
Backed by TreeMap (Red-Black Tree)O(log n) add/remove/containsSorted ascending by defaultImplements SequencedSet (Java 21)
Architecture Diagram

Internal Working of TreeSet — Red-Black Tree

TreeSet is internally backed by a TreeMap. Every element you add to a TreeSet is stored as a key in the backing TreeMap, with a constant dummy value (PRESENT = new Object()). This means TreeSet reuses all of TreeMap's Red-Black Tree machinery.

A Red-Black Tree is a self-balancing Binary Search Tree (BST) that maintains the following five invariants to guarantee O(log n) height:

▶
Property 1 — Node Color — Every node is either RED or BLACK.
▶
Property 2 — Root — The root node is always BLACK.
▶
Property 3 — Null Leaves — All null leaf nodes (NIL sentinels) are considered BLACK.
▶
Property 4 — Red Rule — A RED node cannot have a RED parent or RED child (no two consecutive red nodes on any path).
▶
Property 5 — Black Depth — Every path from a node to its descendant null leaves contains the same number of BLACK nodes.

These invariants together guarantee the tree height is always at most 2 × log₂(n+1), which bounds all operations at O(log n). When add() or remove() violates these properties, the tree performs rotations and recoloring — invisible to the developer — to restore balance automatically.

Why does this matter for you as a developer? Unlike HashSet where worst-case performance degrades to O(n) with a poor hash function, TreeSet's O(log n) guarantee is unconditional — no hash collisions, no load factor resizing, no surprises. For 1 million elements, log₂(1,000,000) ≈ 20 — TreeSet finds any element in at most ~20 comparisons.

TreeSet Constructors

TreeSet provides four constructors, each suited to a different initialization scenario:

☕ JavaTreeSet Constructors

import java.util.*;

public class TreeSetConstructors {
    public static void main(String[] args) {

        // 1. Default constructor — natural ordering (Comparable)
        TreeSet<Integer> ts1 = new TreeSet<>();
        ts1.add(50); ts1.add(10); ts1.add(30);
        System.out.println("Natural order: " + ts1);  // [10, 30, 50]

        // 2. Constructor with Comparator — custom ordering
        TreeSet<Integer> ts2 = new TreeSet<>(Comparator.reverseOrder());
        ts2.add(50); ts2.add(10); ts2.add(30);
        System.out.println("Reverse order: " + ts2);  // [50, 30, 10]

        // 3. Constructor from another Collection
        List<String> list = Arrays.asList("Mango", "Apple", "Banana", "Apple");
        TreeSet<String> ts3 = new TreeSet<>(list);
        System.out.println("From list:     " + ts3);  // [Apple, Banana, Mango]

        // 4. Constructor from another SortedSet — inherits its Comparator
        TreeSet<Integer> ts4 = new TreeSet<>(ts2);  // inherits reverseOrder
        ts4.add(70); ts4.add(20);
        System.out.println("From SortedSet:" + ts4);  // [70, 50, 30, 20, 10]
    }
}

Output

Natural order: [10, 30, 50] Reverse order: [50, 30, 10] From list: [Apple, Banana, Mango] From SortedSet:[70, 50, 30, 20, 10]

TreeSet Methods — Complete Reference

TreeSet inherits methods from Collection, Set, SortedSet, and NavigableSet. Here is the complete reference of the most important methods with examples:

☕ JavaTreeSet — All Key Methods Demo

import java.util.*;

public class TreeSetMethods {
    public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>(Arrays.asList(50, 20, 80, 10, 40, 70, 90, 30, 60));
        System.out.println("TreeSet: " + ts);
        // [10, 20, 30, 40, 50, 60, 70, 80, 90]

        // ── Basic Operations ──────────────────────
        ts.add(55);
        System.out.println("After add(55):    " + ts);
        ts.remove(80);
        System.out.println("After remove(80): " + ts);
        System.out.println("contains(40): " + ts.contains(40));  // true
        System.out.println("size():       " + ts.size());
        System.out.println("isEmpty():    " + ts.isEmpty());

        // ── SortedSet Methods ─────────────────────
        System.out.println("first():      " + ts.first());   // 10
        System.out.println("last():       " + ts.last());    // 90
        System.out.println("comparator(): " + ts.comparator()); // null (natural order)

        // ── NavigableSet Methods ──────────────────
        System.out.println("ceiling(45):  " + ts.ceiling(45)); // 50
        System.out.println("floor(45):    " + ts.floor(45));   // 40
        System.out.println("higher(50):   " + ts.higher(50));  // 55
        System.out.println("lower(50):    " + ts.lower(50));   // 40

        // pollFirst / pollLast — retrieve AND remove
        System.out.println("pollFirst():  " + ts.pollFirst()); // 10
        System.out.println("pollLast():   " + ts.pollLast());  // 90
        System.out.println("After polls:  " + ts);

        // ── Range View Methods ────────────────────
        System.out.println("headSet(50):         " + ts.headSet(50));        // < 50
        System.out.println("tailSet(50):         " + ts.tailSet(50));        // >= 50
        System.out.println("subSet(30, 60):      " + ts.subSet(30, 60));     // 30..59
        System.out.println("subSet(30,true,60,true): " + ts.subSet(30, true, 60, true)); // 30..60

        // descendingSet — reverse order view
        System.out.println("descendingSet(): " + ts.descendingSet());
    }
}

Output

TreeSet: [10, 20, 30, 40, 50, 60, 70, 80, 90] After add(55): [10, 20, 30, 40, 50, 55, 60, 70, 80, 90] After remove(80): [10, 20, 30, 40, 50, 55, 60, 70, 90] contains(40): true size(): 9 isEmpty(): false first(): 10 last(): 90 comparator(): null ceiling(45): 50 floor(45): 40 higher(50): 55 lower(50): 40 pollFirst(): 10 pollLast(): 90 After polls: [20, 30, 40, 50, 55, 60, 70] headSet(50): [20, 30, 40] tailSet(50): [50, 55, 60, 70] subSet(30, 60): [30, 40, 50, 55] subSet(30,true,60,true): [30, 40, 50, 55, 60] descendingSet(): [70, 60, 55, 50, 40, 30, 20]

Natural Ordering with Comparable

When no Comparator is provided to the TreeSet constructor, it uses the element's natural ordering — defined by the element class implementing java.lang.Comparable<T>. All Java wrapper types (Integer, String, Double, etc.) already implement Comparable. For custom objects, you must implement it yourself.

☕ JavaTreeSet with Custom Class — Comparable

import java.util.*;

class Student implements Comparable<Student> {
    int    rollNo;
    String name;
    double cgpa;

    Student(int rollNo, String name, double cgpa) {
        this.rollNo = rollNo;
        this.name   = name;
        this.cgpa   = cgpa;
    }

    // Natural order: by rollNo ascending
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.rollNo, other.rollNo);
    }

    @Override
    public String toString() {
        return rollNo + "-" + name + "(" + cgpa + ")";
    }
}

public class NaturalOrderDemo {
    public static void main(String[] args) {
        TreeSet<Student> students = new TreeSet<>();
        students.add(new Student(103, "Charlie", 8.5));
        students.add(new Student(101, "Alice",   9.2));
        students.add(new Student(105, "Eve",     7.8));
        students.add(new Student(102, "Bob",     8.9));
        students.add(new Student(104, "Diana",   9.5));

        // Automatically sorted by rollNo (Comparable)
        System.out.println("Students by Roll No:");
        students.forEach(System.out::println);

        // Duplicate rollNo — silently ignored
        boolean added = students.add(new Student(101, "Alice-Duplicate", 9.9));
        System.out.println("Duplicate added: " + added);  // false
        System.out.println("Size: " + students.size());    // 5
    }
}

Output

Students by Roll No: 101-Alice(9.2) 102-Bob(8.9) 103-Charlie(8.5) 104-Diana(9.5) 105-Eve(7.8) Duplicate added: false Size: 5

Critical rule: TreeSet uses compareTo() (not equals()) to determine uniqueness. Two objects are considered duplicates if compareTo() returns 0 — even if equals() would return false. Always ensure your compareTo() is consistent with equals() to avoid unexpected behavior.

Custom Ordering with Comparator

When you need a different sort order than natural ordering, or when the element class does not implement Comparable, pass a Comparator to the TreeSet constructor. The TreeSet will use that Comparator for all ordering decisions.

☕ JavaTreeSet with Comparator — Multiple Sort Strategies

import java.util.*;

class Product {
    String name;
    double price;
    int    stock;

    Product(String name, double price, int stock) {
        this.name  = name;
        this.price = price;
        this.stock = stock;
    }

    @Override
    public String toString() {
        return name + "(₹" + price + ", stock=" + stock + ")";
    }
}

public class ComparatorDemo {
    public static void main(String[] args) {
        List<Product> products = Arrays.asList(
            new Product("Laptop",  75000.0, 15),
            new Product("Phone",   25000.0, 50),
            new Product("Tablet",  35000.0, 30),
            new Product("Watch",   15000.0, 80),
            new Product("Earbuds",  5000.0, 120)
        );

        // Sort by price ascending
        TreeSet<Product> byPrice = new TreeSet<>(
            Comparator.comparingDouble(p -> p.price)
        );
        byPrice.addAll(products);
        System.out.println("By Price (asc):");
        byPrice.forEach(p -> System.out.println("  " + p));

        // Sort by price descending
        TreeSet<Product> byPriceDesc = new TreeSet<>(
            Comparator.<Product, Double>comparing(p -> p.price, Comparator.reverseOrder())
        );
        byPriceDesc.addAll(products);
        System.out.println("\nBy Price (desc):");
        byPriceDesc.forEach(p -> System.out.println("  " + p));

        // Sort by name alphabetically
        TreeSet<Product> byName = new TreeSet<>(
            Comparator.comparing(p -> p.name)
        );
        byName.addAll(products);
        System.out.println("\nBy Name:");
        byName.forEach(p -> System.out.println("  " + p));
    }
}

Output

By Price (asc): Earbuds(₹5000.0, stock=120) Watch(₹15000.0, stock=80) Phone(₹25000.0, stock=50) Tablet(₹35000.0, stock=30) Laptop(₹75000.0, stock=15) By Price (desc): Laptop(₹75000.0, stock=15) Tablet(₹35000.0, stock=30) Phone(₹25000.0, stock=50) Watch(₹15000.0, stock=80) Earbuds(₹5000.0, stock=120) By Name: Earbuds(₹5000.0, stock=120) Laptop(₹75000.0, stock=15) Phone(₹25000.0, stock=50) Tablet(₹35000.0, stock=30) Watch(₹15000.0, stock=80)

NavigableSet Methods — ceiling, floor, higher, lower

The NavigableSet interface gives TreeSet its most powerful capability: proximity queries. These methods let you find elements relative to a given value — essential for range searches, autocomplete, scheduling systems, and leaderboard queries.

Method	Returns	Includes boundary?	If none exists
floor(e)	Greatest element ≤ e	✅ Yes — includes e if present	Returns null
lower(e)	Greatest element strictly < e	❌ No — excludes e	Returns null
ceiling(e)	Smallest element ≥ e	✅ Yes — includes e if present	Returns null
higher(e)	Smallest element strictly > e	❌ No — excludes e	Returns null
first()	Smallest element in set	N/A	Throws NoSuchElementException
last()	Largest element in set	N/A	Throws NoSuchElementException
pollFirst()	Removes and returns smallest element	N/A	Returns null
pollLast()	Removes and returns largest element	N/A	Returns null

☕ JavaNavigableSet — Proximity Queries Demo

import java.util.*;

public class NavigableSetDemo {
    public static void main(String[] args) {
        // Simulate exam scores
        TreeSet<Integer> scores = new TreeSet<>(
            Arrays.asList(45, 52, 61, 67, 72, 78, 85, 91, 95)
        );
        System.out.println("Scores: " + scores);

        int query = 70;
        System.out.println("Query value: " + query);
        System.out.println("floor(70)   — highest score <= 70: " + scores.floor(70));    // 67
        System.out.println("ceiling(70) — lowest score >= 70:  " + scores.ceiling(70));  // 72
        System.out.println("lower(70)   — highest score < 70:  " + scores.lower(70));    // 67
        System.out.println("higher(70)  — lowest score > 70:   " + scores.higher(70));   // 72

        // Exact match test
        System.out.println("\nfloor(72):   " + scores.floor(72));    // 72 (includes self)
        System.out.println("lower(72):   " + scores.lower(72));    // 67 (excludes self)
        System.out.println("ceiling(72): " + scores.ceiling(72));  // 72 (includes self)
        System.out.println("higher(72):  " + scores.higher(72));   // 78 (excludes self)

        // null when no match
        System.out.println("\nfloor(40):  " + scores.floor(40));    // null
        System.out.println("ceiling(100):" + scores.ceiling(100));  // null

        // Poll — remove and return extremes
        System.out.println("\npollFirst(): " + scores.pollFirst());  // 45
        System.out.println("pollLast():  " + scores.pollLast());   // 95
        System.out.println("After polls: " + scores);
    }
}

Output

Scores: [45, 52, 61, 67, 72, 78, 85, 91, 95] Query value: 70 floor(70) — highest score <= 70: 67 ceiling(70) — lowest score >= 70: 72 lower(70) — highest score < 70: 67 higher(70) — lowest score > 70: 72 floor(72): 72 lower(72): 67 ceiling(72): 72 higher(72): 78 floor(40): null ceiling(100):null pollFirst(): 45 pollLast(): 95 After polls: [52, 61, 67, 72, 78, 85, 91]

Range View Methods — headSet, tailSet, subSet

TreeSet's range view methods return live views of a portion of the set — not copies. Changes to the original TreeSet are reflected in the view, and changes to the view are reflected in the original set. This makes them extremely memory-efficient for range-based processing.

Method	Returns	Boundary inclusion	Note
headSet(toElement)	Elements strictly < toElement	toElement EXCLUDED	SortedSet version — fixed exclusive end
headSet(toElement, inclusive)	Elements ≤ toElement (if true)	Controlled by boolean	NavigableSet version — inclusive flag
tailSet(fromElement)	Elements ≥ fromElement	fromElement INCLUDED	SortedSet version — fixed inclusive start
tailSet(fromElement, inclusive)	Elements ≥ fromElement (if true)	Controlled by boolean	NavigableSet version — inclusive flag
subSet(from, to)	Elements from ≤ e < to	from INCLUDED, to EXCLUDED	SortedSet version — half-open interval
subSet(from, fromInc, to, toInc)	Custom boundaries	Both controlled by booleans	NavigableSet version — full control
descendingSet()	Reverse-order view of entire set	All elements, reversed	Live view — backed by same tree

☕ JavaRange Views — headSet, tailSet, subSet

import java.util.*;

public class RangeViewDemo {
    public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>(
            Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
        );
        System.out.println("Original: " + ts);

        // headSet — elements strictly less than 50
        System.out.println("headSet(50):           " + ts.headSet(50));
        // headSet with inclusive = true — elements <= 50
        System.out.println("headSet(50, true):     " + ts.headSet(50, true));

        // tailSet — elements >= 60
        System.out.println("tailSet(60):           " + ts.tailSet(60));
        // tailSet with inclusive = false — elements strictly > 60
        System.out.println("tailSet(60, false):    " + ts.tailSet(60, false));

        // subSet — 30 <= e < 70
        System.out.println("subSet(30, 70):        " + ts.subSet(30, 70));
        // subSet inclusive both ends — 30 <= e <= 70
        System.out.println("subSet(30,true,70,true):" + ts.subSet(30, true, 70, true));
        // subSet exclusive both ends — 30 < e < 70
        System.out.println("subSet(30,false,70,false):" + ts.subSet(30, false, 70, false));

        // LIVE VIEW — modifying view affects original
        SortedSet<Integer> head = ts.headSet(50);
        head.remove(10);
        System.out.println("\nAfter removing 10 via headSet view:");
        System.out.println("View:     " + head);
        System.out.println("Original: " + ts);  // 10 is gone from ts too!
    }
}

Output

Original: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] headSet(50): [10, 20, 30, 40] headSet(50, true): [10, 20, 30, 40, 50] tailSet(60): [60, 70, 80, 90, 100] tailSet(60, false): [70, 80, 90, 100] subSet(30, 70): [30, 40, 50, 60] subSet(30,true,70,true):[30, 40, 50, 60, 70] subSet(30,false,70,false):[40, 50, 60] After removing 10 via headSet view: View: [20, 30, 40] Original: [20, 30, 40, 50, 60, 70, 80, 90, 100]

TreeSet vs HashSet vs LinkedHashSet

All three implement the Set interface (no duplicates), but they differ significantly in ordering, performance, and capabilities. Choosing the right one is a critical design decision.

Feature	HashSet	LinkedHashSet	TreeSet
Internal Structure	HashMap (hash table)	LinkedHashMap (hash table + linked list)	TreeMap (Red-Black Tree)
Ordering	No guaranteed order	Insertion order preserved	Always sorted (natural or Comparator)
add / remove / contains	O(1) average	O(1) average	O(log n) guaranteed
Null elements	✅ One null allowed	✅ One null allowed	❌ NullPointerException
Implements SortedSet?	❌ No	❌ No	✅ Yes
Implements NavigableSet?	❌ No	❌ No	✅ Yes
Range queries (headSet, etc)	❌ Not available	❌ Not available	✅ Available
Proximity queries (ceiling, floor)	❌ Not available	❌ Not available	✅ Available
Custom Comparator?	❌ No	❌ No	✅ Yes
Memory usage	Low	Medium (extra linked list pointers)	High (node with left, right, parent, color)
Best use case	Fast membership testing, deduplication	Deduplicate while preserving input order	Sorted unique elements, range queries, ordered traversal

Java 21 — TreeSet as SequencedSet

In Java 21 (JEP 431), TreeSet gained the SequencedSet interface — because TreeSet has a well-defined encounter order (sorted order), it naturally supports the new first/last access and reversed view APIs. This is one of the cleanest improvements to the TreeSet API in decades.

New Method (Java 21)	Behavior in TreeSet	Equivalent Before Java 21
getFirst()	Returns the smallest element (same as first())	ts.first()
getLast()	Returns the largest element (same as last())	ts.last()
removeFirst()	Removes and returns the smallest element (same as pollFirst())	ts.pollFirst()
removeLast()	Removes and returns the largest element (same as pollLast())	ts.pollLast()
reversed()	Returns a live descending-order view of the set	ts.descendingSet()
addFirst(e)	Not supported — TreeSet controls its own order	N/A — throws UnsupportedOperationException
addLast(e)	Not supported — TreeSet controls its own order	N/A — throws UnsupportedOperationException

☕ JavaJava 21 SequencedSet — TreeSet Demo

import java.util.*;

public class SequencedSetDemo {
    public static void main(String[] args) {
        // Java 21 — TreeSet typed as SequencedSet
        SequencedSet<String> cities = new TreeSet<>(
            Set.of("Mumbai", "Delhi", "Pune", "Hyderabad", "Ahmedabad")
        );
        System.out.println("Sorted set: " + cities);

        // Java 21 SequencedSet methods
        System.out.println("getFirst():  " + cities.getFirst());   // Ahmedabad
        System.out.println("getLast():   " + cities.getLast());    // Pune

        // reversed() — live descending view
        SequencedSet<String> reversed = cities.reversed();
        System.out.println("reversed():  " + reversed);

        // Modifying original reflects in reversed view
        ((TreeSet<String>) cities).add("Surat");
        System.out.println("After add Surat — reversed: " + reversed);

        // removeFirst() — removes smallest
        System.out.println("removeFirst(): " + cities.removeFirst());  // Ahmedabad
        System.out.println("After removeFirst: " + cities);

        // addFirst / addLast — NOT supported by TreeSet
        try {
            cities.addFirst("Nashik");
        } catch (UnsupportedOperationException e) {
            System.out.println("addFirst() throws UnsupportedOperationException");
        }
    }
}

Output

Sorted set: [Ahmedabad, Delhi, Hyderabad, Mumbai, Pune] getFirst(): Ahmedabad getLast(): Pune reversed(): [Pune, Mumbai, Hyderabad, Delhi, Ahmedabad] After add Surat — reversed: [Surat, Pune, Mumbai, Hyderabad, Delhi, Ahmedabad] removeFirst(): Ahmedabad After removeFirst: [Delhi, Hyderabad, Mumbai, Pune, Surat] addFirst() throws UnsupportedOperationException

Thread Safety in TreeSet

TreeSet is NOT thread-safe. Concurrent access by multiple threads without external synchronization can corrupt the underlying Red-Black Tree structure, causing infinite loops, incorrect results, or ConcurrentModificationException. Java provides several approaches to use TreeSet safely in multi-threaded environments:

☕ JavaThread-Safe TreeSet — Three Approaches

import java.util.*;
import java.util.concurrent.*;

public class ThreadSafeTreeSet {
    public static void main(String[] args) throws InterruptedException {

        // ── Approach 1: Collections.synchronizedSortedSet ──────────────
        // Simple wrapper — all methods synchronized on the set object
        SortedSet<Integer> syncSet =
            Collections.synchronizedSortedSet(new TreeSet<>());

        syncSet.add(30); syncSet.add(10); syncSet.add(20);

        // IMPORTANT: manual synchronization needed during iteration
        synchronized (syncSet) {
            for (int val : syncSet) {
                System.out.print(val + " ");
            }
        }
        System.out.println();

        // ── Approach 2: ConcurrentSkipListSet ─────────────────────────
        // Best for concurrent sorted set — lock-free, thread-safe
        ConcurrentSkipListSet<Integer> skipSet = new ConcurrentSkipListSet<>();

        Runnable adder = () -> {
            for (int i = 0; i < 5; i++) {
                skipSet.add((int)(Math.random() * 100));
            }
        };

        Thread t1 = new Thread(adder);
        Thread t2 = new Thread(adder);
        t1.start(); t2.start();
        t1.join();  t2.join();

        // ConcurrentSkipListSet always sorted, always thread-safe
        System.out.println("ConcurrentSkipListSet (sorted): " + skipSet);

        // ── Approach 3: External synchronization (advanced) ────────────
        // Use ReentrantReadWriteLock for max performance under high reads
        // (pattern used in production systems — see java.util.concurrent.locks)
    }
}

Recommendation: For thread-safe sorted sets in modern Java applications, prefer ConcurrentSkipListSet over Collections.synchronizedSortedSet(new TreeSet<>()). ConcurrentSkipListSet uses a lock-free skip list that provides better concurrency than a single synchronized mutex on the entire set, and still guarantees sorted order and O(log n) operations.

TreeSet add() Operation — Flowchart

The flowchart below shows exactly what happens internally when you call add(element) on a TreeSet — from comparison to Red-Black Tree rebalancing.

📥 add(element) calledon TreeSet

❓ Is element null?null check

Yes — null

💥 NullPointerExceptionTreeSet rejects null

🔍 Navigate Red-Black Treecompare() or compareTo()

comparison done

❓ compareTo() == 0?Is element already in set?

== 0 (duplicate)

❌ Duplicate — return falseElement not inserted

✅ Insert new nodeAdd as RED node in correct position

inserted

⚖️ Rebalance TreeRotations + recoloring if needed

balanced

✅ return trueElement successfully added

Code Execution Flow — from source to output

Real-World Code Examples

Example 1 — Leaderboard System using TreeSet

☕ JavaGame Leaderboard — TreeSet with Comparator

import java.util.*;

class Player {
    String name;
    int    score;
    int    level;

    Player(String name, int score, int level) {
        this.name  = name;
        this.score = score;
        this.level = level;
    }

    @Override
    public String toString() {
        return String.format("%-12s score=%-6d level=%d", name, score, level);
    }
}

public class Leaderboard {

    // Sorted: score desc → level desc → name asc (tie-break)
    private static final Comparator<Player> RANK_ORDER =
        Comparator.comparingInt((Player p) -> p.score).reversed()
                  .thenComparingInt((Player p) -> p.level).reversed()
                  .thenComparing(p -> p.name);

    private final TreeSet<Player> board = new TreeSet<>(RANK_ORDER);

    public void addPlayer(Player p) { board.add(p); }

    public void printTop(int n) {
        System.out.println("=== Top " + n + " Players ===");
        board.stream().limit(n).forEach(p ->
            System.out.println("  " + p));
    }

    public Player getTopPlayer() { return board.first(); }

    public static void main(String[] args) {
        Leaderboard lb = new Leaderboard();
        lb.addPlayer(new Player("Alice",   9800, 42));
        lb.addPlayer(new Player("Bob",     9800, 45));  // same score, higher level
        lb.addPlayer(new Player("Charlie", 8500, 38));
        lb.addPlayer(new Player("Diana",   11200, 50));
        lb.addPlayer(new Player("Eve",     7300, 30));
        lb.addPlayer(new Player("Frank",   9100, 40));

        lb.printTop(3);
        System.out.println("\n🏆 Champion: " + lb.getTopPlayer().name);
    }
}

Output

=== Top 3 Players === Diana score=11200 level=50 Bob score=9800 level=45 Alice score=9800 level=42 🏆 Champion: Diana

Example 2 — Auto-Complete Suggestion Engine using TreeSet

☕ JavaAuto-Complete using TreeSet Range Views

import java.util.*;

public class AutoComplete {

    private final TreeSet<String> dictionary = new TreeSet<>();

    public void addWord(String word) {
        dictionary.add(word.toLowerCase());
    }

    // Returns all words that start with the given prefix
    public SortedSet<String> suggest(String prefix) {
        prefix = prefix.toLowerCase();
        // Build the upper bound: prefix with last char incremented
        String upperBound = prefix.substring(0, prefix.length() - 1)
                         + (char)(prefix.charAt(prefix.length() - 1) + 1);
        return dictionary.subSet(prefix, true, upperBound, false);
    }

    public static void main(String[] args) {
        AutoComplete ac = new AutoComplete();
        String[] words = {
            "java", "javascript", "jakarta", "jar", "javadoc",
            "jvm", "jre", "jdk", "junit", "jackson",
            "python", "pytorch", "pandas", "pydantic"
        };
        for (String w : words) ac.addWord(w);

        System.out.println("Suggestions for 'ja': " + ac.suggest("ja"));
        System.out.println("Suggestions for 'jav': " + ac.suggest("jav"));
        System.out.println("Suggestions for 'py': " + ac.suggest("py"));
        System.out.println("Suggestions for 'j': " + ac.suggest("j"));
    }
}

Output

Suggestions for 'ja': [jackson, jakarta, jar, java, javadoc, javascript] Suggestions for 'jav': [java, javadoc, javascript] Suggestions for 'py': [pydantic, python, pytorch] Suggestions for 'j': [jackson, jakarta, jar, java, javadoc, javascript, jdk, jre, junit, jvm]

Practice This Code — Live Editor

Advantages and Disadvantages of TreeSet

TreeSet is a highly specialized collection. Understanding its strengths and limitations helps you use it in exactly the right situations.

✅ Advantages

Always SortedElements are automatically maintained in sorted order after every add or remove. No need to sort manually — saving development effort and preventing bugs.

Guaranteed O(log n) PerformanceUnlike HashSet where worst-case degrades with hash collisions, TreeSet's Red-Black Tree guarantees O(log n) for all operations unconditionally — predictable performance at any scale.

Rich NavigableSet APIceiling(), floor(), higher(), lower(), pollFirst(), pollLast(), descendingSet() — these proximity and navigation methods are exclusive to TreeSet and enable complex algorithms with minimal code.

Powerful Range ViewsheadSet(), tailSet(), subSet() return live backed views — ideal for range queries, time-window processing, price bands, and interval lookups without creating copies.

Custom Ordering via ComparatorAny sort order is possible — by length, by frequency, by custom business rules. Pass a Comparator to the constructor and TreeSet handles the rest.

No Duplicates GuaranteedTreeSet enforces element uniqueness automatically. Ideal for deduplicating data when sorted order also matters.

Java 21 SequencedSet SupportgetFirst(), getLast(), reversed(), removeFirst(), removeLast() — clean first/last access without the verbose workarounds needed before Java 21.

❌ Disadvantages

Slower than HashSetO(log n) per operation vs O(1) average for HashSet. For large datasets where order doesn't matter, HashSet is significantly faster.

No Null ElementsAdding null throws NullPointerException because compareTo(null) fails. Use HashSet or LinkedHashSet if null elements are needed.

Higher Memory per NodeEach Red-Black Tree node stores the element plus references to left child, right child, parent, and a color bit — more overhead per element than a HashMap bucket entry.

Not Thread-SafeTreeSet is not synchronized. Multi-threaded use without external synchronization corrupts the tree. Use ConcurrentSkipListSet for concurrent sorted sets.

Elements Must Be ComparableWithout a Comparator, elements must implement Comparable. Adding incompatible types (e.g., mixing String and Integer) throws ClassCastException at runtime.

Live Views Can Surprise YouheadSet(), tailSet(), and subSet() return live backed views. Structural modifications to one affect the other — this is powerful but can cause unexpected behavior if you are not careful.

Java TreeSet — Interview Questions

These are the most frequently asked TreeSet interview questions for Java developer positions — from fresher to senior level. Master all of them.

TreeSet is a Set implementation backed by a Red-Black Tree (via TreeMap) that stores elements in sorted ascending order, with O(log n) operations, and no null elements allowed. HashSet is backed by a HashMap (hash table), has no guaranteed order, provides O(1) average operations, and allows one null element. Use TreeSet when sorted order or range queries are needed; use HashSet for pure fast membership testing.

headSet(toElement) returns a live view of elements strictly less than toElement. tailSet(fromElement) returns a live view of elements greater than or equal to fromElement. subSet(from, to) returns a live view of elements where from ≤ e < to. All three return live backed views — modifications to the view affect the original TreeSet and vice versa. NavigableSet versions of these methods accept boolean inclusive flags for full boundary control.

TreeSet uses compareTo() (from Comparable) or compare() (from Comparator) — NOT equals() — to determine duplicates. If compareTo() or compare() returns 0, the element is considered a duplicate and is not inserted (add() returns false). This is why you must ensure your compareTo() is consistent with equals() — if two objects that are logically equal return 0 from compareTo(), only one will be stored.

No, TreeSet is not thread-safe. Concurrent modification can corrupt the Red-Black Tree structure. The best thread-safe alternative for a sorted set is ConcurrentSkipListSet (java.util.concurrent) — it provides lock-free thread safety, maintains sorted order, and has O(log n) operations. You can also wrap with Collections.synchronizedSortedSet(new TreeSet<>()) but must manually synchronize during iteration.

Java 21 (JEP 431) made TreeSet implement SequencedSet, adding getFirst() (= first()), getLast() (= last()), removeFirst() (= pollFirst()), removeLast() (= pollLast()), and reversed() (= descendingSet()) as standard API. addFirst() and addLast() throw UnsupportedOperationException because TreeSet controls its own order. The main benefit is API uniformity — TreeSet now shares a common interface with List and Deque for first/last operations.

Practice Questions — Test Your Knowledge

Test your understanding of TreeSet with these practice questions — from basic output prediction to real-world design challenges. Try answering before revealing each answer.

1. What is the output? TreeSet<String> ts = new TreeSet<>(); ts.add("Banana"); ts.add("apple"); ts.add("Cherry"); ts.add("banana"); System.out.println(ts);

Medium

2. What does this print and why? TreeSet<Integer> ts = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50)); System.out.println(ts.subSet(20, true, 40, true)); System.out.println(ts.subSet(20, false, 40, false));

Easy

3. A TreeSet<Integer> contains {5, 10, 15, 20, 25}. What does ceiling(15), floor(15), higher(15), lower(15) return?

Easy

4. What exception does TreeSet<Integer> ts = new TreeSet<>(); ts.add(null); throw? Why?

Easy

5. You have a TreeSet sorted by natural order. You call pollFirst() and pollLast() alternately until the set is empty. What is the order of elements retrieved for set {3, 1, 4, 1, 5, 9, 2, 6}?

Hard

6. Why does this code throw an exception at runtime? TreeSet<Object> ts = new TreeSet<>(); ts.add("Hello"); ts.add(42);

Medium

✅ AnswerClassCastException is thrown when adding the second element (42). TreeSet has no Comparator, so it uses natural ordering. When adding Integer 42, TreeSet tries to compare it with the existing String 'Hello' by casting to Comparable and calling compareTo(). A String is not comparable to an Integer, so ClassCastException: class java.lang.String cannot be cast to class java.lang.Integer. Note: adding the first element alone never throws — comparison requires at least two elements.

7. Design a solution: Given a list of timestamps (as long values), find all events that occurred between two given timestamps (inclusive) using TreeSet.

Hard

✅ AnswerTreeSet<Long> events = new TreeSet<>(timestamps); SortedSet<Long> range = events.subSet(startTime, true, endTime, true); This returns a live backed view of all events where startTime ≤ event ≤ endTime in O(log n) time to find boundaries, then O(k) to iterate k results. This is far more efficient than filtering a list with a for-loop (O(n)) and demonstrates why TreeSet is the right tool for time-window queries.

8. Are headSet(), tailSet(), and subSet() views or copies? What happens if you modify the original set while holding a view reference?

Hard

✅ AnswerThey return live backed views — not copies. The view and the original TreeSet share the same underlying Red-Black Tree. Modifications to the original are instantly visible in the view, and modifications to the view (within its bounds) are instantly applied to the original. Attempting to add an element to a view that falls outside the view's boundary throws IllegalArgumentException — the view enforces its range constraint.

Conclusion — When to Use TreeSet

TreeSet is one of Java's most powerful and expressive collection classes — but only when used for the right problems. Its combination of guaranteed sorted order, efficient range views, and NavigableSet proximity queries makes it the ideal choice for a specific category of problems that no other Java collection can solve as elegantly.

Scenario	TreeSet?
Need unique elements always in sorted order	✅ Perfect fit — this is TreeSet's core purpose
Range queries: all elements between X and Y	✅ Use subSet() — O(log n) boundaries, O(k) iteration
Proximity: nearest element to a given value	✅ Use ceiling() / floor() — O(log n)
Priority queue with unique priorities	✅ Use pollFirst() / pollLast() — O(log n)
Auto-complete / prefix search	✅ Use subSet() with prefix bounds
Fast deduplication, order doesn't matter	❌ Use HashSet — O(1) is faster
Preserving insertion order with deduplication	❌ Use LinkedHashSet
Null elements needed	❌ Use HashSet or LinkedHashSet
Multi-threaded concurrent sorted set	❌ Use ConcurrentSkipListSet

Your next steps: explore TreeMap (the key-value counterpart of TreeSet backed by the same Red-Black Tree), study ConcurrentSkipListSet for concurrent sorted-set use cases, and practice applying TreeSet's NavigableSet methods to coding problems on platforms like LeetCode and HackerRank. Problems involving sorted windows, nearest neighbors, and range frequency counting are naturally solved by TreeSet.

TreeSet mastery signals strong data-structures knowledge. The developer who reaches for TreeSet when the problem calls for it — and knows exactly which NavigableSet method to use — writes code that is not only correct but measurably faster and cleaner than naive alternatives. ☕

Frequently Asked Questions (FAQ)

HashSet uses hashing (backed by HashMap) — O(1) average operations, no guaranteed order, allows one null element. TreeSet uses a Red-Black Tree (backed by TreeMap) — O(log n) operations, always sorted in natural or Comparator order, does not allow null elements. Use HashSet for fast membership testing; use TreeSet when sorted iteration or range queries (ceiling, floor, headSet, tailSet) are needed.