TreeMap

TreeMap is what you reach for when your data needs to stand in a neat, sorted queue instead of lounging in random order 🌳📚 Under the hood, it’s a self-balancing tree that keeps keys in order as you insert them.

---

👉 TreeMap

• Stores key–value pairs
• Keys are sorted automatically
• Backed by a Red-Black Tree

---

🧠 Key Characteristics

• ❌ No null keys (throws exception)
• ✅ Allows null values
• 🔁 Maintains sorted order of keys
• ⏱️ Operations: O(log n)
• 🔄 Not synchronized

---

📦 Basic Example

import java.util.*;

public class Demo {
    public static void main(String[] args) {
        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}

👉 Automatically sorted by key ✔️

---

🔍 How Sorting Works

🔹 1. Natural Ordering (Comparable)

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

👉 Strings sorted alphabetically

---

🔹 2. Custom Ordering (Comparator)

TreeMap<Integer, String> map =
        new TreeMap<>((a, b) -> b - a); // descending

---

🧪 Important Methods

map.firstKey();   // smallest key
map.

lastKey();    // largest key
map.

ceilingKey(2); // ≥ key
map.

floorKey(2);   // ≤ key
map.

higherKey(2);  // >
map.

lowerKey(2);   // <

---

🆚 TreeMap vs HashMap

Feature	TreeMap	HashMap
Order	Sorted	No order
Structure	Tree	Hash table
Time	O(log n)	O(1) avg
Null key	❌ No	✅ Yes

---

⚠️ Important Interview Points

❗ 1. Uses compareTo() or Comparator

• NOT equals() for ordering

---

❗ 2. If compare returns 0 → treated as duplicate

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

put(1,"A");
map.

put(1,"B"); // replaces value

---

❗ 3. Custom Object Example

class Person implements Comparable<Person> {
    int age;

    public Person(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person p) {
        return Integer.compare(this.age, p.age);
    }
}

---

🎯 Real Interview Answer

“TreeMap is a SortedMap implementation that stores key-value pairs in sorted order using a Red-Black tree. It provides O(log n) time complexity for operations and uses compareTo or Comparator for ordering instead of hashCode.”

---

🧠 Mental Model

Think of TreeMap like a leaderboard 🏆 Every entry finds its correct position instantly.

---

🚀 When to Use

✅ When you need:

• Sorted data
• Range queries
• Nearest key lookups

❌ Avoid when:

• You only need fast lookup → use HashMap

---