Java TreeSet Comparator — How It Silently Drops Duplicates

Most developers think a HashMap is the answer to everything—until they need to iterate in sorted order or find the nearest key. That’s where TreeMap and TreeSet come in: they keep your keys sorted at all times, enforce uniqueness as a side effect, and let you navigate with methods like lowerKey and ceilingEntry. Skip them, and you’ll end up manually sorting collections or writing brittle rank-loops that break the moment your data grows.

How TreeMap and TreeSet Use Comparison to Both Sort and Deduplicate

TreeMap and TreeSet are Red-Black tree implementations in Java that maintain elements in sorted order. The critical mechanic: they use a Comparator (or natural ordering) for both sorting and equality checks. If the Comparator returns 0 for two elements, the map or set treats them as duplicates — the second insertion silently replaces the first. This differs from HashSet/HashMap, which use equals() and hashCode().

When you insert into a TreeSet, the tree walks from the root comparing keys. If the Comparator returns 0 at any node, the existing entry is overwritten; no new node is created. This means two objects that are not equal() but compare as 0 will be treated as identical. The same applies to TreeMap keys. The tree guarantees O(log n) for contains, add, and remove operations.

Use TreeSet/TreeMap when you need a sorted collection and can accept that comparison logic defines identity. Common use cases: maintaining a sorted set of timestamps, implementing range queries (subSet, headSet, tailSet), or building an ordered cache. Never use them when objects have distinct identities but compare equal — you will silently lose data.

TreeSet — When Order Is Non-Negotiable

A TreeSet is a Set — so it never stores duplicates — but unlike HashSet it keeps every element in its natural sorted order at all times. 'Natural order' means whatever Comparable defines for that type: alphabetical for Strings, ascending for numbers, chronological for dates.

The real payoff isn't just iteration order. It's the NavigableSet API: methods like first(), last(), floor(), ceiling(), headSet(), and tailSet() let you slice and query your sorted data without loops. Want every username that comes after 'mike' alphabetically? One line. Want the five closest scores below a threshold? One line.

Internally, TreeSet wraps a TreeMap and stores your elements as keys. Every add(), remove(), and contains() runs in O(log n) — slower than HashSet's O(1) average, but a fair trade when you genuinely need sorted access. Don't use TreeSet by default; use it when the ordering itself is part of the feature you're building.

package io.thecodeforge.collections;

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

public class LeaderboardTreeSet {
    public static void main(String[] args) {
        // io.thecodeforge: Scores are kept sorted (ascending) automatically
        TreeSet<Integer> scores = new TreeSet<>();

        scores.add(4200);
        scores.add(1500);
        scores.add(8750);
        scores.add(3300);
        scores.add(9100);
        scores.add(4200); // duplicate — silently ignored

        System.out.println("All scores (always sorted): " + scores);

        // Lowest and highest score in O(log n)
        System.out.println("Lowest score : " + scores.first());
        System.out.println("Highest score: " + scores.last());

        // floor() returns the greatest element <= 4000
        System.out.println("Highest score at or below 4000: " + scores.floor(4000));

        // subSet with booleans for inclusivity
        NavigableSet<Integer> mainBracket = scores.subSet(3000, true, 9000, false);
        System.out.println("Main bracket [3000, 9000): " + mainBracket);
    }
}

TreeMap — Sorted Keys With All the Power of a Map

TreeMap is to HashMap what TreeSet is to HashSet: it keeps all its keys in sorted order at all times, and it exposes a rich NavigableMap API for range queries, boundary lookups, and sliced views.

The classic use case is any kind of timeline, schedule, or rank-ordered dataset. Imagine you're building a task scheduler. Each task has a deadline (the key) and a description (the value). A TreeMap lets you instantly find the next task due, all tasks due before a certain date, or every task in a given window — without scanning the entire map.

TreeMap also implements SortedMap and NavigableMap, which means you get firstKey(), lastKey(), floorKey(), ceilingKey(), lowerKey(), higherKey(), headMap(), tailMap(), and subMap() — all backed by the same O(log n) Red-Black Tree. You can even get a descending view of the entire map with descendingMap(). These aren't convenience extras; they're the whole reason to choose TreeMap over HashMap.

package io.thecodeforge.collections;

import java.time.LocalDate;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

