java.util.TreeSet<E> is the Set implementation you reach for when sorted order matters. Every element you add is automatically placed in its correct sorted position — first() always returns the smallest, last() always returns the largest, and you can query ranges like "all elements between 100 and 500" in a single method call. The price is O(log n) per operation instead of O(1), but for sorted unique data with range navigation, nothing else in the standard library comes close.

What Is Java TreeSet?

TreeSet<E> is a concrete class in java.util that implements NavigableSet<E>. It stores elements in a self-balancing Red-Black tree, which means elements are always maintained in sorted ascending order. It rejects duplicates, requires elements to be comparable, and provides powerful range navigation methods unavailable on HashSet or LinkedHashSet.

The diagram below shows where TreeSet sits in the full Set hierarchy.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Set<E>                   ← uniqueness contract
                    ├── HashSet<E>                  ← O(1), no order
                    │       └── LinkedHashSet<E>    ← O(1), insertion order
                    └── java.util.SortedSet<E>      ← adds first(), last(), headSet(), tailSet()
                            └── java.util.NavigableSet<E>  ← adds floor(), ceiling(), lower(), higher()
                                    └── java.util.TreeSet<E>  ← Red-Black tree, sorted order

KEY FACTS:
  Package    : java.util
  Since      : Java 1.2
  Backed by  : TreeMap<E, Object> internally
  Ordering   : natural (Comparable) or supplied Comparator — always ascending
  Null       : NOT allowed — compareTo(null) throws NullPointerException
  Duplicates : rejected — two elements where compare returns 0 are the same
  Thread     : NOT thread-safe
  Operations : O(log n) for add, remove, contains — guaranteed by Red-Black tree

The Three Set Implementations at a Glance

FEATURE COMPARISON:

  Feature                HashSet          LinkedHashSet       TreeSet
  ---------------------- ---------------- ------------------- --------------------
  Ordering               None             Insertion order     Sorted (asc)
  add/remove/contains    O(1) average     O(1) average        O(log n) guaranteed
  Null elements          Allowed (1)      Allowed (1)         NOT allowed
  Backed by              HashMap          LinkedHashMap        TreeMap (Red-Black)
  first() / last()       No               No                  O(log n)
  floor() / ceiling()    No               No                  O(log n)
  headSet() / tailSet()  No               No                  O(1) view creation
  Comparator support     No               No                  Yes
  Best for               Fast lookup      Ordered display      Sorted + range ops

When to Use TreeSet

TreeSet is the right choice when sorted unique elements and range-based access are both required. The cost is O(log n) per operation — always, not just on average — because the Red-Black tree must be traversed and rebalanced.

USE TreeSet WHEN:
  1. Elements must be in sorted order for iteration
     — leaderboard scores, alphabetically sorted tags, sorted event timestamps
  2. Range queries are needed:
     — "all scores between 80 and 100": subSet(80, true, 100, true)
     — "top 3 scores": descendingSet() + iteration
     — "all cities alphabetically before Pune": headSet("Pune")
  3. Nearest-element navigation is needed:
     — floor(x)   → largest element <= x
     — ceiling(x) → smallest element >= x
     — lower(x)   → largest element strictly < x
     — higher(x)  → smallest element strictly > x
  4. A sorted view of a dataset needs to be maintained as elements are added

CHOOSE HashSet INSTEAD WHEN:
  - Order is irrelevant and O(1) speed is the priority
  - O(log n) vs O(1) matters at scale (millions of elements, millions of lookups)

CHOOSE LinkedHashSet INSTEAD WHEN:
  - Insertion order (not sorted order) is what matters
  - O(1) operations are required alongside ordered iteration

CHOOSE TreeMap INSTEAD WHEN:
  - Sorted order is needed AND each element has an associated value to look up
  - Range-query results need both key and value, not just the key

NEVER USE TreeSet WHEN:
  - Elements do not implement Comparable AND no Comparator is provided
    → ClassCastException on the second add() call
  - Null elements are needed
    → NullPointerException on any add(null) call

How TreeSet Works Internally

The Red-Black Tree Structure

TreeSet is a thin wrapper around TreeMap<E, Object>, exactly as HashSet wraps HashMap. Every element becomes a key in the backing TreeMap, with a shared static PRESENT dummy object as the value.

TreeSet<Integer> set = new TreeSet<>();
set.add(50); set.add(20); set.add(80); set.add(10); set.add(60);

