Java TreeMap Internal Working

TreeMap<K, V> stores every key-value entry in a self-balancing Red-Black tree. Every put(), get(), and remove() is a tree traversal — comparing keys at each node to decide left or right, guaranteed to complete in O(log n) regardless of insertion order. The sorted key order that TreeMap delivers is a direct consequence of how a binary search tree works: in-order traversal of the tree always yields keys in ascending order. This is what separates TreeMap from HashMap — HashMap is faster on average, but TreeMap is the only standard Map that lets you ask "what is the key closest to X?" or "give me all entries with keys between A and B?" in O(log n).

What Is Inside a TreeMap?

TreeMap<K, V> is backed by a single Red-Black tree. The class holds a reference to the root node, a comparator (or null for natural ordering), the entry count, and a modification counter for fail-fast iteration.

TREEMAP INTERNAL FIELDS (simplified from JDK source):

  private transient Entry<K,V>  root;          ← root of the Red-Black tree
  private transient int         size;           ← number of key-value entries
  private final Comparator<? super K> comparator; ← null means natural ordering
  private transient int         modCount;       ← fail-fast iterator support

  private static final boolean RED   = false;
  private static final boolean BLACK = true;

  static final class Entry<K,V> implements Map.Entry<K,V> {
      K          key;
      V          value;
      Entry<K,V> left;    ← left child  (keys < this.key)
      Entry<K,V> right;   ← right child (keys > this.key)
      Entry<K,V> parent;  ← parent node (null for root)
      boolean    color;   ← RED or BLACK
  }

EMPTY TREEMAP:
  root        = null
  size        = 0
  comparator  = null (uses Comparable.compareTo())
  modCount    = 0

AFTER put("banana",2), put("apple",1), put("cherry",3):

                    root
                     |
               [banana/BLACK]
               /             \
        [apple/RED]       [cherry/RED]
        left=null          left=null
        right=null         right=null

  in-order traversal: apple → banana → cherry  (alphabetical order)
  This is what entrySet() and keySet() iteration always returns.

Basic Overview — How Each Core Method Works

OPERATION          INTERNAL MECHANISM                              COMPLEXITY
───────────────────────────────────────────────────────────────────────────────
put(k, v)          BST insert: compare at each node, go left/right  O(log n)
                   then fix Red-Black properties (rotations/recolor)

get(k)             BST search: compare at each node, go left/right  O(log n)
                   until match or null

remove(k)          BST delete: find node, splice out, fix RB props   O(log n)

containsKey(k)     BST search, same as get                           O(log n)

firstKey()         leftmost node of tree                             O(log n)
lastKey()          rightmost node of tree                            O(log n)

floorKey(k)        largest key <= k                                  O(log n)
ceilingKey(k)      smallest key >= k                                 O(log n)
lowerKey(k)        largest key strictly < k                          O(log n)
higherKey(k)       smallest key strictly > k                         O(log n)

headMap(toKey)     view of entries with keys < toKey                 O(log n)
tailMap(fromKey)   view of entries with keys >= fromKey              O(log n)
subMap(from, to)   view of entries with keys in [from, to)           O(log n)

size()             return size field                                  O(1)
isEmpty()          return size == 0                                   O(1)

in-order iteration all keys in ascending order                        O(n)
(entrySet, keySet, values — all return sorted views)

KEY RULE:
  All single-key operations are O(log n) — no O(1) average like HashMap.
  In exchange: keys are always sorted, range queries work, no hashCode needed.

When to Use TreeMap

USE TreeMap WHEN:

  1. Sorted key iteration is required
     — entrySet(), keySet(), values() always return entries in key order
     — event logs sorted by timestamp, leaderboard sorted by score

  2. Range queries are needed
     — "all orders placed between 9 AM and 5 PM"
     — headMap(toKey), tailMap(fromKey), subMap(from, to)
     — these views are live backed maps, not copies

  3. Closest-match lookup is needed
     — floorKey(k): largest key ≤ k (last event at or before timestamp)
     — ceilingKey(k): smallest key ≥ k (next scheduled slot)
     — lowerKey(k) / higherKey(k): strict variants

  4. Keys implement Comparable or a Comparator is provided
     — String, Integer, Long, LocalDate all implement Comparable
     — Custom sort order: new TreeMap<>(Comparator.reverseOrder())