public class TaskSchedulerTreeMap {
    public static void main(String[] args) {
        // io.thecodeforge: Standardizing chronologically sorted task maps
        TreeMap<LocalDate, String> schedule = new TreeMap<>();

        schedule.put(LocalDate.of(2025, 7, 15), "Submit tax return");
        schedule.put(LocalDate.of(2025, 6, 30), "Renew software licences");
        schedule.put(LocalDate.of(2025, 8, 1),  "Team performance reviews");
        schedule.put(LocalDate.of(2025, 7, 4),  "Deploy v2.0 to production");

        LocalDate today = LocalDate.of(2025, 7, 1);

        // ceilingKey returns the smallest key >= today
        LocalDate nextDeadline = schedule.ceilingKey(today);
        System.out.println("Next task: " + nextDeadline + " - " + schedule.get(nextDeadline));

        // headMap(key, inclusive) provides an efficient view of past entries
        NavigableMap<LocalDate, String> overdue = schedule.headMap(today, false);
        System.out.println("Overdue count: " + overdue.size());
    }
}

NavigableMap and NavigableSet — The Real Reason to Choose Tree

The true power of TreeMap and TreeSet lies in their Navigable interfaces — not just sorted iteration, but the ability to slice, dice, and query your data in logarithmic time. These methods don't copy data; they return live views that reflect ongoing mutations.

• floorKey(k) / ceilingKey(k): Find the nearest key less than/equal or greater than/equal to a target.
• lowerKey(k) / higherKey(k): Strict versions of above (exclusive).
• headMap(k, inclusive): All keys less than (or ≤) k.
• tailMap(k, inclusive): All keys greater than (or ≥) k.
• subMap(from, fromInclusive, to, toInclusive): A contiguous slice.
• descendingMap() / descendingSet(): Reverse-order views without sorting copy.
• pollFirstEntry() / pollLastEntry(): Retrieve and remove boundary entries.

Use these when you need to answer 'what's the next available slot?', 'find all orders within a date range', or 'get the top 5 scores' without ever calling sort().

package io.thecodeforge.collections;

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableApiDemo {
    public static void main(String[] args) {
        // io.thecodeforge: Using NavigableMap for real-time slicing
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "ten");
        map.put(20, "twenty");
        map.put(30, "thirty");
        map.put(40, "forty");
        map.put(50, "fifty");

        // Closest key >= 25
        System.out.println("Ceiling of 25: " + map.ceilingKey(25)); // 30

        // Closest key < 30
        System.out.println("Lower of 30: " + map.lowerKey(30)); // 20

        // Entries between 20 (inclusive) and 40 (exclusive)
        NavigableMap<Integer, String> slice = map.subMap(20, true, 40, false);
        System.out.println("Submap [20,40): " + slice);

        // Reverse order view
        System.out.println("Descending: " + map.descendingMap());
    }
}

Custom Ordering With Comparator — When Natural Order Isn't Enough

Natural order works great for Strings and numbers, but what about your own objects? And what if you want reverse order, or a case-insensitive sort? That's where a Comparator comes in.

Both TreeMap and TreeSet accept a Comparator in their constructor. Once you supply one, it completely overrides natural order — even if your objects implement Comparable. This is powerful, but there's a critical rule: the Comparator you use for ordering becomes the equality definition for the collection. Two elements are considered duplicates if comparator.compare(a, b) == 0, not if a.equals(b). This surprises many developers.

A practical pattern: pass Comparator.reverseOrder() to get a descending TreeMap, which is perfect for leaderboards where you want the highest value first. Or pass String.CASE_INSENSITIVE_ORDER to a TreeSet of strings so 'Apple' and 'apple' are treated as the same entry. The Comparator is your formatting rule for the entire collection.

package io.thecodeforge.collections;

import java.util.Comparator;
import java.util.TreeMap;

public class CustomComparatorDemo {
    record Product(String name, double price) {}

    public static void main(String[] args) {
        // io.thecodeforge: Custom Comparator for secondary sorting
        Comparator<Product> byPriceThenName = Comparator
                .comparingDouble(Product::price)
                .thenComparing(Product::name);

        TreeMap<Product, Integer> inventory = new TreeMap<>(byPriceThenName);
        inventory.put(new Product("Mechanical Keyboard", 120.00), 15);
        inventory.put(new Product("Wireless Mouse", 45.00), 22);
        inventory.put(new Product("USB-C Cable", 15.00), 100);

        inventory.forEach((p, qty) -> System.out.println(p.name() + ": $" + p.price()));
    }
}

TreeMap vs HashMap vs TreeSet vs HashSet — Choosing the Right Tool

The most common mistake is defaulting to HashMap or HashSet out of habit and then discovering you need sorted access later — at which point you're either converting structures or adding sort calls everywhere. Choosing right from the start costs nothing.

