TreeSet

TreeSet is a NavigableSet implementation based on a TreeMap, providing sorted elements with O(log n) time complexity for most operations.

Source Code #

View Source on GitHub

Core Implementation #

TreeSet is a thin wrapper around TreeMap, using the map’s keys to store set elements in sorted order:

private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

Implementation Details #

Construction #

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

// Private constructor used by all others
private TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

Add Operation #

public boolean add(E e) {
    return m.put(e, PRESENT) == null;
}

The add operation:

Uses the element as a key in the backing TreeMap
Associates it with the dummy PRESENT value
Returns true if the key was not already present
Returns false if the element was already in the set
Maintains sorted order automatically via TreeMap

Remove Operation #

public boolean remove(Object o) {
    return m.remove(o) == PRESENT;
}

Contains Operation #

public boolean contains(Object o) {
    return m.containsKey(o);
}

Size Operation #

public int size() {
    return m.size();
}

Clear Operation #

public void clear() {
    m.clear();
}

Comparator Access #

public Comparator<? super E> comparator() {
    return m.comparator();
}

public E lower(E e) {
    return m.lowerKey(e);
}

public E floor(E e) {
    return m.floorKey(e);
}

public E ceiling(E e) {
    return m.ceilingKey(e);
}

public E higher(E e) {
    return m.higherKey(e);
}

Poll Methods #

public E pollFirst() {
    Map.Entry<E,Object> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}

public E pollLast() {
    Map.Entry<E,Object> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

SubSet Operations #

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement, boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement, toInclusive));
}

public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}

public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}

public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}

Descending Operations #

public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}

public Iterator<E> descendingIterator() {
    return descendingSet().iterator();
}

Iterator Support #

public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

The iterator is obtained from the navigableKeySet of the backing TreeMap, which means:

It iterates over the elements in ascending order
It supports removal via Iterator.remove()
It’s fail-fast (throws ConcurrentModificationException if set is modified during iteration)

Clone Operation #

public Object clone() {
    TreeSet<E> clone;
    try {
        clone = (TreeSet<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
    
    clone.m = new TreeMap<>(m);
    return clone;
}

Serialization #

private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    
    // Write out size
    s.writeInt(m.size());
    
    // Write out all elements in order
    for (E e : m.keySet())
        s.writeObject(e);
}

private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    
    // Read in size
    int size = s.readInt();
    
    // Read in all elements in the proper order
    buildFromSorted(size, s, null, null);
}

// Optimized reconstruction method
private void buildFromSorted(int size, Iterator<?> it,
                            java.io.ObjectInputStream str, V defaultVal) {
    this.m = new TreeMap<>();
    
    // Use a more efficient TreeMap addAll algorithm when elements are
    // known to be in order
    for (int i = 0; i < size; i++) {
        @SuppressWarnings("unchecked")
        E key = (E) (str != null ? str.readObject() : it.next());
        m.put(key, PRESENT);
    }
}

Performance Characteristics #

Since TreeSet is backed by TreeMap (which uses a red-black tree), it has these performance characteristics:

Time Complexity:
- add(E e): O(log n)
- remove(Object o): O(log n)
- contains(Object o): O(log n)
- size(): O(1)
- iterator().next(): O(1) amortized
- Navigation methods (lower, floor, ceiling, higher): O(log n)
- Subset operations: O(log n) for bounds, O(k) for iteration where k is subset size
Space Complexity: O(n) where n is the number of elements
Memory Overhead: Higher than HashSet due to tree node overhead (color bit, left/right/parent pointers)

Key Properties #

Sorted Order: Elements are maintained in sorted order (natural or comparator-based)
No Duplicates: Enforces the Set contract - no duplicate elements
Null Elements: Does not permit null elements (throws NullPointerException)
Navigable: Supports navigation methods (lower, floor, ceiling, higher)
Not Thread-Safe: Must be externally synchronized for concurrent use
Fail-Fast Iterators: Iterators throw ConcurrentModificationException if set is modified during iteration

Best Practices #

