🌳 Mastering Data Structures in Java — Part 8: TreeMap

If HashMap is all about speed, then TreeMap is all about order.
It’s a powerful data structure when you need your data to stay sorted automatically — by keys.

Let’s explore what makes TreeMap unique and when to use it 👇

---

🧠 What Is a TreeMap?

A TreeMap in Java is a sorted map implementation based on a Red-Black Tree (a type of self-balancing binary search tree).

It stores key-value pairs just like a HashMap,
👉 but it keeps the keys in sorted order — either by natural ordering or by a custom comparator you define.

import java.util.TreeMap;

public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> users = new TreeMap<>();

        users.put(3, "Ali");
        users.put(1, "Sara");
        users.put(2, "Omar");

        System.out.println(users);
    }
}

Output:

{1=Sara, 2=Omar, 3=Ali}

Notice how it sorted the keys automatically 🔥

---

⚙️ How It Works Internally

TreeMap uses a Red-Black Tree to store entries.

When you insert a key, it finds its correct position in the tree (based on comparison).

The tree stays balanced to keep operations efficient.

This allows O(log n) time for put(), get(), and remove() operations.

In contrast, HashMap uses hashing and provides average O(1) time, but no order.

---

🔍 Example: Natural Ordering (Strings)

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

grades.put("Omar", 85);
grades.put("Sara", 92);
grades.put("Ali", 78);

System.out.println(grades);

Output:

{Ali=78, Omar=85, Sara=92}


Keys are sorted alphabetically.

---

🧩 Example: Custom Ordering

You can control the sorting logic using a Comparator.

import java.util.*;

public class CustomOrderTreeMap {
    public static void main(String[] args) {
        TreeMap<String, Integer> grades = new TreeMap<>(Comparator.reverseOrder());

        grades.put("Omar", 85);
        grades.put("Sara", 92);
        grades.put("Ali", 78);

        System.out.println(grades);
    }
}

Output:

{Sara=92, Omar=85, Ali=78}


Now it’s in descending order.

---

⚡ Performance Comparison

Operation	HashMap	TreeMap
Insertion	O(1) avg	O(log n)
Search	O(1) avg	O(log n)
Deletion	O(1) avg	O(log n)
Ordering	❌ Unordered	✅ Sorted
Null Keys	✅ Allowed	❌ Not Allowed

So if you don’t need ordering, go with HashMap.
If order matters, TreeMap is the right choice.

---

🌍 Where TreeMap Is Used in Real-World Projects

Leaderboards / Rankings

Sort players by score or performance dynamically.

TreeMap<Integer, String> leaderboard = new TreeMap<>(Comparator.reverseOrder());
leaderboard.put(95, "Sara");
leaderboard.put(87, "Ali");
leaderboard.put(92, "Omar");
System.out.println(leaderboard);

Navigable Structures (like Calendar Apps)

Quickly find the next event or previous event using methods like:

higherKey(), lowerKey(), ceilingKey(), floorKey().

Range Queries

Get sub-maps of data between two keys:

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

System.out.println(map.subMap(3, 7)); // {3=B, 5=C}

Configuration Management

When property keys must be stored in order (for readability or file export).

---

🧰 Common Methods

firstKey()
lastKey()
higherKey(K key)
lowerKey(K key)
subMap(K fromKey, K toKey)
headMap(K toKey)
tailMap(K fromKey)

Example:

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

System.out.println(map.firstKey()); // 1
System.out.println(map.lastKey());  // 3

---

💡 Pro Tips

Use TreeMap when you care about sorted keys.

For custom sorting, always pass a Comparator in the constructor.

If performance is your top priority, prefer HashMap.

Avoid null keys — they’ll throw NullPointerException.

---

🧩 Summary

TreeMap brings order to your mappings — it’s ideal when you need your data to stay sorted and searchable by key.
While it’s slower than HashMap, its power lies in navigation and range operations.

Think of it like a map that sorts itself — perfect for leaderboards, calendars, or any data where order matters.

---