TreeMap

#Introduction

TreeMap is the primary Java Map implementation when you need sorted keys. The central idea:

TreeMap stores mappings in a balanced Red-Black Tree, ordered by key.

Unlike HashMap, where ordering isn't guaranteed, TreeMap continuously maintains its keys according to their natural ordering or a supplied Comparator.

#What is TreeMap?

Package:

java.util.TreeMap

Basic Example

Map<Integer, String> map = new TreeMap<>();

map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

10 → A
20 → B
30 → C

The insertion order doesn't matter — the keys are maintained in sorted order.

TreeMap Is Sorted by Key

This is critical: TreeMap<K, V> sorts according to K (the key), not V (the value).

TreeMap<Integer, String> map = new TreeMap<>();

map.put(30, "Apple");
map.put(10, "Zebra");
map.put(20, "Mango");

10 → Zebra
20 → Mango
30 → Apple

The values aren't sorted.

Why Use TreeMap?

Use TreeMap when you need:

• Sorted keys
• Range queries
• First/last key
• Nearest key
• Floor/ceiling operations
• Navigational operations

For example: "Find the greatest key less than or equal to X." That's exactly the kind of problem TreeMap handles efficiently.

#Internal Data Structure

TreeMap uses a Red-Black Tree.

The actual implementation stores entries as tree nodes. Conceptually each node contains key, value, left, right, parent, color.

What Is a Red-Black Tree?

A self-balancing Binary Search Tree with additional rules involving node colours (RED / BLACK). These rules ensure the tree doesn't become excessively skewed, so its height remains O(log n) — giving TreeMap predictable logarithmic operations.

Why Not a Normal Binary Search Tree?

Inserting 10, 20, 30, 40, 50 into a normal BST could produce a tree that behaves almost like a linked list — search becomes O(n):

A Red-Black Tree rebalances itself, so the height stays approximately logarithmic:

Red-Black Tree Properties

The classic rules are:

1. Every node is either RED or BLACK.
2. The root is black.
3. Null leaves are treated as black.
4. A red node cannot have a red child (RED → RED is invalid).
5. Every path from a node to its descendant null leaves contains the same number of black nodes.

These rules maintain balance.

#TreeMap put()

map.put(key, value);

Natural Ordering

If no Comparator is supplied, keys must generally implement Comparable.

TreeMap<Integer, String> map = new TreeMap<>();

Integer implements Comparable<Integer>, so TreeMap knows 10 < 20 < 30.

#Comparable vs Comparator

This distinction is essential.

Comparable

Defines natural ordering inside the class:

class Employee implements Comparable<Employee> {

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);
    }
}

TreeMap<Employee, String> map = new TreeMap<>();

Comparator

Defines ordering outside the class:

TreeMap<Employee, String> map = new TreeMap<>(
        Comparator.comparingInt(Employee::getSalary)
);

Now the TreeMap sorts keys by salary.

Comparator Takes Priority

If you supply new TreeMap<>(comparator), the TreeMap uses that Comparator for key ordering rather than the key's natural ordering. This is useful when the same class needs different sorting requirements.

class Employee {
    String name;
    int salary;
}

TreeMap<Employee, String> map = new TreeMap<>(Comparator.comparingInt(e -> e.salary));

Now TreeMap's ordering is determined by salary.

#Key Equivalence: compare() == 0

Critical Comparator Trap

TreeMap uses its ordering comparison to determine key equivalence.

Comparator<Employee> comparator = Comparator.comparingInt(Employee::getSalary);

Two different Employees with the same salary compare as compare(a, b) == 0. TreeMap can therefore treat them as the same key for Map purposes, even if a.equals(b) == false. This is a major interview concept.

compareTo() == 0 and Key Uniqueness

For TreeMap, key uniqueness is effectively determined by compareTo() / Comparator, not simply by equals().

Employee A (salary 50000) and Employee B (salary 50000) with a salary-only comparator → compare(A, B) == 0 → treated as equivalent keys.

Comparator Consistency Trap

Comparator<String> comparator = (a, b) -> Integer.compare(a.length(), b.length());

TreeMap<String, Integer> map = new TreeMap<>(comparator);

map.put("Java", 1);
map.put("Code", 2);

Both strings have length 4, so compare("Java", "Code") == 0. The second insertion replaces the first mapping's value — the map ends up with a single entry (key "Java", value 2). This is why Comparator design matters enormously with TreeMap.

#TreeMap get()

map.get(key);

TreeMap starts at the root:

#TreeMap Complexity

TreeMap trades HashMap's average O(1) lookup for a guaranteed sorted structure + navigational operations.

#Navigation Methods

Given keys 10, 20, 30, 40 (values A, B, C, D):

firstKey() and lastKey()

map.firstKey();   // 10 — smallest key
map.lastKey();    // 40 — largest key

firstEntry() and lastEntry()

Retrieve the complete mapping:

map.firstEntry();   // 10 = A
map.lastEntry();    // 40 = D

lowerKey()

Greatest key strictly less than the specified key:

map.lowerKey(30);   // 20

floorKey()

Greatest key less than or equal to the specified key:

map.floorKey(30);   // 30
map.floorKey(35);   // 30

higherKey()