DO NOT USE TreeMap WHEN:
  — Pure key-value lookup speed is the priority: use HashMap (O(1) avg)
  — Insertion order iteration is needed: use LinkedHashMap
  — Keys are null: TreeMap NEVER allows null keys (NullPointerException)
  — Keys do not implement Comparable and no Comparator is provided:
    ClassCastException at runtime on first put()

TREEMAP vs HASHMAP vs LINKEDHASHMAP:
  HashMap:        O(1) avg get/put, no order guarantee, allows null key
  LinkedHashMap:  O(1) avg get/put, insertion order, allows null key
  TreeMap:        O(log n) get/put, sorted key order, null key rejected

How TreeMap Works Internally

The Red-Black Tree

A Red-Black tree is a binary search tree with four structural rules that guarantee the tree stays balanced after every insert and delete. These rules bound the height to O(log n), which is why every TreeMap operation is O(log n) regardless of insertion sequence.

RED-BLACK TREE RULES:
  1. Every node is either RED or BLACK
  2. The root is always BLACK
  3. Every null leaf (sentinel) is BLACK
  4. A RED node's children are always BLACK
     (no two consecutive RED nodes on any path)
  5. Every path from any node to its descendant null leaves
     has the same number of BLACK nodes (Black-Height property)

WHY RULES 4 AND 5 TOGETHER GUARANTEE BALANCE:
  Rule 5: equal black nodes on all paths means no path can be
          more than twice as long as any other path.
  Rule 4: red nodes cannot be consecutive, so the longest
          possible path alternates red/black: 2 × (black height).
  Result: height ≤ 2 × log₂(n+1) → O(log n) guaranteed.

  Compare to a plain BST:
    put(1), put(2), put(3), put(4) ... put(n) in order
    → degrades into a linear chain → O(n) get/put
    TreeMap NEVER degrades regardless of insertion order.

TREE ROTATIONS — used after insert/delete to restore balance:
  Left Rotation (x becomes right child of its old left child):
          x               y
         / \             / \
        A   y    →      x   C
           / \         / \
          B   C       A   B

  Right Rotation (mirror of left):
          x               y
         / \             / \
        y   C    →      A   x
       / \                 / \
      A   B               B   C

  Rotations preserve BST ordering while restructuring the tree shape.
  A put() may require at most O(log n) recoloring and 2 rotations.
  A remove() may require at most O(log n) recoloring and 3 rotations.

put() — BST Insert and Red-Black Fix

put("grape", 4) into tree containing apple/banana/cherry/date:

CURRENT TREE (simplified):
              banana (BLACK)
             /              \
       apple (BLACK)      date (BLACK)
                          /           \
                    cherry (RED)    grape? ← to be inserted

STEP 1 — BST DESCENT (compare keys at each node):
  Start at root (banana):
    "grape" > "banana" → go RIGHT → reach date
  At date:
    "grape" > "date" → go RIGHT → reach null
  Insert new Entry("grape", 4) as RED node at date.right

STEP 2 — RED-BLACK FIX (fixAfterInsertion):
  New node is RED. Parent (date) is BLACK.
  Rule 4: RED parent would violate the rule — but parent is BLACK, so OK.
  No rotation needed in this case. Tree remains valid.

CASES THAT REQUIRE ROTATIONS:
  Case 1 — Parent RED, Uncle RED:
    Recolor: parent → BLACK, uncle → BLACK, grandparent → RED
    Continue fix up toward root

  Case 2 — Parent RED, Uncle BLACK, node is inner grandchild:
    Rotate parent to make node an outer grandchild
    Then handle as Case 3

  Case 3 — Parent RED, Uncle BLACK, node is outer grandchild:
    Rotate grandparent, swap colors of parent and grandparent
    Tree balanced — done

