1. Overview

A TreeMap in Java is a Map implementation that keeps its keys sorted — either by natural ordering or by a custom comparator provided at creation.

Example:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

System.out.println(map); 
// Output: {1=A, 2=B, 3=C} (keys sorted in ascending order)

Unlike HashMap, which uses hashing, TreeMap uses a balanced binary search tree to store its entries — specifically a Red-Black Tree.

---

2. Internal Data Structure

Internally, a TreeMap is based on Red-Black Tree, which is a type of self-balancing binary search tree (BST).

Each node stores:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;  // true = red, false = black
}

This tree maintains the sorted order of keys according to either:

1. The natural ordering of keys (Comparable), or
2. A Comparator supplied to the TreeMap constructor.

---

3. How TreeMap Maintains Order

When you insert (put) a key-value pair:

1. Comparator (or Comparable) is used to compare the new key with existing keys.
2. Based on the comparison result, the key is placed in the left or right subtree.
3. After insertion, Red-Black Tree balancing is performed automatically to maintain height balance.
4. As a result, an in-order traversal of the tree will always give sorted keys.

---

4. Step-by-Step Example

Let’s say you insert keys in the order: 5, 2, 8, 1, 3.

Step 1: Insert 5

• Tree is empty → 5 becomes the root.

   5

Step 2: Insert 2

• 2 < 5 → goes to the left.

    5
   /
  2

Step 3: Insert 8

• 8 > 5 → goes to the right.

    5
   / \
  2   8

Step 4: Insert 1

• 1 < 5 → go left
• 1 < 2 → go left

      5
     / \
    2   8
   /
  1

Step 5: Insert 3

• 3 < 5 → go left
• 3 > 2 → go right

      5
     / \
    2   8
   / \
  1   3

Now the tree structure (in-order traversal) = 1, 2, 3, 5, 8, which is sorted.

---

5. Red-Black Tree Balancing Rules

The Red-Black Tree ensures O(log n) lookup, insertion, and deletion time by maintaining balance using these properties:

1. Every node is either red or black.
2. Root is always black.
3. Red nodes cannot have red children (no two reds in a row).
4. Every path from a node to its descendant null nodes must have the same number of black nodes.
5. Insertion or deletion may temporarily violate these properties — tree rotations and recoloring fix it.

This guarantees that the height of the tree remains close to log₂(n).

---

6. Sorting Mechanisms

Case 1: Natural Ordering

If keys implement Comparable, TreeMap uses their compareTo() method.

Example:

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Banana", 2);
map.put("Apple", 1);
map.put("Cherry", 3);
System.out.println(map); // {Apple=1, Banana=2, Cherry=3}

Order is lexicographical because String implements Comparable<String>.

---

Case 2: Custom Comparator

You can define your own sorting logic:

TreeMap<String, Integer> map = new TreeMap<>(
    (a, b) -> b.compareTo(a)  // reverse order
);
map.put("Banana", 2);
map.put("Apple", 1);
map.put("Cherry", 3);
System.out.println(map); // {Cherry=3, Banana=2, Apple=1}

---

7. Retrieval Order

Because TreeMap is sorted, all traversal operations follow key order:

Method	Description
keySet()	Returns keys in ascending order
descendingKeySet()	Returns keys in descending order
firstKey()	Smallest key
lastKey()	Largest key
subMap(from, to)	Returns a view of part of the map within key range

---

8. Important Differences from HashMap

Feature	TreeMap	HashMap
Data Structure	Red-Black Tree	Hash Table
Ordering	Sorted by key	No order
Null Keys	Not allowed	One null key allowed
Performance	O(log n)	O(1) average
Thread Safety	No	No

---

9. Internal put() Logic (Simplified)

Pseudocode:

public V put(K key, V value) {
    if (root == null) {
        root = new Entry<>(key, value, null);
        return null;
    }

    Entry<K, V> parent;
    int cmp;
    Entry<K, V> t = root;

    do {
        parent = t;
        cmp = comparator == null ? ((Comparable<? super K>) key).compareTo(t.key)
                                 : comparator.compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value); // key already exists
    } while (t != null);

    // Insert new node and rebalance tree
    addEntry(key, value, parent, cmp < 0);
    fixAfterInsertion(newEntry);
    return null;
}

---

10. Key Takeaways

1. TreeMap is based on Red-Black Tree, not hashing.
2. Maintains sorted order of keys using compareTo() or Comparator.
3. Self-balancing ensures O(log n) time for insertion, deletion, and lookup.
4. No null keys allowed (since comparison with null throws NullPointerException).
5. Perfect for range queries, sorted data traversal, and ordered views.