Back to Study Material Java

TreeSet in Java

TreeSet is backed by a TreeMap, which in turn uses a self-balancing red-black tree. A red-black tree is a binary search tree that maintains four invariants...

TreeSet in Java

Red-Black Tree and Sorted Order

TreeSet is backed by a TreeMap, which in turn uses a self-balancing red-black tree. A red-black tree is a binary search tree that maintains four invariants to keep the tree approximately balanced: every node is red or black, the root is black, no two consecutive red nodes appear on any path, and all paths from any node to null leaves contain the same number of black nodes. These invariants guarantee that the tree's height stays within O(log n), bounding all basic operations.

Because elements are stored in a binary search tree ordered by comparisons, TreeSet maintains its elements in sorted order at all times. Iterating a TreeSet visits elements in ascending natural order (or in the order defined by a supplied Comparator). The first() and last() methods return the smallest and largest elements in O(log n). The add, remove, and contains operations all run in O(log n) time, which is slower than HashSet's O(1) average but comes with the benefit of ordering.

TreeSet does not permit null elements because inserting null would cause a NullPointerException during comparisons.

Navigation Methods

TreeSet implements NavigableSet, which extends SortedSet and adds powerful range and neighbor query methods. floor(e) returns the greatest element less than or equal to e, or null if none exists. ceiling(e) returns the smallest element greater than or equal to e. lower(e) is strictly less than e, and higher(e) is strictly greater than e. All four run in O(log n).

For range queries, headSet(toElement) returns a view of elements strictly less than toElement, tailSet(fromElement) returns elements greater than or equal to fromElement, and subSet(fromElement, toElement) returns elements in the half-open range [fromElement, toElement). These are live views backed by the original set; changes to the view or the original are reflected in both.

descendingSet() returns a NavigableSet with reversed ordering in O(1) because it wraps the same tree with inverted comparisons rather than copying.

Custom Comparator and Interview Tip

To sort strings case-insensitively: TreeSet<String> ts = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); ts.add("Banana"); ts.add("apple"); ts.add("cherry"); for (String s : ts) System.out.print(s + " "); prints apple Banana cherry in case-insensitive alphabetical order. The Comparator drives both ordering and uniqueness: if two strings compare as equal under the comparator, only the first one is stored even if their equals results differ.

This last point is a key interview trap. TreeSet uses the Comparator (or Comparable natural order) to determine uniqueness, not equals. If you provide a Comparator that returns 0 for two strings that are not equal by equals, only one will be stored. Conversely, if your class's compareTo and equals disagree, TreeSet's behavior diverges from the general Set contract.

An interview tip: when asked to compare HashSet and TreeSet, frame the choice around requirements. Use HashSet when you need O(1) operations and do not care about order. Use TreeSet when you need sorted iteration, range queries, or nearest-element lookups. TreeSet's O(log n) overhead is worthwhile only when the ordering it provides is actually needed.