TreeSet

TreeSet is an implementation of the Set interface that stores unique elements in sorted order. It is backed by a self-balancing Red-Black Tree, providing ordered iteration and logarithmic-time operations. This is a high-frequency interview topic, commonly compared with HashSet and LinkedHashSet.

What Is TreeSet?

• Sorted set implementation
• Stores unique elements only
• Maintains ascending (natural) order by default
• Does not allow null
• Part of java.util package

Set<Integer> set = new TreeSet<>();
          

Position in Collection Hierarchy

Iterable
   └── Collection
        └── Set
             └── SortedSet
                   └── NavigableSet
                         └── TreeSet
          

How TreeSet Works Internally (Interview Favorite)

• Backed by a Red-Black Tree
• Elements compared using:
• Natural ordering (Comparable)
• Custom ordering (Comparator)
• Guarantees sorted traversal at all times

Key Characteristics of TreeSet

• Sorted order maintained automatically
• No duplicates
• No null elements
• Slower than HashSet / LinkedHashSet
• Not synchronized (not thread-safe)

Creating a TreeSet

1️⃣ Natural Ordering

TreeSet<Integer> set = new TreeSet<>();
set.add(30);
set.add(10);
set.add(20);

System.out.println(set); // [10, 20, 30]
          

2️⃣ Custom Ordering (Comparator)

TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a);
set.add(10);
set.add(30);
set.add(20);

System.out.println(set); // [30, 20, 10]
          

✔ Descending order

Important Methods (Sorted & Navigable Operations)

set.first();        // smallest element
set.last();         // largest element
set.lower(20);      // < 20
set.higher(20);     // > 20
set.floor(20);      // <= 20
set.ceiling(20);    // >= 20
          

Duplicate Handling Example

TreeSet<String> set = new TreeSet<>();
set.add("Java");
set.add("Java");

System.out.println(set); // [Java]
          

• ✔ Duplicate ignored
• ✔ No exception thrown

Null Handling (Very Important)

TreeSet<String> set = new TreeSet<>();
set.add(null); // ❌ NullPointerException
          

❌ null not allowed because comparison is required

Performance Complexity

TreeSet vs HashSet vs LinkedHashSet (Interview Table)

When to Use TreeSet

• Sorted data required
• Range queries needed (headSet, tailSet)
• Ordered traversal is mandatory
• Duplicate elimination + sorting

When NOT to Use TreeSet

• Maximum performance is required
• null values must be stored
• Order does not matter
• Large datasets with frequent inserts (prefer HashSet)

Common Beginner Mistakes

• Adding null values
• Forgetting to implement Comparable for custom objects
• Assuming faster than HashSet
• Using TreeSet when sorting is unnecessary

Interview-Ready Answers

Short Answer

TreeSet is a Set implementation that stores elements in sorted order.

Detailed Answer

In Java, TreeSet implements the NavigableSet interface and stores unique elements in sorted order using a Red-Black Tree. It does not allow null elements and provides logarithmic-time performance for basic operations.

Key Takeaway

Use TreeSet when you need sorted, unique elements. Accept the performance trade-off in exchange for automatic ordering and rich navigation APIs.