INTERNALLY → TreeMap<Integer, Object>:

  Red-Black tree after all 5 insertions:

              50 (Black)
            /             \
        20 (Red)         80 (Red)
        /
    10 (Black)   60 (Black — actually between 20 and 80 in BST, shown simplified)

  FULL TREE (actual BST structure):
              50 (B)
            /        \
        20 (R)       80 (R)
       /    \        /
    10 (B) 30(B)  60 (B)

  In-order traversal: 10, 20, 30, 50, 60, 80  ← always sorted ascending
  Height bounded at:  2 × log₂(n+1)            ← Red-Black invariant

  FIVE RED-BLACK INVARIANTS:
  1. Every node is Red or Black
  2. Root is always Black
  3. No two consecutive Red nodes (Red node's parent must be Black)
  4. Every path from a node to its descendant null leaves has the same Black-node count
  5. Null leaves are considered Black

  These invariants guarantee the tree height stays O(log n), preventing degeneration
  to O(n) that would happen with an unbalanced BST on sorted input.

How Comparisons Drive Everything

TreeSet uses compareTo() (natural ordering) or a Comparator (custom ordering) for ALL operations — add(), remove(), contains(), floor(), ceiling(). It never calls equals() or hashCode(). Two elements where compare(a, b) == 0 are considered identical and the duplicate is rejected.

TREESET COMPARISON LOGIC for add(element):

  1. Start at root
  2. compare(element, currentNode.key):
       < 0  → go left
       > 0  → go right
       == 0 → DUPLICATE — reject add(), return false
  3. Repeat from step 2 at the new node
  4. If null is reached → insert new node here
  5. Rebalance to maintain Red-Black invariants — at most O(log n) rotations

  KEY INSIGHT:
  compare() == 0 means "same element" in TreeSet.
  This is independent of equals(). If compare returns 0 but equals returns false,
  TreeSet treats them as duplicates — equals() is never consulted.

  This is why TreeSet's consistency-with-equals contract matters:
  Ideally: (a.compareTo(b) == 0) == (a.equals(b))
  BigDecimal violates this intentionally: 2.0.compareTo(2.00) == 0 but equals returns false
  In a TreeSet<BigDecimal>, 2.0 and 2.00 are treated as the same element.

Core Operations with Examples

Basic add(), contains(), remove() and Size

Java

Try it out

// File: TreeSetBasicsDemo.java

import java.util.TreeSet;

public class TreeSetBasicsDemo {

    public static void main(String[] args) {

        TreeSet<Integer> examScores = new TreeSet<>();

        // add() returns true for new elements, false for duplicates
        System.out.println("=== add() ===");
        System.out.println("add(85) : " + examScores.add(85));  // true
        System.out.println("add(92) : " + examScores.add(92));  // true
        System.out.println("add(78) : " + examScores.add(78));  // true
        System.out.println("add(95) : " + examScores.add(95));  // true
        System.out.println("add(85) : " + examScores.add(85));  // false — duplicate
        System.out.println("add(63) : " + examScores.add(63));  // true
        System.out.println("add(100): " + examScores.add(100)); // true
        System.out.println("TreeSet : " + examScores);          // always sorted!
        System.out.println("Size    : " + examScores.size());   // 6, not 7

        System.out.println();

        // contains() — O(log n), never scans all elements
        System.out.println("=== contains() ===");
        System.out.println("contains(85)  : " + examScores.contains(85));   // true
        System.out.println("contains(50)  : " + examScores.contains(50));   // false

        // remove() — O(log n), rebalances tree after removal
        System.out.println("\n=== remove() ===");
        System.out.println("remove(78) : " + examScores.remove(78));  // true
        System.out.println("remove(50) : " + examScores.remove(50));  // false
        System.out.println("After      : " + examScores);

        // first() and last() — always O(log n) — leftmost and rightmost nodes
        System.out.println("\n=== first() and last() ===");
        System.out.println("first() : " + examScores.first()); // 63 — minimum
        System.out.println("last()  : " + examScores.last());  // 100 — maximum
    }
}

Output:
=== add() ===
add(85) : true
add(92) : true
add(78) : true
add(95) : true
add(85) : false — duplicate
add(63) : true
add(100): true
TreeSet : [63, 78, 85, 92, 95, 100]
Size    : 6

=== contains() ===
contains(85)  : true
contains(50)  : false

=== remove() ===
remove(78) : true
remove(50) : false
After      : [63, 85, 92, 95, 100]

=== first() and last() ===
first() : 63
last()  : 100

NavigableSet Methods — Floor, Ceiling, Lower, Higher

These four methods make TreeSet uniquely powerful for range-based lookups. None of them are available on HashSet or LinkedHashSet.

Java

Try it out

// File: TreeSetNavigationDemo.java

import java.util.TreeSet;

public class TreeSetNavigationDemo {

    public static void main(String[] args) {

        TreeSet<Integer> prices = new TreeSet<>();
        for (int p : new int[]{199, 499, 799, 1199, 1999, 2999, 4999, 7999}) {
            prices.add(p);
        }
        System.out.println("Price tiers: " + prices);
        System.out.println();

        int budget = 1500;

        // floor(e)   — largest element <= e
        System.out.printf("floor(%d)   : %d  (most expensive within budget)%n",
            budget, prices.floor(budget));

        // ceiling(e) — smallest element >= e
        System.out.printf("ceiling(%d) : %d  (cheapest at or above budget)%n",
            budget, prices.ceiling(budget));

        // lower(e)   — largest element strictly < e
        System.out.printf("lower(%d)   : %d  (strictly below budget)%n",
            budget, prices.lower(budget));

        // higher(e)  — smallest element strictly > e
        System.out.printf("higher(%d)  : %d  (just above budget)%n",
            budget, prices.higher(budget));

        System.out.println();

        // Edge cases
        System.out.println("=== Edge cases ===");
        System.out.println("floor(199)    : " + prices.floor(199));    // 199 — exact match
        System.out.println("floor(100)    : " + prices.floor(100));    // null — nothing below
        System.out.println("ceiling(9999) : " + prices.ceiling(9999)); // null — nothing above
        System.out.println("lower(199)    : " + prices.lower(199));    // null — nothing strictly less
        System.out.println("higher(7999)  : " + prices.higher(7999));  // null — nothing above max

        System.out.println();

        // pollFirst() and pollLast() — remove and return
        System.out.println("=== pollFirst() and pollLast() ===");
        System.out.println("pollFirst()   : " + prices.pollFirst()); // removes and returns 199
        System.out.println("pollLast()    : " + prices.pollLast());  // removes and returns 7999
        System.out.println("After polls   : " + prices);
    }
}

Output:
Price tiers: [199, 499, 799, 1199, 1999, 2999, 4999, 7999]

floor(1500)   : 1199  (most expensive within budget)
ceiling(1500) : 1999  (cheapest at or above budget)
lower(1500)   : 1199  (strictly below budget)
higher(1500)  : 1999  (just above budget)

=== Edge cases ===
floor(199)    : 199
floor(100)    : null
ceiling(9999) : null
lower(199)    : null
higher(7999)  : null

=== pollFirst() and pollLast() ===
pollFirst()   : 199
pollLast()    : 7999
After polls   : [499, 799, 1199, 1999, 2999, 4999]

Range Views — headSet, tailSet, subSet

Range views return live, navigable sub-views of the TreeSet. Modifications through the view affect the backing set, and changes to the backing set are visible through the view.

Java

Try it out

// File: TreeSetRangeViewDemo.java

import java.util.TreeSet;

public class TreeSetRangeViewDemo {

    public static void main(String[] args) {

        TreeSet<Integer> scores = new TreeSet<>();
        for (int s : new int[]{45, 55, 62, 70, 78, 84, 88, 91, 95, 100}) {
            scores.add(s);
        }
        System.out.println("All scores: " + scores);
        System.out.println();

        // headSet(toElement) — elements STRICTLY LESS than toElement
        System.out.println("=== headSet() — exclusive by default ===");
        System.out.println("headSet(70)           : " + scores.headSet(70));        // < 70
        System.out.println("headSet(70, true)     : " + scores.headSet(70, true));  // <= 70 (inclusive)

        // tailSet(fromElement) — elements >= fromElement (inclusive by default)
        System.out.println("\n=== tailSet() — inclusive by default ===");
        System.out.println("tailSet(84)           : " + scores.tailSet(84));         // >= 84
        System.out.println("tailSet(84, false)    : " + scores.tailSet(84, false));  // > 84 (exclusive)

        // subSet(from, to) — from inclusive, to exclusive by default
        System.out.println("\n=== subSet() ===");
        System.out.println("subSet(70, 90)           : " + scores.subSet(70, 90));       // [70, 90)
        System.out.println("subSet(70, true, 90, true): " + scores.subSet(70, true, 90, true)); // [70, 90]

        // Range views are LIVE — modification propagates back to original set
        System.out.println("\n=== Live view — removal propagates ===");
        java.util.NavigableSet<Integer> failRange = scores.headSet(60, true);
        System.out.println("Failing scores (<=60): " + failRange);
        failRange.clear(); // removes from the BACKING TreeSet
        System.out.println("After clearing fail range, all scores: " + scores);

        // descendingSet() — reverse-order view
        System.out.println("\n=== descendingSet() — highest first ===");
        System.out.println("Descending: " + scores.descendingSet());
    }
}

Output:
All scores: [45, 55, 62, 70, 78, 84, 88, 91, 95, 100]

=== headSet() — exclusive by default ===
headSet(70)           : [45, 55, 62]
headSet(70, true)     : [45, 55, 62, 70]

=== tailSet() — inclusive by default ===
tailSet(84)           : [84, 88, 91, 95, 100]
tailSet(84, false)    : [88, 91, 95, 100]

=== subSet() ===
subSet(70, 90)           : [70, 78, 84, 88]
subSet(70, true, 90, true): [70, 78, 84, 88, 90]

=== Live view — removal propagates ===
Failing scores (<=60): [45, 55]
After clearing fail range, all scores: [62, 70, 78, 84, 88, 91, 95, 100]

=== Descending: [100, 95, 91, 88, 84, 78, 70, 62]

Custom Ordering with Comparator

When elements do not implement Comparable, or when a non-natural ordering is needed, pass a Comparator to the TreeSet constructor.

Java

Try it out

// File: TreeSetComparatorDemo.java

import java.util.Comparator;
import java.util.Objects;
import java.util.TreeSet;

public class TreeSetComparatorDemo {

    record Product(String sku, String name, double price, int stock) {}

    public static void main(String[] args) {

        // Sort by price ascending, then by name for ties
        Comparator<Product> byPriceThenName =
            Comparator.comparingDouble(Product::price)
                      .thenComparing(Product::name);

        TreeSet<Product> catalogue = new TreeSet<>(byPriceThenName);
        catalogue.add(new Product("P001", "Laptop Stand",    599.0,  45));
        catalogue.add(new Product("P002", "Keyboard Cover",  299.0,  80));
        catalogue.add(new Product("P003", "USB-C Hub",       1299.0, 32));
        catalogue.add(new Product("P004", "Mouse Pad",       199.0,  100));
        catalogue.add(new Product("P005", "Monitor Riser",   799.0,  20));

        // Sorted by price ascending
        System.out.println("=== Sorted by price ===");
        catalogue.forEach(p ->
            System.out.printf("  %-20s Rs.%7.2f  (stock: %d)%n",
                p.name(), p.price(), p.stock()));

        // floor, ceiling work with the Comparator
        Product probe = new Product("", "", 600.0, 0); // probe for price 600
        System.out.println("\nfloor (<=600 by price) : "
            + Objects.requireNonNullElse(catalogue.floor(probe), "none"));
        System.out.println("ceiling (>=600 by price): "
            + Objects.requireNonNullElse(catalogue.ceiling(probe), "none"));

        // Reverse order — most expensive first
        System.out.println("\n=== Descending (most expensive first) ===");
        catalogue.descendingSet().forEach(p ->
            System.out.printf("  %-20s Rs.%7.2f%n", p.name(), p.price()));
    }
}

Output:
=== Sorted by price ===
  Mouse Pad            Rs.   199.00  (stock: 100)
  Keyboard Cover       Rs.   299.00  (stock: 80)
  Laptop Stand         Rs.   599.00  (stock: 45)
  Monitor Riser        Rs.   799.00  (stock: 20)
  USB-C Hub            Rs.  1299.00  (stock: 32)

floor (<=600 by price) : Product[sku=P001, name=Laptop Stand, price=599.0, stock=45]
ceiling (>=600 by price): Product[sku=P005, name=Monitor Riser, price=799.0, stock=20]

=== Descending (most expensive first) ===
  USB-C Hub            Rs.  1299.00
  Monitor Riser        Rs.   799.00
  Laptop Stand         Rs.   599.00
  Keyboard Cover       Rs.   299.00
  Mouse Pad            Rs.   199.00

Real-World Example — PhonePe Transaction History with Range Queries

A payments platform like PhonePe stores transaction amounts for a user and needs to answer range-based analytics queries in real time — total spend in a price band, finding the nearest transaction to a given amount, and filtering transactions above a threshold. TreeSet handles all of these in a single data structure without any sorting step.

Java

Try it out

// File: TransactionRecord.java

import java.util.Objects;

public class TransactionRecord implements Comparable<TransactionRecord> {

    private final String txnId;
    private final double amount;
    private final String category;
    private final String timestamp;

    public TransactionRecord(String txnId, double amount,
                              String category, String timestamp) {
        this.txnId     = txnId;
        this.amount    = amount;
        this.category  = category;
        this.timestamp = timestamp;
    }

    public String getTxnId()    { return txnId;     }
    public double getAmount()   { return amount;    }
    public String getCategory() { return category;  }

    // Primary sort by amount ascending; txnId as tiebreaker to ensure no duplicates are lost
    @Override
    public int compareTo(TransactionRecord other) {
        int cmp = Double.compare(this.amount, other.amount);
        if (cmp != 0) return cmp;
        return this.txnId.compareTo(other.txnId); // tiebreaker
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof TransactionRecord other)) return false;
        return Objects.equals(this.txnId, other.txnId);
    }

    @Override
    public int hashCode() { return Objects.hash(txnId); }

    @Override
    public String toString() {
        return String.format("[%s] Rs.%8.2f  %-14s  %s",
            txnId, amount, category, timestamp);
    }
}

