TreeSet and TreeMap — Sorted Collections and NavigableSet/NavigableMap

Direct Answer

TreeSet and TreeMap are Java's sorted collections backed by Red-Black trees, providing O(log n) operations and iteration in natural (or comparator-defined) order. TreeSet implements NavigableSet; TreeMap implements NavigableMap — both support powerful range queries that HashSet/HashMap can't do: first()/last(), floor(x)/ceiling(x) (closest ≤ or ≥ x), lower(x)/higher(x) (strict variants), headSet/headMap/tailSet/tailMap/subSet/subMap (range views), descendingIterator/descendingMap (reverse-order iteration). Use TreeSet/TreeMap when: (1) you need sorted iteration (e.g., leaderboard, scheduled events); (2) you need range queries (e.g., 'all events between 9am and 5pm'); (3) you need floor/ceiling lookups (e.g., 'closest available time slot ≥ 10:00'); (4) you need predictable O(log n) worst case (HashMap is O(1) avg but O(log n) worst). Trade-offs: slower than HashMap (O(log n) vs O(1) avg); requires Comparable elements or a Comparator; null keys not allowed in TreeMap (TreeSet allows one only if comparator handles it). Common bugs: inconsistent compareTo/equals (TreeSet uses compareTo for membership, not equals); using TreeMap when HashMap would do (premature 'sorted' optimization). For interviews: lead with 'Red-Black tree, O(log n), supports range queries via NavigableMap', then mention specific methods like floorKey, ceilingKey, subMap.

Deep Dive & Architecture

compute, merge, computeIfAbsent, and computeIfPresent are Map methods (Java 8+) that atomically combine get + check + put into a single operation, replacing the verbose get-check-put anti-pattern. computeIfAbsent(key, mappingFunction) — if key absent, compute value and put; most-used for lazy initialization of multi-valued maps: map.computeIfAbsent(key, k -> new ArrayList<>()).add(value). computeIfPresent(key, remappingFunction) — if key present, recompute value (or remove if null returned). compute(key, remappingFunction) — recompute regardless of presence (function gets old value or null). merge(key, value, remappingFunction) — if absent, put value; if present, apply function to combine: map.merge(word, 1, Integer::sum) is the idiomatic word-counter. Why they matter: (1) atomic in ConcurrentHashMap — no lost updates from concurrent get-check-put races; (2) less code than if (map.containsKey(k)) map.put(k, ...) else map.put(k, ...); (3) cleaner intent — the operation says what it does. Pitfalls: (1) not atomic in non-concurrent maps (HashMap) — only the API is single-call, not thread-safe; (2) returning null from a remapping function removes the key — surprising; (3) don't recursively modify the map inside the function — undefined behavior; (4) merge doesn't handle null values the same way as compute — read the Javadoc. For interviews: lead with 'replaces get-check-put, atomic in ConcurrentHashMap, idiomatic for multimap lazy-init and counters'.

TreeSet and TreeMap are Java's sorted collections backed by Red-Black trees, providing O(log n) operations and iteration in natural (or comparator-defined) order. TreeSet implements NavigableSet; TreeMap implements NavigableMap — both support powerful range queries that HashSet/HashMap can't do: first()/last(), floor(x)/ceiling(x) (closest ≤ or ≥ x), lower(x)/higher(x) (strict variants), headSet/headMap/tailSet/tailMap/subSet/subMap (range views), descendingIterator/descendingMap (reverse-order iteration). Use TreeSet/TreeMap when: (1) you need sorted iteration (e.g., leaderboard, scheduled events); (2) you need range queries (e.g., 'all events between 9am and 5pm'); (3) you need floor/ceiling lookups (e.g., 'closest available time slot ≥ 10:00'); (4) you need predictable O(log n) worst case (HashMap is O(1) avg but O(log n) worst). Trade-offs: slower than HashMap (O(log n) vs O(1) avg); requires Comparable elements or a Comparator; null keys not allowed in TreeMap (TreeSet allows one only if comparator handles it). Common bugs: inconsistent compareTo/equals (TreeSet uses compareTo for membership, not equals); using TreeMap when HashMap would do (premature 'sorted' optimization). For interviews: lead with 'Red-Black tree, O(log n), supports range queries via NavigableMap', then mention specific methods like floorKey, ceilingKey, subMap.

A common mistake is confusing the interface with the implementation (e.g., saying List when you mean ArrayList), or not knowing that Map does not extend Collection.

Common Mistakes & Pitfalls

Using TreeSet/TreeMap without implementing Comparable or providing a Comparator, leading to ClassCastException at runtime