Definition
- Red-Black tree: self-balancing BST guaranteeing O(log n) for add, remove, contains
- Natural ordering: elements implement
Comparable, TreeSet usescompareTo() - Custom ordering: pass a
Comparatorto the constructor - Equality via compareTo: if
compareTo()returns 0, TreeSet treats elements as duplicates (not equals!) - ClassCastException: if elements do not implement Comparable and no Comparator is provided
TreeSet is a filing cabinet that automatically keeps accounts sorted when you drop them in. The cabinet needs a sorting rule: either each account card knows how to compare itself (Comparable), or the bank manager hands the cabinet a rule book (Comparator).
Understanding the Concepts
How does TreeSet sort custom objects?
TreeSet wraps a TreeMap internally (elements are keys, values are a dummy PRESENT constant). All sorting behavior comes from the TreeMap's Red-Black tree.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.*;
public class TreeSetSortingDemo {
// Custom class implementing Comparable
record Account(String id, String holder, BigDecimal balance)
implements Comparable<Account> {
@Override
public int compareTo(Account other) {
int cmp = this.balance.compareTo(other.balance);
return cmp != 0 ? cmp : this.id.compareTo(other.id); // tiebreaker!
}
}
public static void main(String[] args) {
// Natural ordering (Comparable)
TreeSet<Account> byBalance = new TreeSet<>();
byBalance.add(new Account("SAV2001", "Rajesh", new BigDecimal("150000")));
byBalance.add(new Account("CUR3001", "Priya", new BigDecimal("75000")));
byBalance.add(new Account("FD4001", "Amit", new BigDecimal("500000")));
System.out.println("Natural order (by balance):");
byBalance.forEach(a -> System.out.println(" " + a.id() + ": " + a.balance()));
// Custom Comparator: sort by holder name
TreeSet<Account> byName = new TreeSet<>(
Comparator.comparing(Account::holder).thenComparing(Account::id)
);
byName.addAll(byBalance);
System.out.println("\nBy holder name:");
byName.forEach(a -> System.out.println(" " + a.holder() + ": " + a.id()));
}
}
Natural order (by balance):
CUR3001: 75000
SAV2001: 150000
FD4001: 500000
By holder name:
Amit: FD4001
Priya: CUR3001
Rajesh: SAV2001
Why is the tiebreaker important?
If two accounts have the same balance and no tiebreaker, compareTo() returns 0, and TreeSet treats them as duplicates. The second account is silently dropped.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.*;
public class TiebreakerDemo {
record AccountNoTie(String id, BigDecimal balance)
implements Comparable<AccountNoTie> {
@Override
public int compareTo(AccountNoTie other) {
return this.balance.compareTo(other.balance); // no tiebreaker!
}
}
public static void main(String[] args) {
TreeSet<AccountNoTie> set = new TreeSet<>();
set.add(new AccountNoTie("SAV2001", new BigDecimal("150000")));
set.add(new AccountNoTie("CUR3001", new BigDecimal("150000"))); // same balance!
System.out.println("Size (no tiebreaker): " + set.size()); // 1! CUR3001 dropped!
}
}
Size (no tiebreaker): 1
What are common mistakes?
Mistake: Using TreeSet for a class without Comparable
class Transaction { String id; } // no Comparable!
TreeSet<Transaction> set = new TreeSet<>();
set.add(new Transaction()); // first add OK (nothing to compare)
set.add(new Transaction()); // ClassCastException!
// Fix: provide Comparator
TreeSet<Transaction> fixed = new TreeSet<>(Comparator.comparing(t -> t.id));
What should a senior engineer know?
- NavigableSet methods. TreeSet provides first(), last(), lower(e), floor(e), ceiling(e), higher(e), subSet(), headSet(), tailSet(), descendingSet(), pollFirst(), pollLast().
- ConcurrentSkipListSet. The thread-safe equivalent of TreeSet. Uses a skip list instead of a Red-Black tree.
- TreeSet.add returns false for compareTo-0 duplicates. The return value tells you whether the element was actually added.
What are common interview follow-up questions?
- "What happens if two elements have the same compareTo result?" – TreeSet treats them as duplicates.
- "How do you prevent accidental duplicate dropping?" – Add a tiebreaker to the comparator.
- "Can TreeSet contain null?" – No (compareTo throws NPE).
- "What is the time complexity of TreeSet.add?" – O(log n).
Visual Overview
TreeSet Red-Black tree
FD4001 (500K)
/ \
CUR3001 (75K) SAV2001 (150K)
add("LON5001", 200K):
→ compare with root (500K) → less → go left
→ compare with CUR3001 (75K) → greater → go right
→ insert as right child of CUR3001
→ rebalance if needed (Red-Black rules)
Tiebreaker matters:
Without: compareTo(SAV, CUR) with same balance → 0 → duplicate! Dropped.
With: compareTo falls back to id comparison → non-zero → both kept.
Key Takeaway
TreeSet sorts elements automatically using a Red-Black tree. Elements must implement Comparable or a Comparator must be provided. The critical detail is that TreeSet uses compareTo for equality: if two elements compare as zero, the second one is silently dropped as a duplicate.
In the National Bank of India's account leaderboard, Rajesh sorts accounts by balance using a TreeSet. He always includes account ID as a tiebreaker in the comparator to prevent two accounts with identical balances from being merged into one. Without the tiebreaker, Priya's CUR3001 would silently disappear from the leaderboard.
Remember one sentence: TreeSet sorts with a Red-Black tree and treats compareTo-0 as duplicate – always include a tiebreaker in the comparator.
---