get() — BST Binary Search

get("date"):

  STEP 1: Start at root (banana)
    compare("date", "banana") → "date" > "banana" → go right

  STEP 2: At node date
    compare("date", "date") → 0 → MATCH
    return node.value

  STEP 3 (if not found): reach null child → return null

  COMPARISON METHOD:
    if (comparator != null):
      comparator.compare(key, nodeKey)      ← use provided Comparator
    else:
      ((Comparable<K>) key).compareTo(nodeKey) ← use natural ordering

  This is why null keys are rejected:
    null.compareTo(x) → NullPointerException
    comparator may also reject null depending on implementation

firstKey(), lastKey(), and NavigableMap Operations

firstKey() — leftmost node:
  Entry<K,V> p = root;
  while (p.left != null) p = p.left;
  return p.key;

  This finds the minimum key by always going left.

lastKey() — rightmost node:
  Entry<K,V> p = root;
  while (p.right != null) p = p.right;
  return p.key;

floorKey(k) — largest key ≤ k:
  Traverse tree. At each node:
    if node.key <= k: this is a candidate floor; go right to find larger valid key
    if node.key >  k: go left (current node is too large)
  Return best candidate found.

ceilingKey(k) — smallest key ≥ k:
  Mirror of floorKey: node.key >= k → candidate, go left for smaller valid key
                      node.key < k  → go right

subMap(fromKey, toKey) — live view of entries in [fromKey, toKey):
  Returns a SubMap that wraps the TreeMap.
  Reads and writes through to the backing TreeMap.
  Any put() into the SubMap with a key outside [from, to) throws IllegalArgumentException.
  Internally uses comparisons against fromKey and toKey as bounds during iteration.

headMap(toKey) — live view of entries with keys < toKey
tailMap(fromKey) — live view of entries with keys >= fromKey

Core Operations with Examples

Sorted Order, Navigation, and Range Views

Output:
=== Sorted iteration (always ascending) ===
  Ananya     97
  Arjun      95
  Karan      84
  Meera      88
  Priya      91
  Rohan      79

=== Boundary access ===
firstKey()         : Ananya
lastKey()          : Rohan
firstEntry()       : Ananya=97
lastEntry()        : Rohan=79

=== Closest-match navigation ===
floorKey(Karan)    : Karan
floorKey(Kavya)    : Karan
ceilingKey(Karan)  : Karan
ceilingKey(Kavya)  : Meera
lowerKey(Meera)    : Karan
higherKey(Meera)   : Priya

=== Range views (backed by the same TreeMap) ===
headMap(Meera) keys  < Meera : [Ananya, Arjun, Karan]
tailMap(Meera) keys >= Meera : [Meera, Priya, Rohan]
subMap(Karan, Priya) [Karan, Priya): [Karan, Meera]

=== Descending iteration ===
  Rohan      79
  Priya      91
  Meera      88
  Karan      84
  Arjun      95
  Ananya     97

Custom Comparator and Reverse Ordering

Output:
=== Reverse alphabetical order ===
  Spring       3
  Redis        5
  Kafka        4
  Hibernate    2
  Docker       1

=== Sort by length, then alphabetical ===
  C              (1 chars) compiled
  Go             (2 chars) compiled
  Java           (4 chars) compiled
  Rust           (4 chars) compiled
  Python         (6 chars) interpreted
  JavaScript     (10 chars) interpreted

=== Case-insensitive key comparison ===
get(ADMIN)   : role-admin
get(admin)   : role-admin
get(Admin)   : role-admin
Sorted keys  : [Admin, developer, manager, VIEWER]

=== Null key rejection ===
put(null, 1) throws NullPointerException

pollFirstEntry, pollLastEntry, and Live Submap Mutations

Output:
=== pollFirstEntry / pollLastEntry ===
Before: [900, 1030, 1200, 1400, 1530]
pollFirstEntry: 900=market-open
pollLastEntry : 1530=market-close
Remaining     : [1030, 1200, 1400]