Java

Try it out

// File: TransactionAnalytics.java

import java.util.NavigableSet;
import java.util.TreeSet;

public class TransactionAnalytics {

    private final TreeSet<TransactionRecord> transactions = new TreeSet<>();

    public void record(TransactionRecord txn) {
        transactions.add(txn);
    }

    // Range query — all transactions between minAmount and maxAmount (inclusive)
    public NavigableSet<TransactionRecord> inRange(double minAmount, double maxAmount) {
        TransactionRecord low  = new TransactionRecord("", minAmount, "", "");
        TransactionRecord high = new TransactionRecord("\uFFFF", maxAmount, "", ""); // high tiebreaker
        return transactions.subSet(low, true, high, true);
    }

    // Find the nearest transaction to a given amount
    public TransactionRecord nearestTo(double targetAmount) {
        TransactionRecord probe = new TransactionRecord("", targetAmount, "", "");
        TransactionRecord below = transactions.floor(probe);
        TransactionRecord above = transactions.ceiling(probe);

        if (below == null) return above;
        if (above == null) return below;

        double diffBelow = Math.abs(below.getAmount() - targetAmount);
        double diffAbove = Math.abs(above.getAmount() - targetAmount);
        return diffBelow <= diffAbove ? below : above;
    }

    public void printReport() {
        System.out.println("=".repeat(64));
        System.out.println("  TRANSACTION HISTORY (sorted by amount)");
        System.out.println("=".repeat(64));
        transactions.forEach(t -> System.out.println("  " + t));
        System.out.printf("%n  Total transactions : %d%n", transactions.size());
        System.out.printf("  Minimum amount     : Rs.%.2f%n", transactions.first().getAmount());
        System.out.printf("  Maximum amount     : Rs.%.2f%n", transactions.last().getAmount());
        System.out.println("=".repeat(64));
    }

