[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":94,"_71":95,"_35":96},"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":52,"_62":52,"_63":64,"_65":66,"_67":68,"_69":70},"id",75,"title","TreeSet / Binary Search Tree","slug","dsa-cheatsheet-part-4-treeset","excerpt","Visual guide to TreeSet/BST: self-balancing trees, sorted operations. See insertions and rotations in real-time.","# TreeSet / Binary Search Tree\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Sorted set backed by Red-Black Tree |\n| **Add/Remove/Contains** | O(log n) |\n| **First/Last** | O(log n) |\n| **Memory** | O(n) with node overhead |\n| **Ordering** | Natural order or custom Comparator |\n| **Best For** | Sorted unique elements, range queries |\n\n**One-liner**: *Self-balancing BST providing O(log n) sorted operations with no duplicates.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how TreeSet maintains balance during insertions and deletions:\n\n```visualizer-treeset\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Insert elements - see tree balancing (rotations)\n2. Delete a node - watch restructuring\n3. Find an element - observe O(log n) path\n4. Try inserting duplicates - they're ignored!\n\n---\n\n## 🔧 Key Operations\n\n### Creating\n\n```java\n// Natural ordering\nTreeSet set = new TreeSet<>();\n\n// Custom comparator\nTreeSet set = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);\nTreeSet set = new TreeSet<>(Comparator.comparing(Person::getAge));\n\n// From collection\nTreeSet set = new TreeSet<>(existingCollection);\n```\n\n### Adding/Removing\n\n```java\nset.add(5); // O(log n) - returns true if added\nset.addAll(collection); // O(n log n)\nset.remove(5); // O(log n)\nset.clear(); // O(n)\n\n// Conditional\nset.removeIf(x -> x < 0); // O(n)\n```\n\n### Querying\n\n```java\nboolean has = set.contains(5); // O(log n)\nint size = set.size(); // O(1)\nboolean empty = set.isEmpty(); // O(1)\n\n// First/Last\nInteger first = set.first(); // O(log n) - throws if empty\nInteger last = set.last(); // O(log n) - throws if empty\n```\n\n### Navigation (Sorted Operations)\n\n```java\n// Floor/Ceiling (≤ and ≥)\nInteger floor = set.floor(5); // Greatest element ≤ 5\nInteger ceiling = set.ceiling(5); // Smallest element ≥ 5\n\n// Lower/Higher (< and >)\nInteger lower = set.lower(5); // Greatest element < 5\nInteger higher = set.higher(5); // Smallest element > 5\n\n// Subsets\nSortedSet head = set.headSet(5); // Elements < 5\nSortedSet tail = set.tailSet(5); // Elements ≥ 5\nSortedSet sub = set.subSet(2, 8); // Elements [2, 8)\n\n// With inclusive bounds\nNavigableSet sub = set.subSet(2, true, 8, true); // [2, 8]\n```\n\n### Iteration\n\n```java\n// Ascending (default)\nfor (Integer num : set) { }\n\n// Descending\nfor (Integer num : set.descendingSet()) { }\n\n// Descending iterator\nIterator desc = set.descendingIterator();\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Operation | Time | Notes |\n|-----------|------|-------|\n| `add(e)` | O(log n) | Tree traversal + possible rebalancing |\n| `remove(e)` | O(log n) | Find + restructure |\n| `contains(e)` | O(log n) | Binary search in tree |\n| `first/last` | O(log n) | Traverse to leftmost/rightmost |\n| `floor/ceiling` | O(log n) | Modified binary search |\n| `subSet/headSet/tailSet` | O(1) | Returns view, not copy |\n| `iteration` | O(n) | In-order traversal |\n\n### Red-Black Tree Properties\n\n```\n1. Every node is RED or BLACK\n2. Root is BLACK\n3. Leaves (NIL) are BLACK\n4. RED node → both children BLACK\n5. All paths from node to leaves have same BLACK count\n\nThese rules ensure: height ≤ 2 × log(n+1)\n```\n\n---\n\n## ✅ When to Use TreeSet\n\n### Good Use Cases\n\n- **Sorted unique elements** - always in order\n- **Range queries** - subSet, headSet, tailSet\n- **Finding neighbors** - floor, ceiling, lower, higher\n- **Min/Max operations** - first(), last()\n\n### Avoid When\n\n- **Just need uniqueness** - use `HashSet` (O(1) vs O(log n))\n- **Frequent contains checks** - HashSet is faster\n- **Need index access** - TreeSet has no get(i)\n- **Null elements needed** - TreeSet doesn't allow null\n\n---\n\n## 🔄 TreeSet vs HashSet vs LinkedHashSet\n\n| Feature | HashSet | LinkedHashSet | TreeSet |\n|---------|---------|---------------|---------|\n| Order | None | Insertion | Sorted |\n| add/contains | O(1) | O(1) | O(log n) |\n| Memory | Lowest | Medium | Highest |\n| Null allowed | Yes | Yes | No |\n| Range queries | No | No | Yes |\n\n```java\n// Choose based on needs:\nSet fast = new HashSet<>(); // Just uniqueness\nSet ordered = new LinkedHashSet<>(); // Insertion order\nSet sorted = new TreeSet<>(); // Sorted order\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Inconsistent Comparator with equals\n\n```java\n// ❌ Comparator only checks age, but equals checks name too\nTreeSet set = new TreeSet<>(Comparator.comparing(Person::getAge));\nset.add(new Person(\"Alice\", 25));\nset.add(new Person(\"Bob\", 25)); // Not added! Same age = \"equal\" to TreeSet\n\n// ✅ Comparator should be consistent with equals\nTreeSet set = new TreeSet<>(\n Comparator.comparing(Person::getAge)\n .thenComparing(Person::getName)\n);\n```\n\n### 2. Mutating Elements After Insert\n\n```java\n// ❌ Modifying sort key after insertion\nPerson alice = new Person(\"Alice\", 25);\nset.add(alice);\nalice.setAge(30); // Tree structure now invalid!\nset.contains(alice); // May return false!\n\n// ✅ Remove, modify, re-add\nset.remove(alice);\nalice.setAge(30);\nset.add(alice);\n```\n\n### 3. Using Non-Comparable Types\n\n```java\n// ❌ No natural ordering\nTreeSet set = new TreeSet<>();\nset.add(new Person(\"Alice\")); // ClassCastException!\n\n// ✅ Provide comparator or implement Comparable\nTreeSet set = new TreeSet<>(Comparator.comparing(Person::getName));\n```\n\n### 4. Expecting O(1) Like HashSet\n\n```java\n// ❌ Using TreeSet when order doesn't matter\nTreeSet seen = new TreeSet<>(); // O(log n) operations\nfor (String item : items) {\n if (!seen.contains(item)) seen.add(item);\n}\n\n// ✅ Use HashSet for pure uniqueness\nHashSet seen = new HashSet<>(); // O(1) operations\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: What's the difference between TreeSet and HashSet?**\n\n> TreeSet maintains sorted order using a Red-Black tree (O(log n) operations), while HashSet uses hashing (O(1) average). Choose TreeSet when you need sorted iteration or range queries; HashSet otherwise.\n\n**Q: Why can't TreeSet contain null?**\n\n> TreeSet relies on comparisons to position elements. Comparing with null would throw NullPointerException. HashSet allows one null because it uses equals() for comparison.\n\n**Q: How does TreeSet handle duplicates?**\n\n> Elements are compared using compareTo() or the Comparator. If comparison returns 0, elements are considered equal and the duplicate is not added. This is why Comparator should be consistent with equals().\n\n**Q: What's floor() vs lower()?**\n\n> floor(e) returns greatest element ≤ e (inclusive), lower(e) returns greatest element < e (exclusive). Similarly, ceiling is ≥ and higher is >.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 3: HashMap](dsa-cheatsheet-part-3-hashmap)\n\n**Next**: [Part 5: PriorityQueue / Heap](dsa-cheatsheet-part-5-priorityqueue)\n\n---\n\n**Visualizer**: `TreeSet` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.631164Z","createdAt","2026-06-10T07:19:25.631359Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",4,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId","seriesOrder","author",{"_31":55,"_101":57,"_102":103,"_104":105,"_106":-5,"_107":-5,"_108":-5,"_109":-5,"_110":-5},"category",{"_31":97,"_71":59,"_35":98,"_74":99,"_100":-5},"tags",[77,78,79,80,81],"series",{"_31":52,"_71":72,"_35":73,"_74":75,"_76":23},"name","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","isActive",{"_31":94,"_71":95,"_35":96},{"_31":91,"_71":92,"_35":93},{"_31":88,"_71":89,"_35":90},{"_31":85,"_71":86,"_35":87},{"_31":82,"_71":83,"_35":84},260,"Treeset","treeset",262,"Sorted","sorted",263,"O(log N)","o(log-n)",252,"Data Structure","data-structure",261,"Bst","bst",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]