[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_72":87,"_35":88},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":19,"_64":65,"_66":67,"_68":69,"_70":71},"id",106,"title","TreeSet and NavigableSet","slug","java-collections-part-10-treeset-navigable","excerpt","Master sorted set operations using Red-Black trees, NavigableSet methods (ceiling, floor, higher, lower), and when logarithmic complexity beats constant-time hashing.","# Java Collections Compendium Part 10: TreeSet & NavigableSet Operations\n\nMaster sorted set operations with TreeSet and NavigableSet. Learn when logarithmic time complexity beats constant time, how Red-Black trees maintain balance, and when to use ceiling, floor, and range queries for elegant solutions.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| **Topic** | TreeSet, NavigableSet, SortedSet, Red-Black Trees |\n| **Complexity** | Intermediate to Advanced |\n| **Prerequisites** | Part 3 (equals/hashCode), Part 9 (HashSet) |\n| **Time to Master** | 3-4 hours |\n| **Interview Frequency** | High (tree operations, NavigableSet methods) |\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. Understand TreeSet's Red-Black tree implementation\n2. Use NavigableSet operations (ceiling, floor, higher, lower) effectively\n3. Create efficient range queries with subset views\n4. Choose between TreeSet and HashSet for different use cases\n5. Avoid ClassCastException with proper Comparable/Comparator usage\n\n### Interactive Visualizer\n\nExplore how TreeSet maintains a Binary Search Tree structure - watch as elements are inserted and searched with O(log n) complexity:\n\n```visualizer-treeset\ncontrols: true\n```\n\n---\n\n## Production Story: The Range Query Performance Disaster\n\n### The Incident\n\nOur analytics dashboard was timing out. The query to find all events between two timestamps was taking 30+ seconds for power users with millions of events.\n\nThe problematic code:\n\n```java\n// EventAnalytics.java - The slow approach\npublic List getEventsBetween(LocalDateTime start, LocalDateTime end) {\n Set allEvents = userEventStore.getAllEvents(userId); // HashSet\n List result = new ArrayList<>();\n\n for (Event event : allEvents) {\n if (!event.getTimestamp().isBefore(start) &&\n !event.getTimestamp().isAfter(end)) {\n result.add(event); // O(n) - checking ALL events\n }\n }\n\n Collections.sort(result, Comparator.comparing(Event::getTimestamp));\n return result;\n}\n```\n\nFor a user with 2 million events, this method:\n1. Iterated through all 2M events: O(n)\n2. Sorted the results: O(k log k) where k is result size\n3. Total time: ~30 seconds\n\n### The Fix: TreeSet with Range Query\n\n```java\n// EventAnalytics.java - The fast approach\npublic class EventStore {\n // Events sorted by timestamp\n private final NavigableSet events = new TreeSet<>(\n Comparator.comparing(Event::getTimestamp)\n );\n\n public List getEventsBetween(LocalDateTime start, LocalDateTime end) {\n // Create boundary events for the query\n Event startBoundary = Event.withTimestamp(start);\n Event endBoundary = Event.withTimestamp(end);\n\n // O(log n) to find range, O(k) to iterate results\n return new ArrayList<>(\n events.subSet(startBoundary, true, endBoundary, true)\n );\n }\n}\n```\n\n**Performance improvement:**\n- Before: O(n) iteration + O(k log k) sort = 30 seconds\n- After: O(log n) range lookup + O(k) iteration = 50 milliseconds\n- **600x faster!**\n\n### Why TreeSet Wins for Range Queries\n\n```text\nHashSet for timestamp lookup:\n┌─────────────────────────────────────────────────────────────────────┐\n│ Bucket 0 Bucket 1 Bucket 2 ... Bucket n │\n│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │\n│ │ 3pm │ │ 9am │ │ 6pm │ │11am │ Events scattered │\n│ └─────┘ └─────┘ └─────┘ └─────┘ by hash, not time │\n│ │\n│ To find 10am-2pm: Must check ALL buckets! │\n└─────────────────────────────────────────────────────────────────────┘\n\nTreeSet for timestamp lookup:\n┌─────────────────────────────────────────────────────────────────────┐\n│ 12pm │\n│ / \\ │\n│ 9am 3pm │\n│ / \\ / \\ │\n│ 8am 10am 1pm 6pm │\n│ │\n│ To find 10am-2pm: Navigate tree to 10am, iterate to 2pm │\n│ O(log n) to start + O(k) for k results │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n### Lessons Learned\n\n1. **HashSet is O(1) for exact match, but O(n) for range queries**\n2. **TreeSet is O(log n) for everything, including range queries**\n3. **NavigableSet's subSet() is a view, not a copy** - very efficient\n4. **Choose data structure based on query patterns**, not just insert/lookup\n\n---\n\n## Mental Model: The Library Card Catalog\n\nThink of TreeSet as an old-school library card catalog:\n\n```text\n┌─────────────────────────────────────────────────────────────────────┐\n│ LIBRARY CARD CATALOG │\n├─────────────────────────────────────────────────────────────────────┤\n│ │\n│ HashSet = Pile of Cards (fast to find exact title) │\n│ ┌─────┐┌─────┐┌─────┐┌─────┐┌─────┐┌─────┐ │\n│ │ Zoo ││ Art ││ Math││ Web ││ Java││ SQL │ Unsorted pile │\n│ └─────┘└─────┘└─────┘└─────┘└─────┘└─────┘ Find \"Java\" = O(1) │\n│ Find \"J-L\" = O(n) │\n│ │\n│ TreeSet = Sorted Card Catalog (fast for ranges) │\n│ ┌─────┬─────┬─────┬─────┬─────┬─────┐ │\n│ │ Art │ Java│ Math│ SQL │ Web │ Zoo │ Alphabetically sorted │\n│ └─────┴─────┴─────┴─────┴─────┴─────┘ │\n│ │\n│ Find \"Java\" = O(log n) - binary search │\n│ Find \"J-M\" = O(log n) - go to J, stop at M │\n│ │\n│ NavigableSet operations: │\n│ • ceiling(\"K\") = \"Math\" (smallest >= K) │\n│ • floor(\"K\") = \"Java\" (largest <= K) │\n│ • higher(\"Java\") = \"Math\" (smallest > Java) │\n│ • lower(\"Math\") = \"Java\" (largest < Math) │\n│ │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## Deep Dive: TreeSet Internals\n\n### Red-Black Tree Basics\n\nTreeSet is backed by TreeMap, which uses a **Red-Black Tree** - a self-balancing binary search tree:\n\n```text\nRed-Black Tree Properties:\n1. Every node is either red or black\n2. Root is always black\n3. Leaves (NIL) are black\n4. Red node's children must be black\n5. All paths from root to leaves have same number of black nodes\n\nThis guarantees O(log n) height, thus O(log n) operations.\n\nExample TreeSet with {3, 7, 10, 12, 15, 20, 25}:\n\n [12B]\n / \\\n [7R] [20R]\n / \\ / \\\n [3B] [10B] [15B] [25B]\n\nB = Black, R = Red\n\nHeight is always O(log n) due to balancing rules.\n```\n\n### TreeSet Construction\n\n```java\n// Natural ordering (elements must implement Comparable)\nTreeSet set1 = new TreeSet<>();\nset1.add(\"banana\");\nset1.add(\"apple\");\nset1.add(\"cherry\");\n// Order: [apple, banana, cherry]\n\n// Custom Comparator\nTreeSet set2 = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);\nset2.add(\"Apple\");\nset2.add(\"BANANA\");\nset2.add(\"cherry\");\n// Order: [Apple, BANANA, cherry]\n\n// Comparator with lambda\nTreeSet byAge = new TreeSet<>(\n Comparator.comparingInt(Person::getAge)\n .thenComparing(Person::getName)\n);\n\n// From another collection\nList numbers = Arrays.asList(5, 2, 8, 1, 9);\nTreeSet sorted = new TreeSet<>(numbers);\n// Order: [1, 2, 5, 8, 9]\n```\n\n### Comparable vs Comparator\n\n```java\n// Option 1: Implement Comparable in the class\npublic class Event implements Comparable {\n private LocalDateTime timestamp;\n private String name;\n\n @Override\n public int compareTo(Event other) {\n return this.timestamp.compareTo(other.timestamp);\n }\n}\n\nTreeSet events = new TreeSet<>(); // Uses natural ordering\n\n// Option 2: Provide Comparator at construction\npublic class Event { // No Comparable needed\n private LocalDateTime timestamp;\n private String name;\n}\n\nTreeSet events = new TreeSet<>(\n Comparator.comparing(Event::getTimestamp)\n);\n\n// ❌ WRONG: Neither Comparable nor Comparator\npublic class Event { // Not Comparable\n // ...\n}\nTreeSet events = new TreeSet<>();\nevents.add(new Event()); // 💥 ClassCastException!\n```\n\n### ClassCastException Deep Dive\n\n```java\n// This is a RUNTIME error, not compile-time!\npublic class Product {\n private String name;\n private double price;\n // No Comparable implementation\n}\n\nTreeSet products = new TreeSet<>();\nproducts.add(new Product(\"A\", 10.0));\n// 💥 ClassCastException: Product cannot be cast to Comparable\n\n// The exception is thrown at add(), not at construction!\n// TreeSet is created successfully, fails on first add.\n\n// Fix 1: Implement Comparable\npublic class Product implements Comparable {\n @Override\n public int compareTo(Product other) {\n return Double.compare(this.price, other.price);\n }\n}\n\n// Fix 2: Provide Comparator\nTreeSet products = new TreeSet<>(\n Comparator.comparing(Product::getPrice)\n);\n```\n\n---\n\n## Deep Dive: NavigableSet Operations\n\n### Core Navigation Methods\n\n```java\nNavigableSet set = new TreeSet<>();\nset.addAll(Arrays.asList(10, 20, 30, 40, 50));\n\n// ceiling(e) - smallest element >= e\nset.ceiling(25); // 30\nset.ceiling(30); // 30 (inclusive)\nset.ceiling(55); // null\n\n// floor(e) - largest element <= e\nset.floor(25); // 20\nset.floor(20); // 20 (inclusive)\nset.floor(5); // null\n\n// higher(e) - smallest element > e (strictly greater)\nset.higher(30); // 40\nset.higher(25); // 30\nset.higher(50); // null\n\n// lower(e) - largest element < e (strictly less)\nset.lower(30); // 20\nset.lower(25); // 20\nset.lower(10); // null\n```\n\n### Visual Guide to Navigation\n\n```text\nNavigableSet: [10, 20, 30, 40, 50]\n\nQuery: element = 25\n\nceiling(25) = 30 floor(25) = 20\n ↓ ↓\n ● ●\n 10----20----30----40----50\n ↑ ↑\n floor ceiling\n\nhigher(25) = 30 lower(25) = 20\n(same as ceiling because 25 not in set)\n\nQuery: element = 30 (exists in set)\n\nceiling(30) = 30 floor(30) = 30\nhigher(30) = 40 lower(30) = 20\n```\n\n### Polling Operations\n\n```java\nNavigableSet set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));\n\n// pollFirst() - removes and returns smallest\nInteger first = set.pollFirst(); // 10, set is now [20, 30, 40, 50]\n\n// pollLast() - removes and returns largest\nInteger last = set.pollLast(); // 50, set is now [20, 30, 40]\n\n// first() and last() - get without removing\nInteger smallest = set.first(); // 20\nInteger largest = set.last(); // 40\n\n// Use case: Priority processing\nNavigableSet taskQueue = new TreeSet<>(\n Comparator.comparing(Task::getPriority)\n);\nwhile (!taskQueue.isEmpty()) {\n Task highest = taskQueue.pollFirst();\n process(highest);\n}\n```\n\n---\n\n## Deep Dive: Subset Views\n\n### subSet(), headSet(), tailSet()\n\n```java\nNavigableSet set = new TreeSet<>();\nset.addAll(Arrays.asList(10, 20, 30, 40, 50, 60, 70));\n\n// subSet(from, fromInclusive, to, toInclusive)\nNavigableSet sub = set.subSet(20, true, 50, false);\n// Result: [20, 30, 40] - includes 20, excludes 50\n\n// headSet(to, inclusive) - elements less than 'to'\nNavigableSet head = set.headSet(40, true);\n// Result: [10, 20, 30, 40]\n\n// tailSet(from, inclusive) - elements greater than or equal to 'from'\nNavigableSet tail = set.tailSet(40, false);\n// Result: [50, 60, 70]\n\n// Legacy SortedSet methods (exclusive endpoints)\nSortedSet subOld = set.subSet(20, 50); // [20, 30, 40]\nSortedSet headOld = set.headSet(40); // [10, 20, 30]\nSortedSet tailOld = set.tailSet(40); // [40, 50, 60, 70]\n```\n\n### Views Are Live!\n\n```java\nNavigableSet original = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));\nNavigableSet view = original.subSet(20, true, 40, true);\n\nSystem.out.println(view); // [20, 30, 40]\n\n// Add to original - appears in view if in range\noriginal.add(25);\nSystem.out.println(view); // [20, 25, 30, 40]\n\n// Add to original - outside range, not in view\noriginal.add(45);\nSystem.out.println(view); // [20, 25, 30, 40] (unchanged)\n\n// Modify through view - affects original\nview.remove(25);\nSystem.out.println(original); // [10, 20, 30, 40, 45, 50]\n\n// ⚠️ Adding element outside range to view throws exception\nview.add(50); // 💥 IllegalArgumentException: key out of range\n```\n\n### Descending Views\n\n```java\nNavigableSet set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));\n\n// Get descending view (reversed order)\nNavigableSet descending = set.descendingSet();\nSystem.out.println(descending); // [50, 40, 30, 20, 10]\n\n// Descending iterator\nIterator descIt = set.descendingIterator();\nwhile (descIt.hasNext()) {\n System.out.println(descIt.next()); // 50, 40, 30, 20, 10\n}\n\n// Changes to descending view affect original\ndescending.add(35);\nSystem.out.println(set); // [10, 20, 30, 35, 40, 50]\n\n// Useful for \"top N\" queries\nNavigableSet scores = new TreeSet<>();\n// Get top 10 scores\nList topTen = scores.descendingSet().stream()\n .limit(10)\n .collect(Collectors.toList());\n```\n\n---\n\n## Deep Dive: Performance Characteristics\n\n### Operation Complexity\n\n| Operation | TreeSet | HashSet |\n|-----------|---------|---------|\n| add(e) | O(log n) | O(1) |\n| remove(e) | O(log n) | O(1) |\n| contains(e) | O(log n) | O(1) |\n| first()/last() | O(log n) | N/A |\n| ceiling()/floor() | O(log n) | N/A |\n| higher()/lower() | O(log n) | N/A |\n| subSet() | O(log n) | N/A |\n| Iteration | O(n) sorted | O(n) unsorted |\n\n### When to Use TreeSet\n\n```java\n// ✅ Use TreeSet when you need:\n\n// 1. Sorted iteration\nTreeSet names = new TreeSet<>();\nnames.forEach(System.out::println); // Alphabetically sorted\n\n// 2. Range queries\nTreeSet dates = new TreeSet<>();\nNavigableSet lastWeek = dates.subSet(\n LocalDate.now().minusDays(7), true,\n LocalDate.now(), true\n);\n\n// 3. Closest match queries\nTreeSet prices = new TreeSet<>();\nInteger nearestPrice = prices.ceiling(100); // Find price >= 100\n\n// 4. Min/Max access\nInteger min = prices.first();\nInteger max = prices.last();\n\n// 5. Ordered unique elements\nTreeSet timeline = new TreeSet<>(\n Comparator.comparing(Event::getTimestamp)\n);\n```\n\n### When to Use HashSet\n\n```java\n// ✅ Use HashSet when you need:\n\n// 1. Fast exact lookup (O(1) vs O(log n))\nSet validCodes = new HashSet<>(loadCodes());\nif (validCodes.contains(userCode)) { ... }\n\n// 2. No ordering requirements\nSet uniqueVisitors = new HashSet<>();\n\n// 3. Simple contains/add/remove\nSet processedIds = new HashSet<>();\nif (processedIds.add(id)) { // Returns false if already present\n process(id);\n}\n\n// 4. Membership testing\nSet blocklist = new HashSet<>(loadBlocklist());\nif (!blocklist.contains(ip)) { ... }\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Missing Comparable/Comparator\n\n```java\n// ❌ WRONG: Class doesn't implement Comparable\npublic class Product {\n private String name;\n private double price;\n}\n\nTreeSet products = new TreeSet<>();\nproducts.add(new Product(\"A\", 10.0)); // 💥 ClassCastException\n\n// ✅ CORRECT: Provide Comparator\nTreeSet products = new TreeSet<>(\n Comparator.comparing(Product::getPrice)\n);\n\n// ✅ CORRECT: Implement Comparable\npublic class Product implements Comparable {\n @Override\n public int compareTo(Product other) {\n return Double.compare(this.price, other.price);\n }\n}\n```\n\n### Mistake 2: Inconsistent compareTo and equals\n\n```java\n// ❌ WRONG: compareTo inconsistent with equals\npublic class Person implements Comparable {\n private String name;\n private int age;\n\n @Override\n public int compareTo(Person other) {\n return Integer.compare(this.age, other.age); // By age only\n }\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (!(o instanceof Person)) return false;\n Person person = (Person) o;\n return age == person.age && name.equals(person.name); // By age AND name\n }\n}\n\n// Problem: Two people with same age but different names\nPerson alice = new Person(\"Alice\", 30);\nPerson bob = new Person(\"Bob\", 30);\n\nTreeSet set = new TreeSet<>();\nset.add(alice);\nset.add(bob); // Bob NOT added! compareTo returns 0 (considered equal)\nset.size(); // 1, not 2!\n\n// ✅ CORRECT: Make compareTo consistent\n@Override\npublic int compareTo(Person other) {\n int ageCompare = Integer.compare(this.age, other.age);\n if (ageCompare != 0) return ageCompare;\n return this.name.compareTo(other.name); // Tiebreaker\n}\n```\n\n### Mistake 3: Modifying Elements After Adding\n\n```java\n// ❌ WRONG: Modifying sort key after adding\nTreeSet set = new TreeSet<>();\nStringBuilder sb = new StringBuilder(\"apple\");\nset.add(sb);\n\nsb.append(\"sauce\"); // Modifies the element!\n// TreeSet position is now wrong - element in wrong place\n\nset.contains(new StringBuilder(\"apple\")); // false (might be)\nset.contains(new StringBuilder(\"applesauce\")); // false (might be)\n\n// The tree structure is corrupted!\n\n// ✅ CORRECT: Use immutable keys or don't modify\n// Option 1: Use immutable types (String, Integer, etc.)\nTreeSet safeSet = new TreeSet<>();\n\n// Option 2: Remove, modify, re-add\nset.remove(sb);\nsb.append(\"sauce\");\nset.add(sb);\n```\n\n### Mistake 4: subSet() Range Violations\n\n```java\nNavigableSet set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));\nNavigableSet sub = set.subSet(20, true, 40, true);\n\n// ❌ WRONG: Adding element outside range\nsub.add(50); // 💥 IllegalArgumentException: key out of range\nsub.add(15); // 💥 IllegalArgumentException: key out of range\n\n// ✅ CORRECT: Only add elements within the range\nsub.add(25); // OK - within [20, 40]\nsub.add(35); // OK - within [20, 40]\n```\n\n### Mistake 5: Null Handling\n\n```java\n// ❌ WRONG: Adding null to TreeSet\nTreeSet set = new TreeSet<>();\nset.add(null); // 💥 NullPointerException\n\n// TreeSet doesn't allow null because it needs to compare elements\n// HashSet allows one null element\n\n// ✅ CORRECT: Handle nulls before adding\nString value = getValue();\nif (value != null) {\n set.add(value);\n}\n\n// Or use Comparator.nullsFirst/nullsLast (but not recommended)\nTreeSet withNulls = new TreeSet<>(\n Comparator.nullsFirst(Comparator.naturalOrder())\n);\nwithNulls.add(null); // Works, but usually not a good idea\n```\n\n---\n\n## 🐛 Debug This\n\n### Challenge 1: The Missing Element\n\n```java\nTreeSet prices = new TreeSet<>();\nprices.add(10.0);\nprices.add(20.0);\nprices.add(Double.NaN);\nprices.add(30.0);\n\nSystem.out.println(prices.size());\nSystem.out.println(prices.contains(30.0));\n```\n\n**✅ Answer:**\n\nOutput is unpredictable! `Double.NaN` violates comparison contract because `NaN.compareTo(x)` is inconsistent.\n\n`NaN` is not equal to anything, not even itself, which breaks TreeSet's assumptions. The tree structure becomes corrupted.\n\n**Fix**: Never add `NaN` to TreeSet:\n```java\nif (!value.isNaN()) {\n prices.add(value);\n}\n```\n\n### Challenge 2: The Duplicate Elements\n\n```java\nclass Item implements Comparable {\n String name;\n int priority;\n\n @Override\n public int compareTo(Item other) {\n return Integer.compare(this.priority, other.priority);\n }\n}\n\nTreeSet items = new TreeSet<>();\nitems.add(new Item(\"A\", 1));\nitems.add(new Item(\"B\", 1));\nitems.add(new Item(\"C\", 2));\n\nSystem.out.println(items.size());\n```\n\n**✅ Answer:**\n\nOutput: `2`\n\nItems \"A\" and \"B\" have the same priority, so `compareTo` returns 0. TreeSet considers them equal and only keeps one.\n\n**Fix**: Add tiebreaker to compareTo:\n```java\n@Override\npublic int compareTo(Item other) {\n int priorityCompare = Integer.compare(this.priority, other.priority);\n if (priorityCompare != 0) return priorityCompare;\n return this.name.compareTo(other.name);\n}\n```\n\n### Challenge 3: The Infinite Loop\n\n```java\nTreeSet set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5));\nNavigableSet sub = set.subSet(2, true, 4, true);\n\nfor (Integer i : sub) {\n if (i == 3) {\n set.add(6); // What happens?\n }\n}\n```\n\n**✅ Answer:**\n\nThrows `ConcurrentModificationException`.\n\nEven though we add outside the subSet range, the subSet is a view backed by the original set. Modifying the original set during iteration of the view triggers the fail-fast mechanism.\n\n**Fix**: Collect modifications and apply after iteration:\n```java\nList toAdd = new ArrayList<>();\nfor (Integer i : sub) {\n if (i == 3) {\n toAdd.add(6);\n }\n}\nset.addAll(toAdd);\n```\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Find Closest Value\n\nImplement a method that finds the closest value to a target:\n\n```java\npublic static Integer findClosest(NavigableSet set, int target) {\n // Return element closest to target, or null if set is empty\n}\n\n// Example:\n// set = {10, 20, 30, 40, 50}\n// findClosest(set, 27) -> 30\n// findClosest(set, 25) -> 20 or 30 (either acceptable)\n```\n\n**✅ Solution:**\n\n```java\npublic static Integer findClosest(NavigableSet set, int target) {\n if (set.isEmpty()) return null;\n\n Integer floor = set.floor(target);\n Integer ceiling = set.ceiling(target);\n\n if (floor == null) return ceiling;\n if (ceiling == null) return floor;\n\n // Return whichever is closer\n return (target - floor <= ceiling - target) ? floor : ceiling;\n}\n```\n\n### Exercise 2: Range Count\n\nImplement efficient range counting:\n\n```java\npublic class RangeCounter {\n private NavigableSet set;\n\n public int countInRange(T from, T to) {\n // Return count of elements where from <= element <= to\n }\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class RangeCounter {\n private final NavigableSet set;\n\n public RangeCounter(NavigableSet set) {\n this.set = set;\n }\n\n public int countInRange(T from, T to) {\n return set.subSet(from, true, to, true).size();\n }\n\n // For large sets, if you need this frequently,\n // consider using a custom structure or caching\n}\n```\n\n### Exercise 3: Top K Elements\n\nImplement efficient top-K retrieval:\n\n```java\npublic static List topK(NavigableSet set, int k) {\n // Return top k elements (largest first)\n}\n\n// Example:\n// set = {10, 20, 30, 40, 50}\n// topK(set, 3) -> [50, 40, 30]\n```\n\n**✅ Solution:**\n\n```java\npublic static List topK(NavigableSet set, int k) {\n return set.descendingSet().stream()\n .limit(k)\n .collect(Collectors.toList());\n}\n\n// More efficient for very large sets:\npublic static List topKEfficient(NavigableSet set, int k) {\n List result = new ArrayList<>(Math.min(k, set.size()));\n Iterator descIt = set.descendingIterator();\n while (descIt.hasNext() && result.size() < k) {\n result.add(descIt.next());\n }\n return result;\n}\n```\n\n### Exercise 4: Scheduling System\n\nCreate a scheduling system using TreeSet:\n\n```java\npublic class Scheduler {\n // Add appointment (return false if conflicts)\n public boolean schedule(LocalDateTime start, LocalDateTime end);\n\n // Find next available slot of given duration after given time\n public LocalDateTime findNextSlot(LocalDateTime after, Duration duration);\n\n // Get appointments in time range\n public List getAppointments(LocalDateTime from, LocalDateTime to);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class Scheduler {\n private final NavigableSet appointments = new TreeSet<>(\n Comparator.comparing(Appointment::getStart)\n );\n\n public boolean schedule(LocalDateTime start, LocalDateTime end) {\n Appointment newAppt = new Appointment(start, end);\n\n // Check for conflicts\n Appointment floor = appointments.floor(newAppt);\n Appointment ceiling = appointments.ceiling(newAppt);\n\n if (floor != null && floor.getEnd().isAfter(start)) {\n return false; // Conflict with earlier appointment\n }\n if (ceiling != null && ceiling.getStart().isBefore(end)) {\n return false; // Conflict with later appointment\n }\n\n appointments.add(newAppt);\n return true;\n }\n\n public LocalDateTime findNextSlot(LocalDateTime after, Duration duration) {\n LocalDateTime slotStart = after;\n\n for (Appointment appt : appointments.tailSet(\n new Appointment(after, after), true)) {\n if (slotStart.plus(duration).isBefore(appt.getStart()) ||\n slotStart.plus(duration).equals(appt.getStart())) {\n return slotStart; // Found gap\n }\n slotStart = appt.getEnd(); // Move past this appointment\n }\n return slotStart; // After all appointments\n }\n\n public List getAppointments(LocalDateTime from, LocalDateTime to) {\n return new ArrayList<>(appointments.subSet(\n new Appointment(from, from), true,\n new Appointment(to, to), true\n ));\n }\n}\n\nrecord Appointment(LocalDateTime start, LocalDateTime end) {}\n```\n\n### Exercise 5: Leaderboard\n\nImplement a game leaderboard with efficient ranking:\n\n```java\npublic class Leaderboard {\n // Add or update player score\n public void updateScore(String player, int score);\n\n // Get player rank (1-based)\n public int getRank(String player);\n\n // Get top N players\n public List getTopN(int n);\n\n // Get players around a given player (n above, n below)\n public List getPlayersAround(String player, int n);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class Leaderboard {\n private record Entry(String player, int score) implements Comparable {\n @Override\n public int compareTo(Entry other) {\n int scoreCompare = Integer.compare(other.score, this.score); // Descending\n return scoreCompare != 0 ? scoreCompare : this.player.compareTo(other.player);\n }\n }\n\n private final NavigableSet entries = new TreeSet<>();\n private final Map playerEntries = new HashMap<>();\n\n public void updateScore(String player, int score) {\n Entry oldEntry = playerEntries.get(player);\n if (oldEntry != null) {\n entries.remove(oldEntry);\n }\n Entry newEntry = new Entry(player, score);\n entries.add(newEntry);\n playerEntries.put(player, newEntry);\n }\n\n public int getRank(String player) {\n Entry entry = playerEntries.get(player);\n if (entry == null) return -1;\n return entries.headSet(entry, false).size() + 1;\n }\n\n public List getTopN(int n) {\n return entries.stream()\n .limit(n)\n .map(Entry::player)\n .collect(Collectors.toList());\n }\n\n public List getPlayersAround(String player, int n) {\n Entry entry = playerEntries.get(player);\n if (entry == null) return Collections.emptyList();\n\n List result = new ArrayList<>();\n\n // Get n players above\n NavigableSet above = entries.headSet(entry, false);\n List aboveList = new ArrayList<>(above);\n Collections.reverse(aboveList);\n aboveList.stream().limit(n).forEach(e -> result.add(0, e.player()));\n\n // Add current player\n result.add(player);\n\n // Get n players below\n entries.tailSet(entry, false).stream()\n .limit(n)\n .forEach(e -> result.add(e.player()));\n\n return result;\n }\n}\n```\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question 1: TreeSet vs HashSet Performance\n\n**Q: When would TreeSet outperform HashSet?**\n\n**A:**\n\nTreeSet can outperform HashSet in these scenarios:\n\n1. **Range queries**: Finding elements between X and Y is O(log n + k) for TreeSet vs O(n) for HashSet.\n\n2. **Sorted iteration**: TreeSet iterates in order naturally. HashSet requires collecting and sorting: O(n log n).\n\n3. **Min/Max access**: TreeSet provides O(log n) first()/last(). HashSet requires O(n) scan.\n\n4. **Navigation queries**: ceiling(), floor(), higher(), lower() are O(log n) in TreeSet, impossible efficiently in HashSet.\n\n```java\n// Example: Find all prices between $100 and $200\nTreeSet prices = ...;\nSet result = prices.subSet(100, true, 200, true); // O(log n)\n\n// With HashSet, you'd need O(n) iteration\n```\n\n### Question 2: Red-Black Tree Properties\n\n**Q: Why does TreeSet use a Red-Black tree instead of a simple BST?**\n\n**A:**\n\nA simple BST can degenerate to O(n) operations if elements are inserted in sorted order (becomes a linked list). Red-Black trees guarantee O(log n) by maintaining these properties:\n\n1. Self-balancing through rotations\n2. Maximum height of 2 * log(n+1)\n3. Rebalancing is O(log n) worst case\n\n```text\nSimple BST with sorted insert (1,2,3,4,5):\n1\n \\\n 2\n \\\n 3\n \\\n 4 Height = n, operations = O(n)\n \\\n 5\n\nRed-Black tree with same insertions:\n 2(B)\n / \\\n 1(B) 4(R)\n / \\\n 3(B) 5(B) Height = O(log n), operations = O(log n)\n```\n\n### Question 3: Comparable Consistency\n\n**Q: Why should compareTo() be consistent with equals()?**\n\n**A:**\n\nTreeSet uses compareTo() for both ordering AND equality checking. If compareTo() returns 0 for two objects that aren't equal(), you get unexpected behavior:\n\n```java\n// Inconsistent: compareTo by priority, equals by id\nclass Task {\n int id, priority;\n\n int compareTo(Task o) { return Integer.compare(priority, o.priority); }\n boolean equals(Object o) { return id == ((Task)o).id; }\n}\n\nTreeSet set = new TreeSet<>();\nset.add(new Task(1, 5)); // id=1, priority=5\nset.add(new Task(2, 5)); // id=2, priority=5 - NOT ADDED!\n// compareTo returns 0, so TreeSet considers them \"equal\"\n```\n\nThe Java documentation explicitly warns: \"The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.\"\n\n### Question 4: subSet View Behavior\n\n**Q: What happens when you modify a TreeSet while iterating over its subSet view?**\n\n**A:**\n\nThe subSet is a live view backed by the original TreeSet. Modifications to either affect both:\n\n1. **Modifying original**: Changes visible in subSet (if in range). Triggers ConcurrentModificationException during iteration.\n\n2. **Modifying subSet**: Changes visible in original. Subject to range restrictions.\n\n```java\nTreeSet set = new TreeSet<>(List.of(1,2,3,4,5));\nNavigableSet sub = set.subSet(2, true, 4, true);\n\n// Adding outside range to sub throws exception\nsub.add(5); // IllegalArgumentException\n\n// Adding to original during sub iteration\nfor (Integer i : sub) {\n set.add(6); // ConcurrentModificationException\n}\n```\n\n### Question 5: Custom Comparator with Natural Ordering\n\n**Q: How would you create a TreeSet that sorts by one field primarily but uses natural ordering as a tiebreaker?**\n\n**A:**\n\nUse `Comparator.comparing().thenComparing()`:\n\n```java\nclass Person implements Comparable {\n String name;\n int age;\n\n @Override\n public int compareTo(Person other) {\n return this.name.compareTo(other.name);\n }\n}\n\n// Sort by age primarily, then by natural ordering (name)\nTreeSet byAgeThenName = new TreeSet<>(\n Comparator.comparingInt(Person::getAge)\n .thenComparing(Comparator.naturalOrder())\n);\n\n// Or more explicitly:\nTreeSet explicit = new TreeSet<>(\n Comparator.comparingInt(Person::getAge)\n .thenComparing(Person::getName)\n);\n```\n\n### Question 6: NavigableSet ceiling vs higher\n\n**Q: What's the difference between ceiling() and higher()? When would you use each?**\n\n**A:**\n\n- `ceiling(e)`: Returns smallest element **>=** e (inclusive)\n- `higher(e)`: Returns smallest element **>** e (exclusive)\n\n```java\nNavigableSet set = new TreeSet<>(List.of(10, 20, 30));\n\n// For element NOT in set - same result\nset.ceiling(15); // 20\nset.higher(15); // 20\n\n// For element IN set - different result\nset.ceiling(20); // 20 (includes 20 itself)\nset.higher(20); // 30 (excludes 20)\n```\n\nUse cases:\n- `ceiling()`: \"What's the cheapest option at or above $X?\"\n- `higher()`: \"What's the next item after this one?\"\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### TreeSet Fundamentals\n- Backed by Red-Black tree: O(log n) for all operations\n- Elements must be Comparable or use Comparator\n- No null elements allowed (can't compare null)\n- compareTo() determines both ordering AND equality\n\n### NavigableSet Operations\n- `ceiling(e)` / `floor(e)`: Closest >= / <=\n- `higher(e)` / `lower(e)`: Strictly > / <\n- `pollFirst()` / `pollLast()`: Remove and return extremes\n- `descendingSet()`: Reversed view\n\n### Subset Views\n- `subSet()`, `headSet()`, `tailSet()`: Live views\n- Changes in view affect original (and vice versa)\n- Range restrictions enforced on views\n- ConcurrentModificationException during iteration with modifications\n\n### When to Use TreeSet\n- Need sorted iteration\n- Range queries (find between X and Y)\n- Closest match queries (ceiling/floor)\n- Min/Max access needed\n- O(log n) is acceptable for add/remove/contains\n\n---\n\n## 🏁 Conclusion\n\nTreeSet is more than just a sorted set - it's a powerful tool for range-based queries and navigation operations. The NavigableSet interface provides methods that can replace complex loops with elegant, efficient single calls.\n\nKey takeaways:\n1. **TreeSet uses Red-Black tree** for guaranteed O(log n) operations\n2. **Range queries are TreeSet's superpower** - O(log n) vs O(n) for HashSet\n3. **Subset views are live** - changes propagate bidirectionally\n4. **compareTo() must be consistent** with equals() to avoid surprises\n5. **NavigableSet navigation methods** (ceiling, floor, higher, lower) enable elegant solutions\n\nIn the next article, we'll explore specialized sets like EnumSet and CopyOnWriteArraySet, and when they outperform general-purpose implementations.\n\n---\n\n## 📅 Review Schedule\n\nTo solidify your understanding, review this material:\n- **Tomorrow**: Re-read NavigableSet operations (ceiling, floor, etc.)\n- **In 3 days**: Implement Exercise 4 (Scheduler) again\n- **In 1 week**: Explain TreeSet vs HashSet tradeoffs to a colleague\n- **In 2 weeks**: Review the production story and common mistakes\n\n---\n\n**Next in Series**: [Part 11: EnumSet & Specialized Sets](/articles/java-collections-part-11-enumset-specialized)\n\n**Series Navigation**: [Part 0: How to Use This Series](/articles/java-collections-part-0-how-to-use-this-series) | [Full Index](/articles/java-collections-compendium)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.952637Z","createdAt","2026-06-10T07:19:25.953422Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",19,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder","author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":62,"_72":59,"_35":96,"_75":97,"_98":-5},"tags",[78,79,80,81,82],"series",{"_31":62,"_72":73,"_35":74,"_75":76,"_77":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":95,"_72":59,"_35":96},{"_31":92,"_72":93,"_35":94},{"_31":89,"_72":90,"_35":91},{"_31":86,"_72":87,"_35":88},{"_31":83,"_72":84,"_35":85},260,"Treeset","treeset",342,"Sortedset","sortedset",343,"Red-black Tree","red-black-tree",341,"Navigableset","navigableset",14,"java","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]