    public static void main(String[] args) {

        TransactionAnalytics analytics = new TransactionAnalytics();

        analytics.record(new TransactionRecord("T001",  149.00, "Recharge",    "2024-01-05"));
        analytics.record(new TransactionRecord("T002", 1299.00, "Shopping",    "2024-01-07"));
        analytics.record(new TransactionRecord("T003",   49.00, "Food",        "2024-01-08"));
        analytics.record(new TransactionRecord("T004", 5499.00, "Electronics", "2024-01-10"));
        analytics.record(new TransactionRecord("T005",  749.00, "Travel",      "2024-01-11"));
        analytics.record(new TransactionRecord("T006",  299.00, "Food",        "2024-01-12"));
        analytics.record(new TransactionRecord("T007", 3999.00, "Shopping",    "2024-01-14"));
        analytics.record(new TransactionRecord("T008",   89.00, "Recharge",    "2024-01-15"));

        analytics.printReport();

        System.out.println("\n=== Range query: Rs.200 — Rs.1500 ===");
        analytics.inRange(200, 1500)
                 .forEach(t -> System.out.println("  " + t));

        System.out.println("\n=== Nearest transaction to Rs.400 ===");
        System.out.println("  " + analytics.nearestTo(400));

        System.out.println("\n=== Transactions above Rs.1000 (tailSet) ===");
        TransactionRecord threshold = new TransactionRecord("", 1000.0, "", "");
        analytics.transactions.tailSet(threshold)
                 .forEach(t -> System.out.println("  " + t));

        double highSpendTotal = analytics.transactions.tailSet(threshold)
                 .stream().mapToDouble(TransactionRecord::getAmount).sum();
        System.out.printf("%n  Total above Rs.1000: Rs.%.2f%n", highSpendTotal);
    }
}