The decision is straightforward: if you need to ask range questions ('everything between X and Y'), boundary questions ('what's the closest element to Z?'), or if iteration order must be predictable and sorted, use the Tree variant. If you only ever ask point questions ('does this key exist?', 'give me this value') and don't care about order, stick with the Hash variant for its faster O(1) average operations.

LinkedHashMap and LinkedHashSet are the middle ground — they maintain insertion order but don't sort. Use them when you want predictable iteration without the overhead of sorting. The table below captures the key trade-offs so you can settle this question in seconds during a code review.

package io.thecodeforge.collections;

import java.util.*;

public class ChoosingTheRightCollection {
    public static void main(String[] args) {
        List<String> rawData = List.of("cherry", "apple", "banana");

        // O(1) speed, random order
        Set<String> unordered = new HashSet<>(rawData);
        
        // O(1) speed, maintains "cherry", "apple", "banana" order
        Set<String> insertionOrdered = new LinkedHashSet<>(rawData);

        // O(log n) speed, maintains "apple", "banana", "cherry" order
        Set<String> sorted = new TreeSet<>(rawData);

        System.out.println("TreeSet Order: " + sorted);
    }
}

TreeMap vs HashMap — Detailed Comparison

While both implement Map, TreeMap and HashMap serve fundamentally different purposes. The table below highlights the key differences you need to consider when choosing.

This table is a quick reference for code reviews and design decisions. When in doubt, ask: "Do I need to answer 'what's between X and Y'?" If yes, TreeMap is the answer.

TreeSet vs HashSet — Detailed Comparison

The same trade-offs apply to the Set variants. Here's a direct comparison.

Like the Map counterparts, the decision hinges on whether you ever need ordered iteration or range queries. If you only need uniqueness and fast membership tests, HashSet is the better choice.

Advantages and Disadvantages of TreeMap and TreeSet

Both TreeMap and TreeSet share the same underlying data structure (Red-Black Tree), so their strengths and weaknesses are nearly identical.

Advantages

Disadvantages

These trade-offs are fundamental to the data structure. Use the advantages when you need sorted ordering; avoid the disadvantages by carefully designing keys and comparators.

Advanced NavigableMap Operations: descendingMap, pollFirstEntry, pollLastEntry

Beyond the basic floor/ceiling and sub-range views, NavigableMap offers three powerful methods for boundary manipulation: descendingMap(), pollFirstEntry(), and pollLastEntry(). These are especially useful for leaderboards, job queues, and any scenario where you need to process items in order while mutating the collection.

• descendingMap(): Returns a reverse-order view of the map. No new data is created; iteration over the descending map is just as fast and memory-cheap as iterating forward. Combined with subMap(), you can easily get slices in descending order.
• pollFirstEntry(): Retrieves and removes the entry with the smallest key. This is a single O(log n) operation that both reads and deletes the first entry. Equivalent to firstEntry() + remove(firstKey()) but atomic and more efficient.
• pollLastEntry(): Retrieves and removes the entry with the largest key. Same benefits as pollFirstEntry for the other end.

These methods are commonly used in priority queues where you want to serve items in order while draining the structure. They are also great for implementing round-robin or timeout processing without additional locking or iteration.

package io.thecodeforge.collections;

import java.util.TreeMap;
import java.util.NavigableMap;

public class AdvancedNavigableMap {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 2500);
        scores.put("Bob", 1800);
        scores.put("Charlie", 3200);
        scores.put("Diana", 1500);
        scores.put("Eve", 2900);

        // Descending order view
        NavigableMap<String, Integer> descending = scores.descendingMap();
        System.out.println("Descending order: " + descending);
        // Output: Descending order: {Eve=2900, Charlie=3200, Alice=2500, Bob=1800, Diana=1500}

        // Poll first (lowest) entry
        System.out.println("Poll first (lowest score): " + scores.pollFirstEntry());
        // Output: Poll first (lowest score): Diana=1500
        System.out.println("After pollFirstEntry: " + scores);
        // Output: After pollFirstEntry: {Alice=2500, Bob=1800, Charlie=3200, Eve=2900}

        // Poll last (highest) entry
        System.out.println("Poll last (highest score): " + scores.pollLastEntry());
        // Output: Poll last (highest score): Eve=2900
        System.out.println("After pollLastEntry: " + scores);
        // Output: After pollLastEntry: {Alice=2500, Bob=1800, Charlie=3200}
    }
}

Practice Problems: Interval Scheduling, Range Queries, Sliding Window

The best way to internalize the power of TreeMap and TreeSet is to solve problems that naturally require sorted order and range queries. Below are five practice problems you can implement to sharpen your skills.

1. Interval Scheduling with TreeSet Given a list of intervals (start, end), find the maximum number of non-overlapping intervals you can schedule. Use a TreeSet to store intervals sorted by end time. Iterate through sorted intervals, and when you find one that doesn't overlap with the last scheduled, add it. Demonstrates floor() or last() for boundary checks.

2. Range Sum Queries on a Dynamic Array Maintain a TreeMap of cumulative sums or directly a TreeMap<Integer, Integer> where keys are indices. Support operations: add value at index, query sum between indices. Use subMap() to get entries in the range and compute the sum. Simulates a Fenwick tree without the complexity.

