What is a TreeSet in Java, and how does it differ from a HashSet?
answer
- Red-black tree = always sorted, O(log n)
- HashSet = hash table, O(1), no order
- TreeSet 'equal' means compareTo==0, not equals()
- TreeSet implements NavigableSet
- TreeSet rejects null (natural ordering)
basics
~10 sA TreeSet is a Set that keeps its elements automatically sorted. A HashSet stores elements in no particular order but is faster. Use TreeSet when you need the elements in order.
solid answer
~40 sA TreeSet is an implementation of the Set interface backed by a red-black tree, so it stores no duplicates and keeps every element in sorted order at all times. Iterating a TreeSet yields ascending order (by natural ordering or a supplied Comparator). A HashSet, by contrast, is backed by a hash table: it gives O(1) average add/contains/remove but has no defined iteration order. TreeSet operations (add, contains, remove) are O(log n) because they walk the tree. So the trade-off is ordering and range queries (TreeSet implements NavigableSet) versus raw speed (HashSet). Choose TreeSet when you need sorted iteration, first/last, or floor/ceiling lookups; choose HashSet when you only need membership testing as fast as possible.
go deeper
Knows TreeSet stays sorted and HashSet is unordered/faster, and can name when to use each.
Explains the red-black tree backing, O(log n) vs O(1), and that null is rejected under natural ordering.
Articulates the compareTo==0 duplicate-detection gotcha vs equals(), and the NavigableSet capabilities that justify choosing TreeSet.
Frames the choice in terms of access patterns and data-structure trade-offs (range queries, ordered iteration) and can reason about memory/cache costs of trees vs hash tables at scale.
## First, what is a Set? A **Set** is a collection that holds **no duplicate elements**. `Set` is an interface in `java.util`; you pick a concrete class to actually store the data. ## The two common implementations - **`HashSet`** is backed by a **hash table** — an array of buckets where each element's position is decided by its `hashCode()`. Looking something up means computing its hash and jumping straight to a bucket, so add/contains/remove are **O(1) on average**. The price: elements come out in **no predictable order**. - **`TreeSet`** is backed by a **red-black tree**, a self-balancing binary search tree. In a binary search tree every node's left subtree holds smaller values and its right subtree holds larger values, so an in-order walk visits elements **in sorted order**. "Self-balancing" means the tree rotates itself after inserts/removes so its height stays about log(n); that keeps add/contains/remove at **O(log n)**. ## What 'sorted' means here A TreeSet must know how to compare two elements. It uses either: 1. **Natural ordering** — the element type implements `Comparable<T>` (its `compareTo` defines the order). `Integer`, `String`, etc. already do. 2. A **`Comparator`** you pass to the constructor, e.g. `new TreeSet<>(Comparator.reverseOrder())`. If neither is available, `add` throws `ClassCastException` at runtime. ## Big consequence: equality is by comparison, not equals() In a HashSet, duplicates are detected with `equals()`/`hashCode()`. In a **TreeSet, two elements are considered the same if `compareTo`/`compare` returns 0** — `equals()` is ignored. This is a classic gotcha: if your comparator says two different objects compare equal, the TreeSet treats them as duplicates. ## When to use which - Need elements **iterated in order**, or need **min/max**, or **range/nearest-neighbour queries** (floor, ceiling, headSet…)? → **TreeSet** (it implements `NavigableSet`). - Only need **fast membership testing** and don't care about order? → **HashSet**. - Need insertion-order iteration but still hashing speed? → `LinkedHashSet` (a third option, not tree-based). ## Complexity summary | Operation | HashSet | TreeSet | |---|---|---| | add/contains/remove | O(1) avg | O(log n) | | ordered iteration | not supported | O(n) | | first/last/floor/ceiling | not supported | O(log n) | Both allow only one `null`? — HashSet allows one `null`; **TreeSet does not allow `null`** when using natural ordering (it would have to call `compareTo` on null and throw `NullPointerException`).
- Why might two non-equal objects be wrongly treated as duplicates in a TreeSet?Because TreeSet decides duplication by whether compareTo/compare returns 0. If the ordering logic ignores a field that equals() considers, two distinct objects can compare as 0 and the second add is silently dropped.
- Which set would you pick to deduplicate a stream while preserving insertion order?LinkedHashSet — it hashes for O(1) membership but iterates in insertion order, unlike HashSet (no order) and TreeSet (sorted order).
saying these in an interview costs you the question
- Saying TreeSet is O(1) like HashSet
- Claiming TreeSet uses equals()/hashCode() for duplicate detection
- Thinking HashSet keeps insertion or sorted order
- Believing you can add null to a natural-ordering TreeSet