Output:
================================================================
  TRANSACTION HISTORY (sorted by amount)
================================================================
  [T003] Rs.    49.00  Food            2024-01-08
  [T008] Rs.    89.00  Recharge        2024-01-15
  [T001] Rs.   149.00  Recharge        2024-01-05
  [T006] Rs.   299.00  Food            2024-01-12
  [T005] Rs.   749.00  Travel          2024-01-11
  [T002] Rs.  1299.00  Shopping        2024-01-07
  [T007] Rs.  3999.00  Shopping        2024-01-14
  [T004] Rs.  5499.00  Electronics     2024-01-10

  Total transactions : 8
  Minimum amount     : Rs.49.00
  Maximum amount     : Rs.5499.00
================================================================

=== Range query: Rs.200 — Rs.1500 ===
  [T006] Rs.   299.00  Food            2024-01-12
  [T005] Rs.   749.00  Travel          2024-01-11
  [T002] Rs.  1299.00  Shopping        2024-01-07

=== Nearest transaction to Rs.400 ===
  [T006] Rs.   299.00  Food            2024-01-12

=== Transactions above Rs.1000 (tailSet) ===
  [T002] Rs.  1299.00  Shopping        2024-01-07
  [T007] Rs.  3999.00  Shopping        2024-01-14
  [T004] Rs.  5499.00  Electronics     2024-01-10

  Total above Rs.1000: Rs.10797.00