Smallest key strictly greater than the specified key:

map.higherKey(30);   // 40

ceilingKey()

Smallest key greater than or equal to the specified key:

map.ceilingKey(30);   // 30
map.ceilingKey(35);   // 40

The Four Important Navigation Methods

Memorize this table:

Entry Versions

Every major navigation operation has an Entry equivalent: lowerEntry(), floorEntry(), ceilingEntry(), higherEntry(). Instead of returning only the key, they return a Map.Entry<K,V>:

Map.Entry<Integer, String> entry = map.floorEntry(35);

pollFirstEntry() and pollLastEntry()

Return and remove the smallest / largest mapping.

map.pollFirstEntry();

For 10 → A, 20 → B, 30 → C, after pollFirstEntry() the map is 20 → B, 30 → C. pollLastEntry() removes the largest mapping. Useful for min/max processing, priority-style workflows and ordered data management.

descendingMap() and descendingKeySet()

map.descendingMap();      // reverse-order view: 30, 20, 10
map.descendingKeySet();   // keys in descending order

Useful when you need reverse traversal without copying the Map.

#Range Queries

One of TreeMap's biggest advantages. For keys 10, 20, 30, 40, 50, to get 20 through 40:

map.subMap(20, true, 40, true);   // 20, 30, 40

subMap()

Modern form: subMap(fromKey, fromInclusive, toKey, toInclusive).

map.subMap(20, true, 40, false);   // 20, 30 — 20 included, 40 excluded

headMap()

Entries before a specified key:

map.headMap(30);         // 10, 20
map.headMap(30, true);   // 10, 20, 30

tailMap()

Entries from a specified key onward:

map.tailMap(30);          // 30, 40, 50
map.tailMap(30, false);   // 40, 50

Range Views Are Views

This is important. subMap(), headMap() and tailMap() return views, not necessarily independent copies. Modifications can affect the original TreeMap. This is useful but requires care.

#NavigableMap and SortedMap

TreeMap implements NavigableMap<K,V>, which provides navigation operations (lower, floor, ceiling, higher) plus pollFirstEntry(), pollLastEntry() and descendingMap().

NavigableMap is an enhanced version of SortedMap.

#Null Handling

Null Keys

A common interview trap. TreeMap generally does not permit a null key when using natural ordering:

TreeMap<Integer, String> map = new TreeMap<>();

map.put(null, "A");

NullPointerException

Why? Because TreeMap needs to compare keys.

Null Values

Null values are generally allowed — map.put(10, null); — the issue is the key comparison, not the value.

Can a Comparator Support Null Keys?

Potentially yes, if the supplied Comparator explicitly handles null:

TreeMap<Integer, String> map = new TreeMap<>(
        Comparator.nullsFirst(Comparator.naturalOrder())
);

#Thread Safety

Like HashMap and LinkedHashMap, TreeMap is not inherently thread-safe. For concurrent sorted-map requirements, Java provides ConcurrentSkipListMap rather than a synchronized TreeMap implementation.

#Comparisons

TreeMap vs HashMap

Use HashMap for the fastest general-purpose lookup; use TreeMap for sorted/navigable key operations.

TreeMap vs LinkedHashMap

When TreeMap Is the Right Choice

Strong TreeMap signals in a requirement:

• "Keep keys sorted."
• "Find the nearest key."
• "Find all entries between X and Y."
• "Find the smallest key greater than X."

#Real-World Examples

Price ranges

Price → Product: find the highest price not exceeding 5000.

Integer price = products.floorKey(5000);

Much cleaner than scanning every entry.

Scheduling

timestamp → task: find the next scheduled task after time T.

map.higherEntry(timestamp);

Range query

Employee ID → Employee: employees with IDs between 1000 and 2000.

map.subMap(1000, true, 2000, true);

#Mutable Keys and Rebalancing

Mutable Keys and TreeMap

HashMap has a mutable-key problem involving hashCode(). TreeMap has a related problem involving ordering. If the fields used by the Comparator/compareTo() change after insertion, the tree's ordering assumptions can become invalid.

put() Mental Model

remove() Mental Model

Tree Rotations

Rebalancing can use left rotations and right rotations. A right rotation on a left-leaning chain:

Why Rotation Works

The in-order ordering remains 10 < 20 < 30, but the tree becomes much more balanced. Red-Black Tree rules determine when rotations/recolouring are necessary.

#Keys, Values and Entries

Does TreeMap Store Sorted Values?

No. It stores sorted keys. The values remain associated with their keys but don't influence tree ordering (unless the values are actually part of the key/comparator design).

Can TreeMap Have Duplicate Values?

Yes — map.put(10, "A"); map.put(20, "A"); is perfectly valid.

Can TreeMap Have Duplicate Keys?

No. But remember: "duplicate" is determined by the TreeMap's comparison. If compare(k1, k2) == 0, TreeMap treats them as equivalent keys.

firstKey() vs firstEntry()

firstKey() returns K, while firstEntry() returns Map.Entry<K,V>. Likewise lastKey() / lastEntry().

pollFirstEntry() vs firstEntry()

#Decision Framework

Final Mental Model

Every key follows: Key → Comparator / compareTo() → left or right → balanced tree.

The main trade-off: