# Deep Dive (java.util) - TreeMap 

> *"When you need your keys sorted, there's a Red-Black tree working silently behind every* `get()`*."*

`TreeMap` is a sorted map backed by a **Red-Black tree** — a self-balancing binary search tree. This deep dive explains the tree structure, rotations, and when to choose TreeMap over HashMap.

* * *

## What is TreeMap, Really?

`TreeMap` stores key-value pairs in a **Red-Black tree** — a self-balancing binary search tree that guarantees O(log n) operations for get, put, and remove.

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/7b2ee7b2-7964-4f84-87c8-1db8f58940cb.png align="center")

**Key insight:** Unlike HashMap, TreeMap keeps entries **sorted by key** at all times. Iteration always returns keys in sorted order.

* * *

## Red-Black Tree Basics

A Red-Black tree is a binary search tree with these additional properties:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/d828b6fa-eae1-4e13-94cc-2ab8517e0549.png align="center")

These properties guarantee that the tree's height is at most **2 × log₂(n + 1)**, ensuring O(log n) for all operations.

### The Entry Node

```java
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;    // Left child
    Entry<K,V> right;   // Right child
    Entry<K,V> parent;  // Parent node
    boolean color = BLACK; // RED or BLACK
}
```

### Example Red-Black Tree

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/c600e59c-ee49-4738-aa1d-335bf55fbc06.png align="center")

In this tree:

*   Every path from root (13) to a null leaf passes through exactly **2 BLACK** nodes
    
*   No RED node has a RED child
    
*   The root (13) is BLACK
    

* * *

## How put() Works — Insert and Rebalance

### Phase 1: Binary Search Tree Insert

First, traverse the tree to find the correct position:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/22c2baf3-0ff6-4bc3-bb6e-f216e60e7e77.png align="center")

### Phase 2: Fix Violations (Rotations and Recoloring)

After inserting a RED node, we may violate rule 3 (no adjacent RED nodes). The `fixAfterInsertion` method corrects this:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a995bff8-3e6c-44c8-8df8-6abf78140647.png align="center")

### Rotation Visualized

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/f7ad0933-3e4e-49f4-9548-73e73760386e.png align="center")

* * *

## How get() Works — Binary Search

```java
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p == null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    if (comparator != null)
        return getEntryUsingComparator(key);
    
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p; // Found!
    }
    return null; // Not found
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a117173d-5aa1-47ba-bda1-cf998e56c11e.png align="center")

* * *

## How remove() Works

Removal from a Red-Black tree is the most complex operation:

1.  Find the node (binary search — O(log n))
    
2.  If node has two children, replace with **in-order successor**
    
3.  Delete the node
    
4.  Fix Red-Black violations (`fixAfterDeletion`)
    

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/5b3a3699-df5c-4782-9958-c4cb583a0364.png align="center")

* * *

## NavigableMap Operations

TreeMap's killer feature is its rich **navigation API**:

```java
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");
map.put(40, "forty");
map.put(50, "fifty");

// Floor: greatest key ≤ given key
map.floorKey(25);    // 20
map.floorKey(30);    // 30

// Ceiling: smallest key ≥ given key
map.ceilingKey(25);  // 30
map.ceilingKey(30);  // 30

// Lower/Higher: strictly less/greater
map.lowerKey(30);    // 20
map.higherKey(30);   // 40

// First/Last
map.firstKey();      // 10
map.lastKey();       // 50

// Range views (backed by the same tree!)
SortedMap<Integer, String> sub = map.subMap(20, 40);
// {20=twenty, 30=thirty} — excludes 40

NavigableMap<Integer, String> desc = map.descendingMap();
// {50=fifty, 40=forty, 30=thirty, 20=twenty, 10=ten}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/e6a77ce5-5778-4181-a32d-264ff322431f.png align="center")

> **Key insight:** Range views (`subMap`, `headMap`, `tailMap`) are **views** — they reflect changes to the original map and vice versa. They don't copy data.

* * *

## Comparator vs Comparable

TreeMap orders keys using one of two mechanisms:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/8a09fc50-49fb-48c0-be2c-d1f12578ddc7.png align="center")

```java
// Natural ordering (keys must be Comparable)
TreeMap<String, Integer> map1 = new TreeMap<>();
map1.put("Banana", 2);
map1.put("Apple", 1);
map1.put("Cherry", 3);
// Iteration: Apple, Banana, Cherry (alphabetical)

// Custom Comparator — reverse order
TreeMap<String, Integer> map2 = new TreeMap<>(Comparator.reverseOrder());
map2.putAll(map1);
// Iteration: Cherry, Banana, Apple

// Custom Comparator — by string length
TreeMap<String, Integer> map3 = new TreeMap<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())
);
```

> **Warning:** If your `Comparator` says two keys are equal (`compare` returns 0), TreeMap treats them as the **same key** — the second `put` will overwrite the first, even if `equals()` says they're different!

* * *

## Performance Characteristics

| Operation | Time Complexity | Notes |
| --- | --- | --- |
| `get(key)` | O(log n) | Binary search down the tree |
| `put(key, value)` | O(log n) | Search + insert + rebalance |
| `remove(key)` | O(log n) | Search + delete + rebalance |
| `containsKey(key)` | O(log n) | Same as get |
| `containsValue(value)` | **O(n)** | Must scan all nodes |
| `firstKey()` / `lastKey()` | O(log n) | Walk left/right edge |
| `floorKey()` / `ceilingKey()` | O(log n) | Modified binary search |
| `subMap()` / `headMap()` / `tailMap()` | O(log n) to create | View creation is cheap |
| Iteration | O(n) | In-order traversal |

* * *

## TreeMap vs HashMap vs LinkedHashMap

| Aspect | HashMap | TreeMap | LinkedHashMap |
| --- | --- | --- | --- |
| **Order** | None | Sorted by key | Insertion order |
| **get/put** | O(1) avg | O(log n) | O(1) avg |
| **Null keys** | 1 allowed | ❌ Not allowed | 1 allowed |
| **Null values** | ✅ | ✅ | ✅ |
| **Thread-safe** | ❌ | ❌ | ❌ |
| **Navigation** | ❌ | ✅ floor/ceiling/range | ❌ |
| **Memory** | Moderate | High (tree nodes) | HashMap + linked list |
| **Best for** | General use | Sorted data, range queries | Ordered iteration, LRU cache |

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/8c8c99b4-4791-4fd1-bb41-d11dd9365716.png align="center")

* * *

## Common Pitfalls

### Pitfall 1: Non-Comparable Keys Without Comparator

```java
// ❌ ClassCastException at runtime!
TreeMap<Object, String> map = new TreeMap<>();
map.put(new Object(), "value");
// Object doesn't implement Comparable → crash

// ✅ Provide a Comparator
TreeMap<Object, String> map = new TreeMap<>(
    Comparator.comparingInt(System::identityHashCode)
);
```

### Pitfall 2: Inconsistent Comparator and equals()

```java
// ❌ TRAP: Comparator says case-insensitive, equals() is case-sensitive
TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("Hello", 1);
map.put("HELLO", 2); // Overwrites! Comparator says "Hello" == "HELLO"
map.size();           // 1, not 2!
```

### Pitfall 3: Null Keys

```java
// ❌ NullPointerException!
TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1);  // Cannot compare null with Comparable.compareTo()
```

* * *

## Summary

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/0d7b387e-4243-41eb-8f95-d64553e58b67.png align="center")

**The one-liner:** TreeMap is a Red-Black tree providing O(log n) sorted map operations with rich navigation APIs — choose it when you need range queries or sorted iteration, accept the O(log n) cost vs HashMap's O(1).