=== subMap with inclusive/exclusive bounds ===
All keys: [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
subMap[300, 600]: [300, 400, 500, 600]
headMap(400, inclusive): [100, 200, 300, 400]
tailMap(700, exclusive): [800, 900, 1000]

=== Live subMap — mutations write through ===
SubView before: [Banana, Cherry]
SubView after put(Coconut): [Banana, Cherry, Coconut]
Inventory now: [Apple, Banana, Cherry, Coconut, Date, Elderberry]
put(Elderberry) outside range → IllegalArgumentException

Real-World Example — Zepto Inventory Slot Scheduler

Zepto's 10-minute delivery service assigns incoming orders to delivery slot windows based on estimated preparation time. A TreeMap<LocalTime, DeliverySlot> keeps slots sorted by time automatically. The scheduler queries ceilingKey(requestedTime) to find the next available slot in O(log n), uses subMap() to fetch all slots in a delivery window, and uses pollFirstEntry() to dispatch the earliest pending slot.

Output:
--- Registering delivery slots ---
====================================================
  All registered slots (TreeMap — sorted by time):
====================================================
  09:00 → 09:00 [0/3 orders]
  09:10 → 09:10 [0/3 orders]
  09:20 → 09:20 [0/2 orders]
  09:30 → 09:30 [0/3 orders]
  09:40 → 09:40 [0/2 orders]
  09:50 → 09:50 [0/3 orders]
  10:00 → 10:00 [0/4 orders]
====================================================

--- Assigning orders ---
  [ASSIGNED] ORD-001 → slot 09:00
  [ASSIGNED] ORD-002 → slot 09:00
  [ASSIGNED] ORD-003 → slot 09:10
  [ASSIGNED] ORD-004 → slot 09:10
  [ASSIGNED] ORD-005 → slot 09:20
  [ASSIGNED] ORD-006 → slot 09:20
  [ASSIGNED] ORD-007 → slot 09:30
  [ASSIGNED] ORD-008 → slot 09:00
  [ASSIGNED] ORD-009 → slot 09:10
  [ASSIGNED] ORD-010 → slot 09:30

====================================================
  All registered slots (TreeMap — sorted by time):
====================================================
  09:00 → 09:00 [3/3 orders]
  09:10 → 09:10 [3/3 orders]
  09:20 → 09:20 [2/2 orders]
  09:30 → 09:30 [2/3 orders]
  09:40 → 09:40 [0/2 orders]
  09:50 → 09:50 [0/3 orders]
  10:00 → 10:00 [0/4 orders]
====================================================

--- Slots in 09:20 to 09:40 window (subMap) ---
  09:20 → 09:20 [2/2 orders]
  09:30 → 09:30 [2/3 orders]
  09:40 → 09:40 [0/2 orders]

--- Dispatching earliest slot (pollFirstEntry) ---
Dispatched: 09:00 — orders: [ORD-001, ORD-002, ORD-008]
Remaining slots: [09:10, 09:20, 09:30, 09:40, 09:50, 10:00]

Performance Considerations

TreeMap iteration is more memory-predictable than HashMap iteration. HashMap's entrySet() traversal visits every bucket slot — a map with 16 entries and capacity 256 scans 256 slots. TreeMap's in-order traversal visits exactly n nodes. For sparse maps with frequent full iteration, TreeMap is more efficient.

No resize penalty. TreeMap never resizes. The Red-Black tree grows incrementally by adding one Entry node per put(). HashMap triggers O(n) resizes when size > threshold. For maps that receive entries gradually over time, TreeMap has more predictable per-operation latency with no periodic O(n) spikes.

Best Practices

Ensure key objects implement Comparable correctly, or provide a Comparator at construction. Without either, the first put() throws ClassCastException at runtime — not a compile error. The Comparator must be consistent with equals(): if comparator.compare(a, b) == 0, then a.equals(b) should also be true. Violations cause silent data loss: two keys that compare as equal are treated as the same key, so the second put() overwrites the first without warning.

Pass the Comparator to the constructor — not as a sort step after population. TreeMap uses its Comparator to maintain order during every put(). Sorting a separate list and then inserting does not give you a Comparator-aware TreeMap; insertion order is not preserved. If custom ordering is needed, always: new TreeMap<>(myComparator).

Use subMap(), headMap(), and tailMap() for range queries instead of filtering with streams. treeMap.subMap(low, high) is O(log n) to set up and O(k) to iterate k results. The equivalent stream pipeline — treeMap.entrySet().stream().filter(e -> e.getKey() >= low && e.getKey() < high) — is O(n) because it scans all entries. For large maps with range-query workloads, the TreeMap-native approach is significantly faster.

Prefer TreeMap over sorting an ArrayList when entries are inserted and queried interleaved. Building an ArrayList, sorting it O(n log n), then searching O(log n) is correct once. But if entries keep arriving and range queries happen throughout, maintaining a TreeMap — O(log n) per insert, O(log n) per range query setup — is more efficient than repeated sort cycles.

Common Mistakes

Mistake 1 — Key Class That Does Not Implement Comparable

Output:
Sorted by price: 2

Mistake 2 — Comparator Inconsistent With equals()

Mistake 3 — Using TreeMap When O(1) Lookup Is All That Is Needed

Mistake 4 — Modifying subMap Keys Outside the Allowed Range

Output:
put(800) → IllegalArgumentException (outside subMap range)
midRange after valid put: [300, 350, 400, 500, 600]

Interview Questions

Q1. What data structure backs TreeMap internally and what guarantees does it provide?

TreeMap is backed by a Red-Black tree — a self-balancing binary search tree. Every node is an Entry<K,V> holding the key, value, left and right child references, a parent reference, and a boolean color field (RED or BLACK). The five Red-Black properties guarantee the tree height stays at O(log n) regardless of insertion order. This means put(), get(), remove(), and all navigation operations are O(log n) guaranteed — unlike HashMap, which is O(1) average but O(n) worst case when hash collisions cluster entries in one bucket.

Q2. How does TreeMap maintain sorted key order?

TreeMap maintains the binary search tree invariant on every put() and remove(): left child keys are always less than the parent key, right child keys are always greater. This means in-order traversal of the tree — left subtree, node, right subtree — always yields keys in ascending order. entrySet(), keySet(), and values() all return sorted views by performing in-order traversal internally. No sorting happens at read time; the tree is kept in order at write time.

Q3. What is the difference between floorKey(), ceilingKey(), lowerKey(), and higherKey()?

All four are O(log n) NavigableMap operations that find the closest key to a given value. floorKey(k) returns the largest key less than or equal to k — or null if none exists. ceilingKey(k) returns the smallest key greater than or equal to k. lowerKey(k) is the strict version of floorKey — it returns the largest key strictly less than k. higherKey(k) is the strict version of ceilingKey — strictly greater than k. These are used for nearest-match queries that HashMap cannot support at all.

Q4. Why does TreeMap reject null keys while HashMap allows them?

TreeMap compares keys at every tree traversal step using either Comparable.compareTo() or the provided Comparator. Calling null.compareTo(x) throws NullPointerException. Even with a Comparator, the standard Comparator implementations throw NullPointerException for null inputs. The prohibition is structural — the binary search descent requires ordering every key at every node. HashMap handles null specially by routing it to bucket 0 with an explicit key == null check, which TreeMap cannot do.

Q5. What is the difference between subMap(), headMap(), and tailMap() in TreeMap?

All three return live views backed by the same TreeMap. subMap(fromKey, toKey) returns entries with keys in the range [fromKey, toKey) — inclusive from, exclusive to. The inclusive/exclusive bounds can be flipped using the four-argument form subMap(from, fromInclusive, to, toInclusive). headMap(toKey) returns all entries with keys strictly less than toKey. tailMap(fromKey) returns all entries with keys greater than or equal to fromKey. Live view means reads and writes through the submap operate on the original TreeMap. Writes with keys outside the defined range throw IllegalArgumentException.

Q6. When would you choose TreeMap over HashMap?

TreeMap is the right choice when sorted key order or range queries are needed. Specifically: when iterating entries in key order, when finding the nearest key (floor/ceiling), when querying a key range (subMap), or when dispatching the minimum or maximum key (pollFirstEntry/pollLastEntry). If none of these apply — if the only operation is get/put by exact key — HashMap's O(1) average is faster than TreeMap's O(log n). For 1 million entries, O(log n) is about 20 comparisons per operation compared to O(1) for HashMap. The sorted ordering is the premium paid for the O(log n) cost.

FAQs

What is the time complexity of all TreeMap operations?

Every single-key operation — put(), get(), remove(), containsKey(), firstKey(), lastKey(), floorKey(), ceilingKey(), lowerKey(), higherKey() — is O(log n). subMap(), headMap(), and tailMap() are O(log n) to create the view and O(k) to iterate k entries. Full iteration via entrySet() or keySet() is O(n). size() and isEmpty() are O(1).

Does TreeMap allow duplicate keys?

No. Like all Map implementations, TreeMap stores at most one value per key. A second put() with an existing key replaces the old value and returns it. What makes TreeMap uniquely dangerous for duplicates is the Comparator path: if comparator.compare(k1, k2) == 0, TreeMap treats k1 and k2 as the same key regardless of what equals() says. A Comparator without a tiebreaker that sorts distinct-but-equal-length strings will silently overwrite entries.

Is TreeMap thread-safe?

No. TreeMap is not synchronised. Concurrent reads and writes without external locking corrupt the tree structure — the Red-Black rebalancing modifies multiple node references atomically in a single put(), and concurrent threads can see partial states. For thread-safe sorted map access, use Collections.synchronizedSortedMap(new TreeMap<>()) for a global-lock wrapper, or ConcurrentSkipListMap for a lock-free concurrent sorted map with the same NavigableMap operations.

Can TreeMap store a custom class as a key without implementing Comparable?

Yes, by providing a Comparator at construction: new TreeMap<>(comparator). The Comparator is then used for all key comparisons instead of compareTo(). The class does not need to implement Comparable. The Comparator must be consistent with equals() to avoid silent data loss — comparator.compare(a, b) == 0 implies a.equals(b) should also be true.

What is ConcurrentSkipListMap and how does it relate to TreeMap?

ConcurrentSkipListMap<K, V> in java.util.concurrent is a thread-safe sorted map that implements the same NavigableMap interface as TreeMap. It uses a probabilistic skip list structure instead of a Red-Black tree, allowing lock-free concurrent reads and lock-free concurrent writes at different key ranges. For single-threaded sorted map use, TreeMap is faster. For concurrent workloads where sorted order matters, ConcurrentSkipListMap is the correct replacement — not Collections.synchronizedSortedMap(new TreeMap<>()), which serialises all operations through a single lock.

Does TreeMap preserve insertion order?

No. TreeMap always maintains key order based on the Comparator or natural ordering — not insertion order. Inserting "banana", "apple", "cherry" produces iteration order "apple", "banana", "cherry" regardless of insertion sequence. For insertion-order preservation with O(1) average get/put, use LinkedHashMap.

Summary

TreeMap<K, V> is a Red-Black tree where every node is an Entry holding key, value, left, right, parent, and color. The five Red-Black properties bound tree height to O(log n), making put(), get(), remove(), and all navigation operations O(log n) guaranteed. In-order traversal of the tree — what entrySet(), keySet(), and values() perform — always yields keys in ascending order.

TreeMap earns its O(log n) cost when sorted order or range queries matter: floorKey(), ceilingKey() for closest-match lookups, subMap() / headMap() / tailMap() for range views, firstKey() / lastKey() for boundary access, and pollFirstEntry() / pollLastEntry() for priority-queue-like dispatch. For pure key-value lookup with no ordering requirement, HashMap is the right choice.

Two implementation details answer most TreeMap interview questions: the Comparator consistency rule (inconsistency causes silent key overwrites) and null key rejection (BST descent requires comparing every key — null cannot be compared).

What to Read Next