🟢 Junior Level

TreeMap — a sorted Map where keys are always in order.

Use TreeMap when:

• You need sorting by keys
• You need range queries
• You need the “nearest” key

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(50, "B");
map.put(30, "C");

// Sorted: {10=A, 30=C, 50=B}

// Nearest key
map.floorKey(25);   // → 10 (nearest ≤ 25)
map.ceilingKey(25); // → 30 (nearest ≥ 25)

---

🟡 Middle Level

When TreeMap is needed

1. Range queries:

TreeMap<Integer, String> taxBrackets = new TreeMap<>();
taxBrackets.put(0, "0%");
taxBrackets.put(10000, "10%");
taxBrackets.put(50000, "20%");

// Tax rate for income 35,000
String rate = taxBrackets.floorEntry(35000).getValue();
// → "10%"

// HashMap cannot do this!

2. Sorted reports:

TreeMap<LocalDate, Report> reports = new TreeMap<>();
// Always in chronological order
// subMap for date ranges

3. Prefix search:

TreeMap<String, Data> index = new TreeMap<>();
// All keys with prefix "user:"
SortedMap<String, Data> users = index.subMap("user:", "user{");

When TreeMap is NOT needed

// ❌ Just need a dictionary
Map<String, Integer> map = new TreeMap<>();  // O(log n) — tree, needs to maintain order
// ✅ HashMap
Map<String, Integer> map = new HashMap<>();  // O(1) — hash table, fast insert/search

// ❌ Need insertion order
Map<String, Integer> map = new TreeMap<>();  // It sorts!
// ✅ LinkedHashMap
Map<String, Integer> map = new LinkedHashMap<>();  // Insertion order

---

🔴 Senior Level

Performance

TreeMap: O(log n) per operation
HashMap: O(1)

→ 1 million elements:
  HashMap: ~0.001 ms
  TreeMap: ~0.05 ms (50x slower!)

Approximate for 1 million Integer keys on a modern CPU. Actual numbers depend on JVM and key type. The main point — the order of magnitude difference: O(1) vs O(log n).

→ Don't use TreeMap as the main store
  if sorting is rarely needed!

Alternative: sort on the fly

// ❌ TreeMap for rare sorted iteration
TreeMap<K, V> sortedMap = new TreeMap<>();
// O(log n) on every insert

// ✅ HashMap + sort on iteration
HashMap<K, V> map = new HashMap<>();
List<K> sortedKeys = new ArrayList<>(map.keySet());
Collections.sort(sortedKeys);
// O(n log n) once during iteration
// O(1) on insert!

View: subMap, headMap, tailMap

NavigableMap<Integer, String> view = map.subMap(10, true, 50, true);
// → "Live" view, not a copy!
// → O(1) creation

view.put(30, "X");  // Adds to the ORIGINAL map
map.remove(30);     // Removes from view too!

view.put(100, "Y"); // → IllegalArgumentException!
// → 100 is outside the range [10, 50]

ConcurrentSkipListMap

// TreeMap is NOT thread-safe!
// For concurrent sorted map:
ConcurrentSkipListMap<K, V> map = new ConcurrentSkipListMap<>();
// → Skip List instead of tree
// → O(log n), lock-free

// Skip List = probabilistic structure with "express lanes" for faster search.
// Easier to implement and lock-free, but uses more memory than a tree.

Null keys

// TreeMap does not accept null!
map.put(null, "value");  // → NullPointerException!

// Workaround (not recommended):
TreeMap<String, String> map = new TreeMap<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
map.put(null, "value");  // OK, null goes first

Production Experience

Real scenario: Time-series data

// Sensors: timestamp → measurement
TreeMap<Long, SensorData> data = new TreeMap<>();

// Data for the last hour
Map<Long, SensorData> lastHour = data.tailMap(
    System.currentTimeMillis() - 3600000
);

// Nearest measurement to a time
Map.Entry<Long, SensorData> closest = data.floorEntry(targetTime);

Best Practices

1. TreeMap only for sorting/ranges
2. HashMap — by default
3. Sort “on the fly” if rarely needed
4. View = live, not a copy
5. ConcurrentSkipListMap for multithreading
6. null is prohibited without custom Comparator
7. Memory 3-4x more than HashMap

Summary for Senior

• TreeMap = sorting + navigation + ranges
• O(log n) vs O(1) for HashMap
• floorKey/ceilingKey = nearest key
• subMap = live range view
• Don’t use if sorting is rarely needed
• ConcurrentSkipListMap for concurrency
• null is prohibited (without Comparator)
• Memory > HashMap

---

🎯 Interview Cheat Sheet

Must know:

• TreeMap = O(log n), key sorting + navigation (floorKey, ceilingKey, subMap) — NOT for regular dictionaries
• HashMap = O(1) — default, TreeMap is ~50x slower at 1 million elements
• Range queries: subMap for time series, tax brackets, prefix search
• View (subMap, headMap, tailMap) = live view, not a copy — O(1) creation
• TreeMap is NOT thread-safe — for concurrency use ConcurrentSkipListMap (skip list, lock-free, O(log n))
• Null keys are prohibited (without custom Comparator nullsFirst/nullsLast)
• Memory: 3-4x more than HashMap due to tree nodes (left, right, parent, color)
• Alternative for rare sorting: HashMap + Collections.sort(keySet) — O(1) insert, O(n log n) sort on demand

Frequent follow-up questions:

• When is TreeMap the only choice? — When range queries (subMap) or “nearest” key (floorKey/ceilingKey) are needed. HashMap cannot do this.
• What is a live view and why does it matter? — subMap returns not a copy but a view. Adding/removing through the view affects the original map. You cannot add an element outside the range.
• How does ConcurrentSkipListMap differ from TreeMap? — Thread-safe, uses skip list instead of tree, lock-free operations, but uses more memory.
• Why not use TreeMap as the main store? — O(log n) on every operation. If sorting is rarely needed — HashMap + sort on iteration is cheaper.

Red flags (DO NOT say):

• ❌ “TreeMap is faster than HashMap” — 50x slower! Only use when sorting is needed
• ❌ “TreeMap is thread-safe” — no, use ConcurrentSkipListMap for multithreading
• ❌ “subMap copies data” — it’s a live view, changes reflect in the original map
• ❌ “TreeMap is for insertion order” — LinkedHashMap is for that, TreeMap sorts by keys

Related topics:

• [[15. What is the difference between HashMap, LinkedHashMap and TreeMap]]
• [[13. What is TreeSet and how does it work]]
• [[14. What is Map and what implementations exist]]
• [[18. What is ConcurrentHashMap]]