Java TreeMap

Java TreeMap

java.util.TreeMap<K, V> is the sorted map — every key is automatically placed in its correct sorted position, and firstKey(), lastKey(), floorKey(), ceilingKey(), headMap(), tailMap(), and subMap() let you query ranges without any manual scanning. The price over HashMap is O(log n) per operation — always, not just worst case — because every operation traverses a Red-Black tree. When your data needs to be both keyed and sorted, TreeMap handles both requirements in one structure.

What Is Java TreeMap?

TreeMap<K, V> is a concrete class in java.util that implements NavigableMap<K, V>. It stores entries in a self-balancing Red-Black tree keyed on the natural ordering of keys (via Comparable) or a supplied Comparator. Every traversal visits nodes in ascending key order.

The diagram below shows where TreeMap fits in the Map hierarchy.

java.util.Map<K, V>                         ← key-value contract
    ├── HashMap<K, V>                        ← O(1) avg, no order
    │       └── LinkedHashMap<K, V>          ← insertion/access order
    └── java.util.SortedMap<K, V>            ← adds sorted key view
            └── java.util.NavigableMap<K, V> ← adds floor, ceiling, lower, higher
                    └── java.util.TreeMap<K,V> ← THIS CLASS: Red-Black tree

KEY FACTS:
  Package    : java.util
  Since      : Java 1.2
  Implements : NavigableMap<K,V>, Cloneable, Serializable
  Backed by  : Red-Black tree (self-balancing BST)
  Key order  : natural (Comparable) or supplied Comparator — always ascending
  Null keys  : NOT allowed — compareTo(null) throws NullPointerException
  Null values: allowed (unlimited)
  Thread-safe: NO — use Collections.synchronizedSortedMap() or ConcurrentSkipListMap
  Operations : O(log n) guaranteed — tree height is bounded by 2 × log₂(n+1)

Basic Overview — TreeMap Method Groups

TreeMap inherits put(), get(), remove() from Map, then adds two layers of navigation through SortedMap and NavigableMap.

TREEMAP COMPLETE METHOD REFERENCE:

  MAP OPERATIONS (O(log n)):
    put(key, value)       ← insert or update
    get(key)              ← lookup
    remove(key)           ← delete
    containsKey(key)      ← O(log n) — traverses tree
    containsValue(value)  ← O(n) — full scan (no tree ordering on values)

  SORTED MAP ADDITIONS — SortedMap<K,V>:
    firstKey()            ← smallest key (leftmost node)
    lastKey()             ← largest key (rightmost node)
    headMap(toKey)        ← live view of keys strictly less than toKey
    tailMap(fromKey)      ← live view of keys >= fromKey
    subMap(from, to)      ← live view of keys in [from, to)
    comparator()          ← returns Comparator or null for natural ordering

  NAVIGABLE MAP ADDITIONS — NavigableMap<K,V>:
    floorKey(key)         ← largest key <= key (null if none)
    ceilingKey(key)       ← smallest key >= key (null if none)
    lowerKey(key)         ← largest key strictly < key (null if none)
    higherKey(key)        ← smallest key strictly > key (null if none)
    floorEntry(key)       ← Entry version of floorKey
    ceilingEntry(key)     ← Entry version of ceilingKey
    firstEntry()          ← Entry with smallest key
    lastEntry()           ← Entry with largest key
    pollFirstEntry()      ← remove and return smallest entry
    pollLastEntry()       ← remove and return largest entry
    descendingMap()       ← reverse-order view of entire map
    descendingKeySet()    ← reverse-order NavigableSet of keys
    headMap(to, inclusive)← overloaded with inclusive boundary
    tailMap(from, inclusive)← overloaded with inclusive boundary
    subMap(from,fi,to,ti) ← overloaded with inclusive boundaries

ALL range views are LIVE — modifications propagate back to the backing TreeMap.

When to Use TreeMap

USE TreeMap WHEN:
  1. Keys must be iterated in sorted order
     — leaderboards, alphabetical catalogues, sorted event logs

  2. Range queries are needed
     — all keys between 100 and 500: subMap(100, true, 500, true)
     — all keys alphabetically before "P": headMap("P")
     — all keys from a given timestamp: tailMap(timestamp)

  3. Nearest-key navigation is needed
     — "what is the largest configured timeout <= my request timeout?"
       → floorKey(requestTimeout)
     — "what is the next scheduled event >= now?"
       → ceilingKey(System.currentTimeMillis())

  4. A sorted unique-key view of a dataset must be maintained live
     — price levels, time slots, route segments

