The TreeMap class in Java is a part of the Java Collections Framework (JCF) and implements the NavigableMap interface, which extends SortedMap. Unlike HashMap, which stores key-value pairs in no predictable order, TreeMap automatically sorts its keys based on their natural ordering or a custom comparator provided at map creation.

Let’s go step by step to understand how it works internally.

---

1. Internal Data Structure

Internally, TreeMap is implemented using a Red-Black Tree, which is a self-balancing binary search tree.
Each node in this tree is represented by an inner static class Entry<K, V>:

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;
}

Each node has:

• key and value fields,
• references to left, right, and parent nodes,
• a color field (either RED or BLACK), required for maintaining balance.

---

2. How the Keys Are Ordered

When you insert a key into a TreeMap, it uses comparison logic to determine where in the tree that key should go.

There are two possible ways keys are compared:

1. Natural ordering – if the key class implements Comparable (e.g., String, Integer, Double).
2. Custom comparator – if you pass a Comparator object to the TreeMap constructor.

Example:

TreeMap<Integer, String> naturalOrder = new TreeMap<>(); // uses natural ordering

TreeMap<Integer, String> customOrder = new TreeMap<>((a, b) -> b - a); // reverse order

---

3. Insertion Logic (How Keys Are Placed in Order)

When you call:

treeMap.put(key, value);

the following happens internally:

1. If the tree is empty, the new entry becomes the root.
2. If not empty, the tree is traversed from the root:
   • Compare the new key with the current node’s key using compareTo() or Comparator.compare().
   • If smaller, move to the left child.
   • If greater, move to the right child.
3. Once the correct leaf position is found, the new node is inserted.
4. The Red-Black Tree rebalances itself if needed to maintain its properties.

This comparison ensures that:

• Left subtree keys < parent key
• Right subtree keys > parent key

Hence, at all times, the tree is sorted by key.

---

4. Red-Black Tree Properties

The Red-Black Tree guarantees balanced height using these properties:

1. Every node is either red or black.
2. The root is always black.
3. Every leaf (null reference) is considered black.
4. If a node is red, both its children must be black (no two consecutive red nodes).
5. Every path from a node to its descendant leaves has the same number of black nodes.

Whenever an insertion or deletion violates these properties, the tree performs rotations and recoloring to rebalance itself.

---

5. Rebalancing and Rotations

After an insertion or deletion:

• The tree checks for violations of red-black properties.
• If violated, it performs left rotation, right rotation, or color flipping.

These operations ensure that the height difference between subtrees remains small, guaranteeing that all operations—get(), put(), and remove()—run in O(log n) time.

For example:

• If you insert a red node under another red node → recolor or rotate.
• If you delete a black node → rebalancing ensures black height remains consistent.

---

6. Retrieving Keys in Sorted Order

Because keys are stored in a balanced BST, an in-order traversal of the tree yields keys in sorted order.

So when you call methods like:

treeMap.keySet();
treeMap.entrySet();
treeMap.values();

or iterate over the map using a for-each loop, the elements are visited in ascending key order by default.

Example:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(5, "B");
map.put(20, "C");

for (Map.Entry<Integer, String> e : map.entrySet()) {
    System.out.println(e.getKey() + " => " + e.getValue());
}

Output:

5 => B
10 => A
20 => C

This happens because TreeMap internally performs an in-order traversal of its Red-Black Tree.

---

7. Custom Ordering Example

If you supply a custom comparator, the order changes accordingly.

Example:

TreeMap<Integer, String> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.put(10, "A");
reverseMap.put(5, "B");
reverseMap.put(20, "C");

System.out.println(reverseMap);

Output:

{20=C, 10=A, 5=B}

Internally, the comparator changes the comparison logic, so the tree structure flips accordingly.

---

8. Performance Analysis

Operation	Average Time Complexity	Description
put()	O(log n)	Inserts a key-value pair, rebalancing if needed
get()	O(log n)	Searches for a key using comparison logic
remove()	O(log n)	Deletes a key, then rebalances the tree
firstKey() / lastKey()	O(log n)	Traverses leftmost/rightmost branch
Iteration	O(n)	In-order traversal of the entire tree

---

9. TreeMap vs HashMap (Ordering Perspective)

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

So, use TreeMap when:

• You need sorted keys.
• You need to quickly access smallest/largest keys.
• You require range queries (like subMap(), headMap(), tailMap()).

---

10. Example: Navigating TreeMap in Order

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(5, "B");
map.put(20, "C");
map.put(15, "D");

System.out.println("First Key: " + map.firstKey());
System.out.println("Last Key: " + map.lastKey());
System.out.println("Keys less than 15: " + map.headMap(15));
System.out.println("Keys >= 10: " + map.tailMap(10));
System.out.println("Keys between 5 and 20: " + map.subMap(5, 20));

Output:

First Key: 5
Last Key: 20
Keys less than 15: {5=B, 10=A}
Keys >= 10: {10=A, 15=D, 20=C}
Keys between 5 and 20: {5=B, 10=A, 15=D}

These methods are efficient because the tree structure allows direct navigation to nodes near the range boundaries.

---

Summary

Concept	Explanation
Underlying Structure	Red-Black Tree (self-balancing BST)
Ordering	Based on natural order or custom comparator
Balancing Mechanism	Maintains height using rotations and recoloring
Traversal Order	In-order (ascending keys)
Performance	O(log n) for insert, delete, and search
Use Case	When you need a sorted map with efficient range lookups