Use for sorted data: When you need elements in sorted order
Choose appropriate comparator: For custom ordering requirements
Consider alternatives:
- HashSet for faster lookups when order doesn’t matter
- LinkedHashSet for insertion-order iteration
- ConcurrentSkipListSet for thread-safe sorted sets
Use navigation methods: Leverage lower, floor, ceiling, higher for efficient range queries
Use subset operations: For efficient range-based operations on sorted data

Common Pitfalls #

Null elements: TreeSet throws NullPointerException for null elements
Mutable elements: Changing an element’s properties that affect ordering can break the set
Concurrent modification: Modifying set while iterating causes ConcurrentModificationException
Performance overhead: O(log n) operations are slower than HashSet’s O(1) for large datasets
Inconsistent comparators: Elements must be mutually comparable using the set’s comparator

Comparison with Other Set Implementations #

Implementation	Ordering	Nulls Allowed	Performance	Thread-Safe	Navigation
TreeSet	Sorted	No	O(log n)	No	Yes
HashSet	Unordered	1 null	O(1) average	No	No
LinkedHashSet	Insertion order	1 null	O(1) average	No	No
ConcurrentSkipListSet	Sorted	No	O(log n)	Yes	Yes

Internal TreeMap Structure #

TreeSet relies on TreeMap’s red-black tree implementation:

// From TreeMap - the underlying structure
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

The red-black tree properties:

Color: Each node is either red or black
Root property: Root is always black
Red property: Red nodes cannot have red children
Black height: All paths from root to leaves have same number of black nodes
Leaf property: All leaves (NIL nodes) are black

Tree Operations #

TreeSet inherits these tree operations from TreeMap:

Rotation Operations #

// Left rotation
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

// Right rotation
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

Balancing Operations #

TreeMap automatically balances the tree after insertions and deletions to maintain O(log n) performance.

TreeMap provides efficient navigation:

lowerKey(K key): Greatest key < given key
floorKey(K key): Greatest key ≤ given key
ceilingKey(K key): Least key ≥ given key
higherKey(K key): Least key > given key

Practical Examples #

Range Queries #

TreeSet<Integer> set = new TreeSet<>();
set.addAll(Arrays.asList(10, 20, 30, 40, 50));

// Get elements between 20 (inclusive) and 40 (exclusive)
NavigableSet<Integer> subset = set.subSet(20, true, 40, false);
// Result: [20, 30]

// Get elements less than 30
NavigableSet<Integer> headSet = set.headSet(30, false);
// Result: [10, 20]

// Get elements greater than or equal to 30
NavigableSet<Integer> tailSet = set.tailSet(30, true);
// Result: [30, 40, 50]

TreeSet<String> words = new TreeSet<>();
words.addAll(Arrays.asList("apple", "banana", "cherry", "date", "fig"));

// Find closest matches
String target = "blueberry";
String floor = words.floor(target);  // "banana"
String ceiling = words.ceiling(target); // "cherry"

Descending Order #

TreeSet<Integer> numbers = new TreeSet<>();
numbers.addAll(Arrays.asList(5, 2, 8, 1, 9));

// Iterate in descending order
for (Integer num : numbers.descendingSet()) {
    System.out.println(num); // 9, 8, 5, 2, 1
}

When to Use TreeSet #

TreeSet is ideal when:

You need elements in sorted order
You frequently perform range queries or navigation operations
You need to maintain elements in a specific comparator order
You can tolerate O(log n) performance for insertions/deletions
You don’t need to store null elements

TreeSet is less suitable when:

You need O(1) performance for basic operations
You need to store null elements
You don’t care about element ordering
Memory efficiency is critical (tree nodes have more overhead than hash table entries)

TreeSet

Source Code #

Core Implementation #

Implementation Details #

Construction #

Add Operation #

Remove Operation #

Contains Operation #

Size Operation #

Clear Operation #

Comparator Access #

Navigation Methods #

Poll Methods #

SubSet Operations #

Descending Operations #

Iterator Support #

Clone Operation #

Serialization #

Performance Characteristics #

Key Properties #

Best Practices #

Common Pitfalls #

Comparison with Other Set Implementations #

Internal TreeMap Structure #

Tree Operations #

Rotation Operations #

Balancing Operations #

Navigation Methods #

Practical Examples #

Range Queries #

Navigation Methods #

Descending Order #

When to Use TreeSet #