CHOOSE HashMap INSTEAD WHEN:
  - Key order is irrelevant
  - O(1) is required: HashMap put/get/remove are faster than TreeMap
  - The map holds millions of entries and the O(log n) cost accumulates

CHOOSE LinkedHashMap INSTEAD WHEN:
  - Insertion order (not key-sorted order) matters
  - O(1) operations are needed alongside ordered iteration

CHOOSE ConcurrentSkipListMap INSTEAD WHEN:
  - Sorted map with concurrent multi-thread access is needed
  - ConcurrentSkipListMap provides O(log n) operations with full thread safety

NEVER USE TreeMap WHEN:
  - Keys do not implement Comparable AND no Comparator is provided
    → ClassCastException on the second put() call
  - Null keys are needed → NullPointerException on any put(null, value)

How TreeMap Works Internally

Red-Black Tree Structure

Every entry in TreeMap is stored as an Entry<K, V> node in a Red-Black tree — a self-balancing binary search tree with five invariants that bound the tree height at 2 × log₂(n+1).

TREEMAP ENTRY NODE:
  K     key
  V     value
  Entry left, right  ← BST children
  Entry parent       ← parent reference (for upward traversal)
  boolean color      ← RED or BLACK (Red-Black invariant)

RED-BLACK TREE INVARIANTS:
  1. Every node is RED or BLACK
  2. The root is always BLACK
  3. No two consecutive RED nodes (RED node's parent must be BLACK)
  4. Every path from a node to a null leaf has the same number of BLACK nodes
  5. Null leaves are considered BLACK

THESE INVARIANTS GUARANTEE:
  Height <= 2 × log₂(n + 1)
  For n = 1,000,000 entries: height <= ~40 comparisons per operation

TREEMAP AFTER: put("D",4), put("B",2), put("F",6), put("A",1), put("C",3):

  In-order traversal always produces keys in ascending order.

  Tree structure (simplified, colours omitted):
            D
          /   \
        B       F
       / \
      A   C

  put() steps for "E":
    1. Compare "E" with root "D" → "E" > "D" → go right
    2. Compare "E" with "F"     → "E" < "F" → go left
    3. Null slot found → insert new node here
    4. Rebalance: check Red-Black invariants, rotate if needed
    O(log n) comparisons + O(log n) rotations (bounded)

  get("C"):
    1. Compare "C" with "D" → "C" < "D" → go left
    2. Compare "C" with "B" → "C" > "B" → go right
    3. Compare "C" with "C" → match → return value
    O(log n) comparisons — no collision chains, no hash computation

compareTo() Drives Everything

TreeMap uses compareTo() (natural ordering) or the provided Comparator for all operations. It never calls equals() or hashCode(). Two keys where compare(a, b) == 0 are treated as identical — the second put() replaces the value rather than adding a new entry.

DUPLICATE DETECTION in TreeMap:

  compare(key1, key2) == 0  →  same key — value replaced, no new node
  compare(key1, key2) != 0  →  different keys — separate nodes

  This is independent of equals(). If compare() returns 0 but equals()
  returns false, TreeMap treats them as the same key (value replaced).

  CONSISTENCY-WITH-EQUALS CONTRACT (recommended, not enforced):
    (a.compareTo(b) == 0) should equal (a.equals(b))

  BigDecimal violates this: 2.0.compareTo(2.00) == 0 but equals is false.
  In a TreeMap<BigDecimal, ...>, put(new BigDecimal("2.0"), X) followed by
  put(new BigDecimal("2.00"), Y) results in one entry with value Y.

Core Operations with Examples

put(), get(), Basic SortedMap Methods

Output:
=== TreeMap iterates in sorted key order ===
  Ahmedabad    rank 6
  Bengaluru    rank 3
  Chennai      rank 5
  Delhi        rank 2
  Hyderabad    rank 4
  Mumbai       rank 1

=== SortedMap boundary access ===
firstKey()  : Ahmedabad
lastKey()   : Mumbai
firstEntry(): Ahmedabad=6
lastEntry() : Mumbai=1

=== pollFirstEntry / pollLastEntry ===
pollFirstEntry(): Ahmedabad=6
pollLastEntry() : Mumbai=1
After polls     : [Bengaluru, Chennai, Delhi, Hyderabad]

NavigableMap — Floor, Ceiling, Lower, Higher

Output:
Price tiers: {199=Basic, 499=Standard, 999=Premium, 1999=Pro, 4999=Enterprise}

Budget: Rs.750
floorKey(750)   : 499  (best tier within budget)
ceilingKey(750) : 999  (cheapest tier at or above budget)
lowerKey(750)   : 499  (strictly below budget)
higherKey(750)  : 999  (just above budget)

=== Edge cases ===
floorKey(100)    : null
ceilingKey(6000) : null
floorKey(999)    : 999
lowerKey(199)    : null
floorEntry(750)  : 499=Standard

Range Views — headMap, tailMap, subMap

Output:
All events: [UserLogin, CartUpdated, PaymentInitiated, PaymentConfirmed, OrderPlaced, OrderDispatched, UserLogout]

=== headMap(4000) — before payment confirmation ===
  1000: UserLogin
  2000: CartUpdated
  3000: PaymentInitiated

=== headMap(4000, inclusive=true) ===
  1000: UserLogin
  2000: CartUpdated
  3000: PaymentInitiated
  4000: PaymentConfirmed

=== tailMap(5000) — from order placed onwards ===
  5000: OrderPlaced
  6000: OrderDispatched
  7000: UserLogout

=== subMap(3000, 6000) — payment + order events ===
  3000: PaymentInitiated
  4000: PaymentConfirmed
  5000: OrderPlaced

=== subMap(3000, true, 6000, true) — inclusive both ===
  3000: PaymentInitiated
  4000: PaymentConfirmed
  5000: OrderPlaced
  6000: OrderDispatched

=== Live view — remove through headMap ===
Backing TreeMap after clear: [PaymentConfirmed, OrderPlaced, OrderDispatched, UserLogout]

=== descendingMap() — most recent first ===
  7000: UserLogout
  6000: OrderDispatched
  5000: OrderPlaced
  4000: PaymentConfirmed

Custom Ordering with Comparator

Output:
=== Sorted by price ascending (tiebreak: id) ===
  Rs.199.00  Mouse Pad          (stock: 100)
  Rs.299.00  Keyboard Cover     (stock: 80)
  Rs.399.00  HDMI Cable         (stock: 65)
  Rs.799.00  USB Hub            (stock: 42)
  Rs.799.00  Laptop Stand       (stock: 30)

floor (<=Rs.400)   : HDMI Cable
ceiling (>=Rs.400) : USB Hub

=== Descending (most expensive first) ===
  Rs.799.00  Laptop Stand
  Rs.799.00  USB Hub
  Rs.399.00  HDMI Cable
  Rs.299.00  Keyboard Cover
  Rs.199.00  Mouse Pad

Basic Example

A TreeMap keeps its keys sorted automatically, no matter what order you insert them in. This example stores student names keyed by roll number and shows that iteration always comes out in ascending key order.

Output

TreeMap (sorted by key): {101=Aman, 102=Neha, 103=Priya, 105=Ravi}
Roll 101: Aman
Roll 102: Neha
Roll 103: Priya
Roll 105: Ravi
First key: 101
Last key: 105

How it works:

1. ›Four entries are inserted out of order (103, 101, 105, 102), but TreeMap stores them internally in a sorted tree structure keyed on Integer's natural ordering.
2. ›Printing the map, or iterating its keySet(), always visits the keys in ascending order — 101, 102, 103, 105 — regardless of insertion order.
3. ›firstKey() and lastKey() return the smallest and largest keys directly, without scanning the whole map.

Performance Considerations

O(log n) is worst-case bounded: Unlike HashMap where O(1) average can degrade to O(n) on hash collisions (mitigated by Java 8 treeification), TreeMap's O(log n) is an absolute guarantee. For n = 1,000,000 entries, worst-case height is ~40. For n = 1,000,000,000 entries, worst-case is ~60. The Red-Black invariants make this unconditional.

Range view cost: headMap(), tailMap(), and subMap() return SubMap view objects in O(1) — no copying. Iterating k elements within a range is O(k). This is extremely efficient for analytics queries that touch only a fraction of the map.

Thread safety: TreeMap is not thread-safe. For concurrent sorted map access, use ConcurrentSkipListMap from java.util.concurrent — it provides the same NavigableMap interface with O(log n) thread-safe operations and no global lock.

Best Practices

Declare the variable as NavigableMap<K, V> when range methods are needed. NavigableMap<String, Integer> prices = new TreeMap<>() exposes floor(), ceiling(), headMap(), tailMap(), subMap(), and descendingMap(). SortedMap<String, Integer> exposes only headMap(), tailMap(), subMap(), firstKey(), and lastKey(). Map<String, Integer> hides all navigation methods. Declare the narrowest interface that still exposes the methods callers need.

Always include a tiebreaker in the Comparator to prevent silent key collisions. Two keys where compare(a, b) == 0 are treated as the same key — the second put() replaces the first's value. For a TreeMap sorted by price where two products have the same price, only one is stored. Fix this by appending a secondary comparison field — typically a unique ID: Comparator.comparingDouble(Product::price).thenComparing(Product::id). This is the most common TreeMap correctness bug in production code.

Use range views instead of streaming the entire map. map.subMap(from, to) creates a live view in O(1) and iterates only the k matching entries. map.entrySet().stream().filter(e -> e.getKey() >= from && e.getKey() <= to) iterates all n entries. For large maps with narrow range queries, the subMap approach is O(k + log n) versus O(n).

Pre-build as HashMap then convert to TreeMap for one-time sorted output. Building a TreeMap from n individual inserts is O(n log n). Building a HashMap is O(n), then new TreeMap<>(hashMap) sorts all at once — also O(n log n) total, but with lower constant factors because bulk construction can use more efficient tree-building. If sorted output is only needed once, this pattern keeps the accumulation phase at O(1) per entry.

Common Mistakes

Mistake 1 — Missing Tiebreaker Causes Silent Value Overwrite

Mistake 2 — Inserting null Keys

Mistake 3 — Iterating a Range View While Modifying Its Bounds

Output:
Exception: key outside subMap bounds

Mistake 4 — Using TreeMap When HashMap Performance Is Needed

Interview Questions

Q1. What is TreeMap in Java and how does it differ from HashMap?

TreeMap is a NavigableMap implementation backed by a Red-Black self-balancing binary search tree. It stores entries in ascending key order — natural ordering via Comparable or a supplied Comparator. HashMap uses a hash table, provides O(1) average put() and get(), but guarantees no iteration order. TreeMap provides O(log n) guaranteed for all operations and always iterates in sorted key order. TreeMap also adds the full NavigableMap API — floorKey(), ceilingKey(), headMap(), tailMap(), subMap() — which HashMap has no equivalent for.

Q2. How does TreeMap determine duplicate keys?

TreeMap uses compareTo() (natural ordering) or the Comparator for all comparisons — it never calls equals() or hashCode(). Two keys where compare(a, b) == 0 are treated as identical: the second put() replaces the value without creating a new tree node. This means a class can have equals() returning false for two objects while compareTo() returns 0 — TreeMap still treats them as the same key. This is why the Comparator must include a tiebreaker field (unique ID, timestamp) when the primary sort field is not unique.

Q3. What is the time complexity of TreeMap operations and why is it always O(log n)?

All TreeMap operations — put(), get(), remove(), firstKey(), lastKey(), floorKey(), ceilingKey() — are O(log n) in both average and worst case. This is guaranteed by the Red-Black tree's self-balancing invariants, which bound the tree height at 2 × log₂(n+1) regardless of insertion order. For 1,000,000 entries, every operation traverses at most ~40 nodes. This contrasts with HashMap's O(1) average that can degrade to O(n) on hash collisions (mitigated in Java 8 by treeification, but not eliminated).

Q4. What is the difference between headMap(), tailMap(), and subMap()?

All three return live NavigableMap view objects — no copying. headMap(toKey) returns all entries with keys strictly less than toKey (exclusive); the overloaded headMap(toKey, inclusive) controls the boundary. tailMap(fromKey) returns all entries with keys greater than or equal to fromKey (inclusive by default). subMap(from, to) returns entries with keys in [from, to) — from inclusive, to exclusive by default; the four-argument overload controls both boundaries. Modifications through any view are immediately reflected in the backing TreeMap. Adding a key outside a view's bounds throws IllegalArgumentException.

Q5. Why can't TreeMap have null keys?

TreeMap determines every key's position using compareTo() or the Comparator. Calling compareTo(null) on any object throws NullPointerException — the Java specification requires this. Since TreeMap must compare every new key with existing keys to find its tree position, null cannot be placed anywhere. HashMap can store one null key by placing it in bucket 0 and bypassing hashCode(). If null-tolerant sorted maps are needed, pass Comparator.nullsFirst(Comparator.naturalOrder()) to the TreeMap constructor.

Q6. When would you choose TreeMap over a sorted ArrayList of Map.Entry objects?

TreeMap maintains sorted order on every put() and remove() in O(log n). A sorted ArrayList requires Collections.sort() after each insertion — O(n log n) per sort — and O(n) for remove() by key (binary search finds position, shifting fills the gap). containsKey() on ArrayList is O(n); TreeMap.get() is O(log n). TreeMap also provides floorKey(), ceilingKey(), and range views — none of which ArrayList supports natively. For any use case with frequent insertions, deletions, and key-based lookups, TreeMap is strictly superior to a manually maintained sorted list.

FAQs

Does TreeMap allow duplicate keys?

No. When compare(a, b) == 0, TreeMap treats a and b as the same key and replaces the existing value. This is determined purely by the Comparator or compareTo() — not by equals(). Two objects can be logically different (by equals()) but treated as duplicates by TreeMap if the comparison returns 0 without a tiebreaker field.

What is the difference between TreeMap and TreeSet?

TreeSet is backed by a TreeMap where elements become keys and a shared static PRESENT object is the value. Everything about TreeMap's Red-Black tree, O(log n) operations, null rejection, and NavigableSet API (which parallels NavigableMap) applies directly to TreeSet. Use TreeMap when each key has an associated value to retrieve; use TreeSet for pure membership testing with sorted unique elements.

How do I create a TreeMap in reverse sorted order?

Pass Comparator.reverseOrder() for natural reverse ordering: new TreeMap<>(Comparator.reverseOrder()). For custom reverse ordering: myComparator.reversed(). This creates a max-first tree where firstKey() returns the largest key and lastKey() returns the smallest. descendingMap() provides a reverse-order view of an existing TreeMap without creating a new map.

Is TreeMap thread-safe?

No. Concurrent modifications from multiple threads can corrupt the tree structure. For concurrent sorted maps, use ConcurrentSkipListMap from java.util.concurrent, which implements ConcurrentNavigableMap — the full NavigableMap interface with O(log n) thread-safe operations including floorKey(), ceilingKey(), and all range views.

What is ConcurrentSkipListMap and when should it replace TreeMap?

ConcurrentSkipListMap is a thread-safe sorted map backed by a skip list (probabilistic data structure providing O(log n) expected performance). It supports the full NavigableMap interface without any external synchronisation. Use it when multiple threads need concurrent read and write access to a sorted map. TreeMap with Collections.synchronizedSortedMap() exists but holds a single lock — only one thread accesses the map at a time. ConcurrentSkipListMap allows fine-grained concurrent access at much higher throughput.

What happens if the compareTo() method is inconsistent with equals()?

TreeMap's behaviour becomes inconsistent with the Map contract. The general Map contract defines key uniqueness by equals(). If compareTo() returns 0 for two keys where equals() returns false, TreeMap treats them as one key while a HashMap would treat them as two. BigDecimal is the standard Java example: new BigDecimal("2.0").compareTo(new BigDecimal("2.00")) == 0 but equals() returns false. In a TreeMap<BigDecimal, V>, only one of them can be stored. The Java documentation recommends making compareTo() consistent with equals() for SortedMap keys.

Summary

TreeMap<K, V> is Java's sorted map — O(log n) for every operation, guaranteed by Red-Black tree invariants that bound height at 2 × log₂(n+1). Keys are always maintained in ascending order, and the full NavigableMap API — floorKey(), ceilingKey(), headMap(), tailMap(), subMap(), descendingMap() — enables range queries and nearest-key navigation that no hash-based collection provides.

Two rules prevent the most common TreeMap bugs: always include a tiebreaker in the Comparator when the primary sort field is not unique (equal keys silently overwrite), and never insert null keys (compareTo throws). Range views are live and O(1) to create — use subMap() for range queries instead of streaming and filtering the entire map.

For interviews: explain the Red-Black tree structure and O(log n) guarantee, describe how duplicates are detected via compareTo() not equals(), walk through the NavigableMap method set, explain why null keys throw, and distinguish TreeMap from ConcurrentSkipListMap for concurrent use. These questions appear consistently from fresher campus rounds through senior engineering interviews.

What to Read Next