Performance Considerations

Operation	HashSet	LinkedHashSet	TreeSet
add(e)	O(1) avg	O(1) avg	O(log n) guaranteed
remove(e)	O(1) avg	O(1) avg	O(log n) guaranteed
contains(e)	O(1) avg	O(1) avg	O(log n) guaranteed
first() / last()	N/A	N/A	O(log n)
floor() / ceiling()	N/A	N/A	O(log n)
headSet() / tailSet() view	N/A	N/A	O(1) view creation
Iteration	O(n + capacity)	O(n)	O(n) — in-order
Memory per element	~48 bytes	~64 bytes	~56 bytes (tree node)

O(log n) is always bounded: Unlike HashMap's O(1) average that degrades to O(n) on collision attacks, TreeSet's O(log n) is guaranteed regardless of input order. The Red-Black rebalancing invariants bound tree height at 2 × log₂(n+1), so a tree of 1,000,000 elements has a maximum height of ~40.

Range view cost: headSet(), tailSet(), and subSet() return live view objects in O(1) — they do not copy elements. Iteration over the view is O(k) where k is the number of elements in the range. This makes range queries very efficient: view creation is instant; only the elements actually accessed are traversed.

Thread safety: TreeSet is not thread-safe. For concurrent sorted set access, use ConcurrentSkipListSet from java.util.concurrent — it provides O(log n) operations with full concurrency guarantees.

Best Practices

Always include a tiebreaker in compareTo() or Comparator to avoid silent duplicate loss. If two distinct objects compare as equal (return 0), TreeSet treats them as the same element and rejects the second. For TransactionRecord sorted by amount, two different transactions with the same amount would be considered duplicates — only one would be stored. Include a secondary comparison field like a unique ID to break ties: Comparator.comparingDouble(T::amount).thenComparing(T::id).

Declare the variable as NavigableSet<E> rather than TreeSet<E> when range methods are needed. NavigableSet<Integer> prices = new TreeSet<>() exposes floor(), ceiling(), headSet(), tailSet(), and subSet() — the full navigation API. Set<Integer> prices = new TreeSet<>() hides them. SortedSet<Integer> exposes headSet()/tailSet() but not floor()/ceiling(). Choose the declaration type based on which methods callers need.

Use Comparator.comparing() chains instead of manual compareTo() logic. Java 8's Comparator.comparing(keyExtractor).thenComparing(secondary) is cleaner, null-safe with Comparator.nullsFirst(), and reversible with reversed(). Manual compareTo() implementations are error-prone — the classic bug is returning a.field - b.field for integer comparison, which overflows for large negative values.

Pre-build a HashSet for fast loading, convert to TreeSet when sorted output is needed. Building a TreeSet from 100,000 elements is O(n log n). Building a HashSet from the same elements is O(n), then new TreeSet<>(hashSet) is O(n log n). The total cost is the same, but if sorted access is only needed once (for a sorted report), the HashSet approach is more memory-efficient during the accumulation phase.

Common Mistakes

Mistake 1 — Missing Tiebreaker Causes Silent Duplicate Loss

Java

Try it out

// Product sorted by price only — two products with the same price collide
Comparator<Product> byPriceOnly = Comparator.comparingDouble(Product::getPrice);
TreeSet<Product> products = new TreeSet<>(byPriceOnly);

products.add(new Product("P001", "USB Hub",      599.0));
products.add(new Product("P002", "Laptop Stand", 599.0)); // same price → compare returns 0 → DUPLICATE

System.out.println(products.size()); // 1 — P002 silently dropped!

// CORRECT — add a tiebreaker to distinguish equal-price products
Comparator<Product> byPriceThenId =
    Comparator.comparingDouble(Product::getPrice)
              .thenComparing(Product::getId);
