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

TreeSet Examples

1. Creating a TreeSet (Natural Sorting)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(30);
        set.add(10);
        set.add(20);
        System.out.println(set);
    }
}
          

Output

[10, 20, 30]

2. TreeSet Does Not Allow Duplicates

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("Java");
        set.add("Java");
        System.out.println(set.size());
    }
}
          

Output

1

3. TreeSet Does NOT Allow null

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        // set.add(null); // ❌ NullPointerException
        System.out.println("Null not allowed");
    }
}
          

4. Sorting Strings Alphabetically

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("Banana");
        set.add("Apple");
        set.add("Orange");
        System.out.println(set);
    }
}
          

Output

[Apple, Banana, Orange]

5. Sorting in Reverse Order (Comparator)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>(Comparator.reverseOrder());
        set.add(10);
        set.add(30);
        set.add(20);
        System.out.println(set);
    }
}
          

Output

[30, 20, 10]

6. Custom Sorting Using Comparator

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<String> set =
            new TreeSet<>((a, b) -> a.length() - b.length());
        set.add("Java");
        set.add("API");
        set.add("Automation");
        System.out.println(set);
    }
}
          

Output

[API, Java, Automation]

7. Iterating Using for-each

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(1, 2, 3));
        for (int x : set) {
            System.out.println(x);
        }
    }
}
          

8. Iterating Using Iterator

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<String> set =
            new TreeSet<>(Arrays.asList("A", "B", "C"));
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}
          

9. Removing Elements

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30));
        set.remove(20);
        System.out.println(set);
    }
}
          

Output

[10, 30]

10. first() and last()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30));
        System.out.println(set.first());
        System.out.println(set.last());
    }
}
          

Output

10
30
          

11. headSet() – Elements Less Than Given Value

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30, 40));
        System.out.println(set.headSet(30));
    }
}
          

Output

[10, 20]

12. tailSet() – Elements Greater Than or Equal

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30, 40));
        System.out.println(set.tailSet(30));
    }
}
          

Output

[30, 40]

13. subSet() – Range View

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30, 40));
        System.out.println(set.subSet(20, 40));
    }
}
          

Output

[20, 30]

14. Navigational Methods (lower, higher, floor, ceiling)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30));
        System.out.println(set.lower(20));
        System.out.println(set.higher(20));
        System.out.println(set.floor(25));
        System.out.println(set.ceiling(25));
    }
}
          

Output

10
30
20
30
          

15. Polling Elements (pollFirst, pollLast)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<Integer> set =
            new TreeSet<>(Arrays.asList(10, 20, 30));
        System.out.println(set.pollFirst());
        System.out.println(set.pollLast());
        System.out.println(set);
    }
}
          

Output

10
30
[20]
          

16. Converting List to TreeSet (Sort + Remove Duplicates)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(3, 1, 2, 2);
        TreeSet<Integer> set = new TreeSet<>(list);
        System.out.println(set);
    }
}
          

Output

[1, 2, 3]

17. Custom Objects with Comparable

class User implements Comparable<User> {
    int id;
    User(int id) { this.id = id; }

    public int compareTo(User u) {
        return this.id - u.id;
    }
}

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<User> set = new TreeSet<>();
        set.add(new User(2));
        set.add(new User(1));
        System.out.println(set.size());
    }
}
          

Output

2

18. Custom Objects with Comparator

import java.util.*;

class User {
    int id;
    User(int id) { this.id = id; }
}

class Demo {
    public static void main(String[] args) {
        TreeSet<User> set =
            new TreeSet<>((a, b) -> a.id - b.id);
        set.add(new User(2));
        set.add(new User(1));
        System.out.println(set.size());
    }
}
          

19. Performance Note (Concept)

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

Explanation

• Backed by Red-Black Tree
• Operations are O(log n)
• Slower than HashSet, faster ordered access

20. Interview Summary – TreeSet

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("Sorted");
        set.add("Unique");
        System.out.println(set);
    }
}
          

Key Points

• Sorted set
• No duplicates
• No null allowed
• Uses Red-Black Tree
• Supports navigational methods

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.