3. Sliding Window Median Given a stream of integers and a window size k, find the median of each window. Use two TreeSets (or one TreeSet with order statistics) to maintain left and right halves. Use last() and first() to get the max of left and min of right. Demonstrates maintaining balance and using boundary methods.

4. Nearest Neighbor in 1D Given a set of points on a line (integers), support insert(x) and query(x) that returns the closest point to x. Use TreeSet and its floor() and ceiling() methods. Compare distances to find nearest. Classic example of why NavigableSet exists.

5. Task Scheduler with Deadline Constraints Given tasks with deadlines and durations, find if all tasks can be scheduled. Use a TreeMap to store tasks sorted by deadline. Iterate from earliest deadline, subtract duration from current time, and if you ever go negative, impossible. Uses firstKey() and pollFirstEntry() efficiently.

Each problem can be solved in < 50 lines of Java using TreeMap/TreeSet. Implement them to gain confidence with the APIs discussed in this article.

Red-Black Trees Under the Hood — Why O(log n) Isn't Magic

TreeMap and TreeSet don't use some generic sorted container. They're backed by a Red-Black tree — a self-balancing binary search tree that guarantees O(log n) for insert, delete, and lookup. That's not a marketing claim; it's a mathematical guarantee.

Why does the balancing matter? Because without it, a BST degenerates into a linked list when you insert sorted data. Your O(log n) becomes O(n), and your production latency graph looks like a cliff. Red-Black trees enforce five invariants that keep the tree height bounded by 2*log2(n+1). Every insert or delete triggers a rotation and recoloring cascade that maintains balance.

The practical takeaway: TreeMap and TreeSet are predictable. They don't have bad days. HashMap has O(1) average but O(n) worst-case under collision attacks or poor hash distribution. Trees give you consistent performance. When you're building latency-sensitive systems — trading systems, real-time dashboards, rate limiters — that predictability beats raw speed every time.

// io.thecodeforge — java tutorial

// Simulate tree depth after inserting sorted data
import java.util.*;

public class TreeRotationSimulation {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        HashSet<Integer> hashSet = new HashSet<>();
        List<Integer> sortedData = new ArrayList<>();

        for (int i = 0; i < 1_000_000; i++) {
            sortedData.add(i);
        }

        // TreeSet: insert sorted data
        long start = System.nanoTime();
        treeSet.addAll(sortedData);
        long treeTime = System.nanoTime() - start;

        // HashSet: insert same sorted data
        start = System.nanoTime();
        hashSet.addAll(sortedData);
        long hashTime = System.nanoTime() - start;

        System.out.println("TreeSet insert time (millions of nanoseconds): " + treeTime / 1_000_000);
        System.out.println("HashSet insert time (millions of nanoseconds): " + hashTime / 1_000_000);
        System.out.println("TreeSet size: " + treeSet.size());
        System.out.println("HashSet size: " + hashSet.size());
    }
}

The NullPointerException Trap — TreeMap Doesn't Tolerate Null Keys

You can stuff null values into a HashMap all day. TreeMap? It throws a NullPointerException in your face the moment you try a null key. This isn't a bug — it's a design decision rooted in comparison logic.

TreeMap sorts keys using either their natural ordering (Comparable) or a provided Comparator. But null isn't an object. You can't call compareTo() on null. So the map punts and fires an exception. However, TreeMap handles null values without complaint — the value side has no ordering constraint.

TreeSet has the same constraint. Since it's backed by a TreeMap, null elements are also rejected. Contrast that with HashSet, which happily accepts null (it goes into bucket 0). This catches devs off guard during refactors: swapping a HashMap for a TreeMap to get sorted iteration suddenly breaks every null-key lookup.

The fix? Either filter nulls before insertion, or write a custom Comparator that explicitly handles nulls by defining an ordering (e.g., nulls first or nulls last). But think hard before doing that — it usually masks a design smell where you shouldn't have null keys at all.

// io.thecodeforge — java tutorial

import java.util.*;

public class NullKeyTrap {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        
        // This works — null value is fine
        scores.put("Alice", null);
        
        try {
            // This throws — null key is not
            scores.put(null, 100);
        } catch (NullPointerException e) {
            System.out.println("Caught NPE on null key: " + e.getMessage());
        }
        
        // TreeSet analog
        TreeSet<String> names = new TreeSet<>();
        names.add("Bob");
        try {
            names.add(null);
        } catch (NullPointerException e) {
            System.out.println("TreeSet also rejects null elements");
        }
        
        System.out.println("TreeMap contents: " + scores);
        System.out.println("TreeSet contents: " + names);
    }
}