TreeSet<Product> safeProducts = new TreeSet<>(byPriceThenId);
safeProducts.add(new Product("P001", "USB Hub",      599.0));
safeProducts.add(new Product("P002", "Laptop Stand", 599.0)); // different ID — stored
System.out.println(safeProducts.size()); // 2

Mistake 2 — Adding Null Elements

Java

Try it out

TreeSet<String> cities = new TreeSet<>();
cities.add("Mumbai");
cities.add("Delhi");

// WRONG — TreeSet calls compareTo() on the null element
cities.add(null); // throws NullPointerException — compareTo(null) throws

// CORRECT — either avoid null, or use a null-tolerant Comparator
TreeSet<String> withNullSupport = new TreeSet<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
withNullSupport.add(null);    // null placed before all non-null elements
withNullSupport.add("Mumbai");
withNullSupport.add("Delhi");
System.out.println(withNullSupport); // [null, Delhi, Mumbai]

Mistake 3 — Using compareTo() Returns for Numeric Subtraction

Java

Try it out

// WRONG — integer subtraction can overflow for large negative values
class Score implements Comparable<Score> {
    int value;

    @Override
    public int compareTo(Score other) {
        return this.value - other.value; // overflow: Integer.MIN_VALUE - 1 wraps to positive
    }
}

// CORRECT — use Integer.compare() or Double.compare()
@Override
public int compareTo(Score other) {
    return Integer.compare(this.value, other.value); // safe, no overflow
}

Mistake 4 — Modifying an Element's Comparison Field After Insertion

Java

Try it out

