Home/Learn/Java A–Z/TreeSet

TreeSet

Intermediate
Collections Framework

A sorted Set backed by a TreeMap — O(log n) operations with powerful range-query methods for finding nearest elements and iterating ranges.

Overview

TreeSet implements NavigableSet using a TreeMap internally (elements are keys, a constant is the value). Like TreeMap, it keeps elements in sorted order at all times (natural order or custom Comparator). All operations are O(log n). TreeSet adds Set semantics on top of TreeMap's sorted navigation: floor(), ceiling(), lower(), higher(), subSet(), headSet(), tailSet() — all returning elements near or within a range. It is the go-to choice when you need a sorted collection of unique values.

Core Operations & Sorted Iteration

TreeSet elements must implement Comparable or a Comparator must be provided. The natural ordering determines both sort order and equality — two elements that compareTo() == 0 are considered duplicates even if equals() says otherwise. This is the most common TreeSet pitfall.

Iteration always returns elements in ascending sorted order. first() and last() return boundary elements in O(log n).

TreeSetBasics.java
import java.util.*;

public class TreeSetBasics {
    public static void main(String[] args) {
        // Natural order (Integer Comparable)
        TreeSet<Integer> numbers = new TreeSet<>(Set.of(5, 2, 8, 1, 9, 3, 5));
        System.out.println(numbers); // [1, 2, 3, 5, 8, 9] — sorted, no duplicate 5

        System.out.println(numbers.first()); // 1
        System.out.println(numbers.last());  // 9
        System.out.println(numbers.size());  // 6

        // Sorted String set
        TreeSet<String> words = new TreeSet<>(
            List.of("banana", "apple", "cherry", "avocado"));
        System.out.println(words); // [apple, avocado, banana, cherry]

        // Custom Comparator — sort by string length, then alphabetically
        TreeSet<String> byLength = new TreeSet<>(
            Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        byLength.addAll(words);
        System.out.println(byLength); // [apple, banana, avocado, cherry]

        // PITFALL: compareTo == 0 means duplicate, even if equals() differs
        TreeSet<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
        caseInsensitive.add("Apple");
        caseInsensitive.add("apple"); // treated as duplicate — compareTo returns 0
        System.out.println(caseInsensitive.size()); // 1, not 2!
    }
}

NavigableSet — Range Queries

floor(e) — greatest element ≤ e ceiling(e) — smallest element ≥ e lower(e) — greatest element strictly < e higher(e) — smallest element strictly > e subSet(from, fromInclusive, to, toInclusive) — range view headSet(to, inclusive) — elements below to tailSet(from, inclusive) — elements from and above pollFirst() / pollLast() — remove and return boundary descendingSet() — reversed NavigableSet view

TreeSetNavigation.java
import java.util.*;

public class TreeSetNavigation {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>(Set.of(10, 20, 30, 40, 50));

        // Nearest-element lookups — O(log n)
        System.out.println(set.floor(25));   // 20
        System.out.println(set.ceiling(25)); // 30
        System.out.println(set.lower(30));   // 20 — strictly less
        System.out.println(set.higher(30));  // 40 — strictly greater

        // Range subsets (live views backed by original)
        NavigableSet<Integer> mid = set.subSet(20, true, 40, true);
        System.out.println(mid); // [20, 30, 40]

        mid.add(35);             // modifies original set
        System.out.println(set); // [10, 20, 30, 35, 40, 50]

        // headSet — elements strictly below 30
        System.out.println(set.headSet(30));         // [10, 20]
        System.out.println(set.headSet(30, true));   // [10, 20, 30]

        // tailSet — elements from 35 upwards
        System.out.println(set.tailSet(35));         // [35, 40, 50]

        // Poll removes boundary elements
        System.out.println(set.pollFirst()); // 10
        System.out.println(set.pollLast());  // 50
        System.out.println(set);             // [20, 30, 35, 40]

        // Descending view
        System.out.println(set.descendingSet()); // [40, 35, 30, 20]

        // Practical: find all scores in a grade range
        TreeSet<Integer> scores = new TreeSet<>(
            Set.of(45, 62, 78, 83, 91, 95, 55, 70));
        System.out.println("B grades (80–89): " + scores.subSet(80, true, 90, false));
        // B grades (80–89): [83]
    }
}

TreeSet vs HashSet — Decision Guide

HashSet — O(1) average; unordered; use when order does not matter and speed is priority TreeSet — O(log n); sorted; use when you need: • Iteration in sorted order • Range queries (subSet, headSet, tailSet) • Nearest-element lookups (floor, ceiling) • Removing the min/max efficiently

Common interview pattern: use a TreeSet (or PriorityQueue) to maintain a running sorted window, find the kth largest element, or solve interval-overlap problems.

SlidingWindowMax.java
import java.util.*;

// Interview pattern: sliding window median using two TreeSets
public class SlidingWindowMax {

    // Find max in every window of size k — O(n log k) with TreeMap
    public static int[] slidingMax(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        // TreeMap<value, count> to handle duplicates
        TreeMap<Integer, Integer> window = new TreeMap<>();

        for (int i = 0; i < nums.length; i++) {
            // Add new element
            window.merge(nums[i], 1, Integer::sum);

            // Remove element going out of window
            if (i >= k) {
                int out = nums[i - k];
                window.merge(out, -1, Integer::sum);
                if (window.get(out) == 0) window.remove(out);
            }

            // Record max when window is full
            if (i >= k - 1) {
                result[i - k + 1] = window.lastKey(); // O(log k)
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(slidingMax(nums, 3)));
        // [3, 3, 5, 5, 6, 7]
    }
}

Interactive Visualization

«I»Collection
«I»List
«I»Set
«I»Queue
Collection is the root interface. It branches into List, Set, and Queue.
1 / 5

Key Points to Remember

  • TreeSet is backed by a TreeMap — O(log n) all ops; elements always in sorted order
  • Equality in TreeSet is determined by compareTo (not equals) — compareTo==0 means duplicate
  • floor/ceiling/lower/higher give O(log n) nearest-element lookups
  • subSet/headSet/tailSet return live views — mutations propagate to the original
  • pollFirst/pollLast remove and return boundary elements in O(log n)
  • Use TreeSet over HashSet when sorted iteration or range queries are required

Practice TreeSet in the Playground

Run and modify code directly in your browser - no setup needed.

Interview Questions

Sign in to ask Aria
1

What is the internal implementation of TreeSet?

MediumAmazon
2

What is the difference between TreeSet and HashSet?

EasyTCS
3

How does TreeSet determine duplicates — equals() or compareTo()?

MediumGoogle
4

What is the difference between floor() and lower() in TreeSet?

MediumOracle
5

How would you get the kth smallest element from a stream of numbers efficiently?

HardMicrosoft

Ask Aria about TreeSet

Your personal AI tutor — ask anything about this concept

Previous
HashSet & LinkedHashSet
Next
Stack & Deque