TreeSet in Java – Sorted Set with Red-Black Tree Internals

TreeSet in Java is a powerful Set implementation that stores elements in sorted order using a Red-Black Tree under the hood. It guarantees logarithmic time complexity for common operations and is ideal when both uniqueness and order matter.

This guide explores TreeSet in depth — its internal structure, performance, code examples, pitfalls, and Java 8+ integration.

---

🔍 What is TreeSet?

• Implements the NavigableSet interface
• Elements are stored in ascending sorted order
• Backed internally by a TreeMap
• Does not allow duplicates or null elements

Set<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
System.out.println(numbers); // [2, 5, 8]

---

🛠️ Internal Working: Red-Black Tree via TreeMap

TreeSet is a wrapper over TreeMap. Each element becomes a key, and a constant dummy value is used.

private transient NavigableMap<E,Object> map;
private static final Object PRESENT = new Object();

Red-Black Tree Features:

• Self-balancing binary search tree
• Guarantees O(log n) time for add, remove, and contains
• Maintains sorted order based on Comparable or Comparator

---

📦 Java Syntax and Basic Operations

TreeSet<String> set = new TreeSet<>();
set.add("Banana");
set.add("Apple");
set.add("Cherry");
System.out.println(set); // [Apple, Banana, Cherry]

Using a custom Comparator:

TreeSet<String> reverseSet = new TreeSet<>(Comparator.reverseOrder());
reverseSet.add("A");
reverseSet.add("C");
reverseSet.add("B");
System.out.println(reverseSet); // [C, B, A]

---

⏱️ Performance Characteristics

Operation	Time Complexity	Details
add()	O(log n)	Due to Red-Black Tree insert
remove()	O(log n)	Tree rebalancing may occur
contains()	O(log n)	Tree traversal
iteration()	O(n)	In-order traversal

---

✅ Real-World Use Cases

• Maintaining a sorted set of elements
• Removing duplicates while keeping sorted order
• Auto-sorted navigation menus, priority tags, or filters
• Data structures requiring range views (headSet, tailSet, subSet)

SortedSet<Integer> ages = new TreeSet<>(List.of(45, 30, 65, 30));
System.out.println(ages.headSet(50)); // [30, 45]

---

🧬 TreeSet and Java 8 Streams

List<String> items = List.of("z", "a", "b", "a");

Set<String> sortedUnique = items.stream()
    .collect(Collectors.toCollection(TreeSet::new));

System.out.println(sortedUnique); // [a, b, z]

---

🔁 TreeSet vs HashSet vs LinkedHashSet

Feature	TreeSet	HashSet	LinkedHashSet
Order	✅ Sorted	❌ None	✅ Insertion
Performance	❌ Slower	✅ Fastest	✅ Fast
Null Support	❌ Risky	✅ One null	✅ One null
Backed By	TreeMap	HashMap	LinkedHashMap

---

❌ Pitfalls and Anti-Patterns

• ❌ Inserting null → NullPointerException
• ❌ Using mutable objects as elements (breaks tree structure)
• ❌ Forgetting to implement Comparable or provide Comparator

✅ Always use consistent comparison logic when implementing custom sorting.

public class Employee implements Comparable<Employee> {
    int id;
    public int compareTo(Employee e) {
        return Integer.compare(this.id, e.id);
    }
}

---

📌 What's New in Java Versions?

Java 8

• Stream API, Collectors.toCollection(TreeSet::new)
• forEach, removeIf

Java 9

• Immutable sorted sets via Set.copyOf() with sort logic

Java 10

• Local variable type inference with var

Java 11

• Minor optimizations in tree-based collections

Java 17 & 21

• JVM tuning and GC performance boosts benefiting Red-Black Tree-backed collections

---

🔄 Refactoring Legacy Code

Before:

List<String> unsorted = Arrays.asList("x", "a", "z", "x");
Collections.sort(unsorted);
Set<String> dedupSorted = new LinkedHashSet<>(unsorted);

After (modern):

Set<String> dedupSorted = new TreeSet<>(unsorted);

---

🧠 Real-World Analogy

A TreeSet is like a filing cabinet that auto-sorts new files by name as you insert them. No duplicates allowed, and you always know the next/previous entry alphabetically.

---

❓ FAQ – Expert-Level Questions

1. Can TreeSet store null values?

   • No, NullPointerException is thrown unless custom Comparator allows it.

2. Is TreeSet thread-safe?

   • No. Use Collections.synchronizedSortedSet() or external synchronization.

3. How does TreeSet avoid duplicates?

   • Based on compareTo() or Comparator.compare()

4. What if multiple elements compare as equal?

   • Only one is retained.

5. Can I get a reverse view of a TreeSet?

   NavigableSet<Integer> desc = treeSet.descendingSet();
   

6. How to sort TreeSet by custom property?

   new TreeSet<>(Comparator.comparing(Employee::getName));
   

7. Can TreeSet have heterogeneous types?

   • No, must be mutually comparable.

8. Which interface does TreeSet implement?

   • NavigableSet, SortedSet, Set

9. How to iterate in descending order?

   for (Integer i : treeSet.descendingSet()) { ... }
   

10. How to safely remove while iterating?

Iterator<Integer> it = treeSet.iterator();
while (it.hasNext()) {
    if (condition) it.remove();
}

---

🏁 Conclusion and Key Takeaways

• TreeSet is your go-to when both order and uniqueness are important
• Internally uses a Red-Black Tree via TreeMap
• Slightly slower than HashSet but far more powerful for ordered sets
• Always use consistent comparison logic and avoid null

💡 Pro Tip: Prefer TreeSet over HashSet when your logic needs sorted data — it’s clean, robust, and expressive.

---