TreeMap

TreeMap is an implementation of the Map interface that stores key-value pairs in sorted order. It is backed by a self-balancing Red-Black Tree, providing ordered traversal and logarithmic-time operations. This is a high-frequency interview topic, often compared with HashMap and LinkedHashMap.

What Is TreeMap?

• Sorted map implementation
• Stores key-value pairs
• Keys are stored in natural or custom order
• Does not allow null keys
• Allows multiple null values
• Part of java.util package

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

Position in Map Hierarchy

Map
 └── SortedMap
       └── NavigableMap
             └── TreeMap
          

How TreeMap Works Internally (Interview Favorite)

• Backed by a Red-Black Tree
• Keys are compared using:
  • Comparable (natural ordering)
  • Comparator (custom ordering)
• Maintains sorted order at all times

Key Characteristics of TreeMap

• Sorted by keys, not values
• No duplicate keys
• Slower than HashMap / LinkedHashMap
• Not synchronized (not thread-safe)
• Rich navigation APIs

Creating a TreeMap

1️⃣ Natural Ordering (Comparable)

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Java");
map.put(1, "Python");
map.put(2, "C++");
System.out.println(map); // {1=Python, 2=C++, 3=Java}
          

2️⃣ Custom Ordering (Comparator)

TreeMap<Integer, String> map =
    new TreeMap<>((a, b) -> b - a);
map.put(1, "Java");
map.put(3, "Python");
map.put(2, "C++");
System.out.println(map); // {3=Python, 2=C++, 1=Java}
          

✔ Descending order

Important TreeMap Methods (NavigableMap)

map.firstKey();     // smallest key
map.lastKey();      // largest key
map.lowerKey(2);    // < 2
map.higherKey(2);   // > 2
map.floorKey(2);    // <= 2
map.ceilingKey(2);  // >= 2
          

Duplicate Key Behavior

map.put(1, "Java");
map.put(1, "Python");
System.out.println(map); // {1=Python}
          

✔ Old value replaced

✔ No exception thrown

null Handling (Very Important)

map.put(null, "Java"); // ❌ NullPointerException
          

❌ null keys not allowed

✔ null values allowed

Performance Complexity

TreeMap vs HashMap vs LinkedHashMap

When to Use TreeMap

• Sorted keys are required
• Range queries are needed
• Ordered traversal is mandatory
• Duplicate removal + sorting

When NOT to Use TreeMap

• Maximum performance required
• null keys needed
• Order does not matter
• Heavy write operations

Common Beginner Mistakes

• Adding null keys
• Forgetting Comparable / Comparator
• Expecting insertion order
• Using TreeMap unnecessarily

Interview-Ready Answers

Short Answer

TreeMap is a Map implementation that stores keys in sorted order.

Detailed Answer

In Java, TreeMap implements the NavigableMap interface and stores key-value pairs in sorted order using a Red-Black Tree. It does not allow null keys, provides logarithmic-time operations, and supports advanced navigation methods.

Key Takeaway

Use TreeMap when you need sorted keys with rich navigation support. Accept the performance trade-off in exchange for automatic ordering and range queries.