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.

TreeMap Examples

1. Creating a TreeMap (Natural Sorting by Key)

import java.util.*;

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}
          

2. TreeMap Does NOT Allow Duplicate Keys

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "Java");
        map.put(1, "Selenium");
        System.out.println(map);
    }
}
          

Output

{1=Selenium}
          

3. TreeMap Does NOT Allow null Keys

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        // map.put(null, "X"); // ❌ NullPointerException
        System.out.println("Null key not allowed");
    }
}
          

4. TreeMap Allows Multiple null Values

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, null);
        map.put(2, null);
        System.out.println(map);
    }
}
          

Output

{1=null, 2=null}
          

5. Sorting Keys in Reverse Order

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map =
            new TreeMap<>(Comparator.reverseOrder());
        map.put(1, "A");
        map.put(3, "C");
        map.put(2, "B");
        System.out.println(map);
    }
}
          

Output

{3=C, 2=B, 1=A}
          

6. Custom Sorting Using Comparator

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<String, Integer> map =
            new TreeMap<>((a, b) -> a.length() - b.length());
        map.put("Java", 1);
        map.put("API", 2);
        map.put("Automation", 3);
        System.out.println(map);
    }
}
          

Output

{API=2, Java=1, Automation=3}
          

7. Iterating Using entrySet()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "A");
        map.put(2, "B");

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

8. Iterating Using keySet()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "X");
        map.put(20, "Y");

        for (Integer key : map.keySet()) {
            System.out.println(key);
        }
    }
}
          

9. Iterating Using values()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "Java");
        map.put(2, "API");

        for (String value : map.values()) {
            System.out.println(value);
        }
    }
}
          

10. firstKey() and lastKey()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");

        System.out.println(map.firstKey());
        System.out.println(map.lastKey());
    }
}
          

Output

10
30
          

11. headMap() – Keys Less Than Given Key

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");

        System.out.println(map.headMap(20));
    }
}
          

Output

{10=A}
          

12. tailMap() – Keys Greater Than or Equal

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");

        System.out.println(map.tailMap(20));
    }
}
          

Output

{20=B, 30=C}
          

13. subMap() – Range of Keys

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");
        map.put(40, "D");

        System.out.println(map.subMap(20, 40));
    }
}
          

Output

{20=B, 30=C}
          

14. Navigational Methods (lowerKey, higherKey)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");

        System.out.println(map.lowerKey(20));
        System.out.println(map.higherKey(20));
    }
}
          

Output

10
30
          

15. floorKey() and ceilingKey()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");

        System.out.println(map.floorKey(25));
        System.out.println(map.ceilingKey(25));
    }
}
          

Output

20
30
          

16. pollFirstEntry() and pollLastEntry()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");

        System.out.println(map.pollFirstEntry());
        System.out.println(map.pollLastEntry());
        System.out.println(map);
    }
}
          

Output

10=A
30=C
{20=B}
          

17. Converting HashMap to TreeMap (Sorting)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        HashMap<Integer, String> hashMap = new HashMap<>();
        hashMap.put(3, "C");
        hashMap.put(1, "A");

        TreeMap<Integer, String> treeMap = new TreeMap<>(hashMap);
        System.out.println(treeMap);
    }
}
          

18. Custom Object as Key using Comparable

class User implements Comparable<User> {
    int id;
    User(int id) { this.id = id; }

    public int compareTo(User u) {
        return this.id - u.id;
    }
}

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<User, String> map = new TreeMap<>();
        map.put(new User(2), "B");
        map.put(new User(1), "A");
        System.out.println(map.size());
    }
}
          

Output

2
          

19. Performance Note (Concept)

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

Explanation

• Backed by Red-Black Tree
• Time complexity: O(log n)
• Slower than HashMap, but sorted

20. Interview Summary – TreeMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(2, "Sorted");
        map.put(1, "ByKey");
        System.out.println(map);
    }
}
          

Key Points

• Sorted by keys
• No null keys
• Duplicate keys overwrite values
• Supports navigation methods
• Uses Red-Black Tree