// WRONG — mutating the field used in compareTo() after insertion corrupts the tree
class Task implements Comparable<Task> {
    int priority;
    String name;

    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

TreeSet<Task> queue = new TreeSet<>();
Task task = new Task(5, "Deploy");
queue.add(task);

task.priority = 1; // BST property violated — task is in wrong position in tree

queue.contains(task); // may return false — tree traversal goes wrong way
queue.remove(task);   // may fail — cannot find the element via BST path
// Always use immutable comparison fields in TreeSet elements

Interview Questions

Q1. What is TreeSet in Java and what makes it different from HashSet and LinkedHashSet?

TreeSet is a NavigableSet implementation backed by a TreeMap (Red-Black self-balancing binary search tree). It stores elements in sorted ascending order — either natural ordering via Comparable or a supplied Comparator. Unlike HashSet (O(1) average, no order) and LinkedHashSet (O(1) average, insertion order), TreeSet guarantees O(log n) for all operations due to the tree structure, and elements are always iterated in sorted order. It also provides navigation methods — floor(), ceiling(), lower(), higher(), headSet(), tailSet(), subSet() — that the hash-based implementations do not offer.

Q2. How does TreeSet determine duplicate elements?

TreeSet uses compareTo() (natural ordering) or the supplied Comparator for all comparisons — it never calls equals() or hashCode(). Two elements where compare(a, b) == 0 are considered identical, and the second is rejected. This means a class can have equals() returning false for two objects while compareTo() returns 0 — TreeSet treats them as duplicates and only stores one. This is why TreeSet's consistency-with-equals contract recommends that (a.compareTo(b) == 0) == a.equals(b), even though it is not enforced.

Q3. What is the time complexity of TreeSet operations and why is it always O(log n)?

All TreeSet operations — add(), remove(), contains(), first(), last(), floor(), ceiling() — are O(log n) in both average and worst case. This is guaranteed by the Red-Black tree's self-balancing invariants, which bound the tree height at 2 × log₂(n+1) regardless of insertion order. Contrast this with HashMap's O(1) average that can degrade to O(n) on hash collisions (mitigated but not eliminated by Java 8 treeification). TreeSet trades the speed advantage of hashing for the guarantee of sorted order and bounded worst-case performance.

Q4. What happens if you add an element to a TreeSet whose class does not implement Comparable?

The first add() succeeds — the tree is empty, no comparison is needed. The second add() throws ClassCastException at runtime because the tree must compare the new element with the existing one using compareTo(), which does not exist on the class. The compiler does not catch this — generics allow TreeSet<MyClass> even without Comparable. The fix is to either implement Comparable on MyClass or pass a Comparator to the TreeSet constructor.

Q5. What is the difference between headSet(), tailSet(), and subSet()?

All three return live view objects — they do not copy elements. headSet(toElement) returns all elements strictly less than toElement (exclusive by default); the overloaded form headSet(toElement, inclusive) controls the boundary. tailSet(fromElement) returns all elements greater than or equal to fromElement (inclusive by default). subSet(from, to) returns elements from from (inclusive by default) to to (exclusive by default); the four-argument overload allows full control over both boundaries. Modifying the view modifies the backing TreeSet, and changes to the backing set are reflected in all views. Adding an element outside a view's range throws IllegalArgumentException.

Q6. Why can TreeSet not contain null elements?

TreeSet determines element position using compareTo() or a Comparator. Comparing any non-null object with null using compareTo() throws NullPointerException — the Java specification requires compareTo() to throw when called with a null argument. Since TreeSet must compare every new element with existing elements to find its position in the tree, null cannot be placed anywhere in the tree. HashSet can store one null because it uses hashCode() (mapped to bucket 0 for null) and skips compareTo() entirely.

FAQs

Does TreeSet allow duplicate elements?

No. TreeSet rejects any element where compareTo() or the Comparator returns 0 when compared to an existing element. add() returns false for such elements. Note that "duplicate" for TreeSet means compare returns 0 — not necessarily that equals() returns true. Two objects can be logically different (by equals()) but considered duplicates by TreeSet if their comparison fields are identical without a tiebreaker.

Can TreeSet work with a custom sort order?

Yes. Pass a Comparator<E> to the constructor: new TreeSet<>(Comparator.comparing(Product::getPrice)). The Comparator overrides any Comparable ordering the class may have. Java 8 Comparator.comparing() chains are the idiomatic approach: Comparator.comparing(Product::getCategory).thenComparing(Product::getPrice).thenComparing(Product::getId) for multi-level sorting with a tiebreaker.

What is the difference between TreeSet and a sorted ArrayList?

A sorted ArrayList is O(n) for contains() and O(n) for remove() by value. TreeSet is O(log n) for both. Inserting in sorted position in an ArrayList is O(n) (binary search finds position in O(log n), but shifting elements is O(n)). TreeSet.add() is O(log n) with no shifting. TreeSet also provides floor(), ceiling(), and range views — none of which ArrayList supports natively. For sets that require frequent membership checks and range queries, TreeSet is significantly more efficient than a maintained sorted ArrayList.

Is TreeSet iteration always in ascending order?

Yes — for-each, iterators, and stream() on a TreeSet always produce elements in ascending sorted order (or the Comparator order if one was provided). Use descendingSet() to get a descending-order view, or descendingIterator() to iterate in reverse without creating a view object.

What is ConcurrentSkipListSet and when should it replace TreeSet?

ConcurrentSkipListSet from java.util.concurrent is a thread-safe sorted set backed by a skip list (a probabilistic data structure that provides O(log n) expected performance). It supports all NavigableSet operations including floor(), ceiling(), and range views, without any external synchronisation. Use it when multiple threads need to read from and write to a sorted set concurrently. TreeSet with Collections.synchronizedSortedSet() exists but requires manual synchronisation during iteration and provides no atomicity guarantees for compound operations.

How does TreeSet compare to using a sorted list for leaderboards?

A leaderboard backed by TreeSet automatically maintains sorted order on every insertion and removal — no sort() call is ever needed. contains() and remove() by value are O(log n). first() and last() for top and bottom scores are O(log n). subSet() for score ranges is O(1) view creation plus O(k) iteration. A sorted ArrayList requires Collections.sort() after each insertion (O(n log n) or O(n) with binary search + insert) and O(n) for removal by value. For a leaderboard that updates frequently, TreeSet is the correct data structure.

Summary

TreeSet<E> is Java's sorted unique-element collection. Backed by a TreeMap Red-Black tree, every element is always in its correct sorted position — O(log n) for every operation, guaranteed. The real power is in the NavigableSet methods: floor(), ceiling(), lower(), higher(), headSet(), tailSet(), and subSet() enable range queries and nearest-element lookups that no other standard Set implementation provides.

Two rules govern TreeSet correctness: elements must implement Comparable or a Comparator must be supplied, and every comparison must include a tiebreaker field when logically distinct elements can have equal primary comparison values. Violating the second rule causes silent duplicate loss — the most confusing TreeSet bug in production code.

For interviews: explain the Red-Black tree backing and the O(log n) guarantee, describe how duplicates are detected via compareTo() not equals(), walk through the NavigableSet API methods, and explain why null elements cause NullPointerException. These questions appear consistently in Java collections interviews at all levels.

What to Read Next

Continue Learning Collections Framework

Next Step

Queue

Learn how to process elements in first-in, first-out order.

→

CopyOnWriteArrayList

Learn a thread-safe list built for frequent reads, rare writes.

→

Deque

Learn a queue you can add to or remove from at both ends.

→

sorted()

Learn how to sort the elements in a Stream.

→

←

PreviousLinkedHashSet

NextQueue

→