Java Notes

TreeMap in Java

Complete guide to Java TreeMap — Red-Black tree implementation, sorted map operations, NavigableMap methods, custom comparators, range queries, and performance analysis.

What is TreeMap?

java.util.TreeMap is a Red-Black tree based implementation of NavigableMap. It stores key-value pairs in sorted order by keys, either using the keys' natural ordering (Comparable) or a custom Comparator.

java example

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, Serializable

Key characteristics:

Keys are always sorted (natural order or custom comparator)
O(log n) for get, put, remove, containsKey
No null keys (throws NullPointerException)
Not synchronized (not thread-safe)
Implements NavigableMap — provides ceiling, floor, higher, lower operations

Time Complexity

Operation	Time Complexity
-----------	:-:
`put(key, value)`	O(log n)
`get(key)`	O(log n)
`remove(key)`	O(log n)
`containsKey(key)`	O(log n)
`containsValue(value)`	O(n)
`firstKey()` / `lastKey()`	O(log n)
`ceilingKey()` / `floorKey()`	O(log n)
`subMap()` / `headMap()` / `tailMap()`	O(log n)
Iteration (full)	O(n)

Note: Unlike HashMap's O(1), TreeMap guarantees O(log n) — no best-case/worst-case variation.

Basic Usage

java example

import java.util.*;

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

        // Elements are sorted by key automatically
        scores.put("Charlie", 85);
        scores.put("Alice", 92);
        scores.put("Eve", 78);
        scores.put("Bob", 88);
        scores.put("Diana", 95);

        // Iterates in SORTED order by key
        System.out.println("Sorted by name:");
        scores.forEach((name, score) ->
            System.out.println("  " + name + ": " + score));

        // First and last
        System.out.println("\nFirst: " + scores.firstKey());    // Alice
        System.out.println("Last: " + scores.lastKey());         // Eve
        System.out.println("First entry: " + scores.firstEntry()); // Alice=92
        System.out.println("Last entry: " + scores.lastEntry());   // Eve=78
    }
}

Output:

Alice	92
Bob	88
Charlie	85
Diana	95
Eve	78
First	Alice
Last	Eve

NavigableMap Methods

TreeMap implements NavigableMap, providing powerful navigation operations:

Ceiling, Floor, Higher, Lower

java example

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");

// ceilingKey — smallest key >= given key
System.out.println(map.ceilingKey(25));  // 30
System.out.println(map.ceilingKey(30));  // 30 (inclusive)

// floorKey — largest key <= given key
System.out.println(map.floorKey(25));    // 20
System.out.println(map.floorKey(20));    // 20 (inclusive)

// higherKey — smallest key STRICTLY > given key
System.out.println(map.higherKey(30));   // 40

// lowerKey — largest key STRICTLY < given key
System.out.println(map.lowerKey(30));    // 20

Polling (Remove First/Last)

java example

// pollFirstEntry — removes and returns the entry with lowest key
Map.Entry<Integer, String> first = map.pollFirstEntry();  // 10=Ten (removed!)

// pollLastEntry — removes and returns the entry with highest key
Map.Entry<Integer, String> last = map.pollLastEntry();    // 50=Fifty (removed!)

SubMap, HeadMap, TailMap (Range Views)

Example

TreeMap<Integer, String> map = new TreeMap<>(); for (int i = 1; i <= 10; i++) map.put(i * 10, "Val" + i); // {10=Val1, 20=Val2, 30=Val3, ..., 100=Val10} // subMap(fromKey, inclusive, toKey, inclusive) SortedMap<Integer, String> sub = map.subMap(30, true, 70, true); System.out.println(sub); // {30=Val3, 40=Val4, 50=Val5, 60=Val6, 70=Val7} // headMap(toKey, inclusive) — all entries < toKey SortedMap<Integer, String> head = map.headMap(40, false); System.out.println(head); // {10=Val1, 20=Val2, 30=Val3} // tailMap(fromKey, inclusive) — all entries >= fromKey SortedMap<Integer, String> tail = map.tailMap(80, true); System.out.println(tail); // {80=Val8, 90=Val9, 100=Val10}

Important: These are views, not copies. Modifications reflect in the original map:

java example

sub.put(55, "New");
System.out.println(map.get(55));  // "New" — added to original map!

Descending Order

java example

// Reverse view
NavigableMap<Integer, String> descending = map.descendingMap();
System.out.println(descending.firstKey());  // 100 (highest becomes first)

// Descending key set
NavigableSet<Integer> descKeys = map.descendingKeySet();

Custom Comparator

Example

// Sort by key in reverse order TreeMap<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder()); reverseMap.put("Alice", 1); reverseMap.put("Bob", 2); reverseMap.put("Charlie", 3); System.out.println(reverseMap.keySet()); // [Charlie, Bob, Alice] // Sort by key length, then alphabetically TreeMap<String, Integer> byLength = new TreeMap<>( Comparator.comparingInt(String::length) .thenComparing(Comparator.naturalOrder()) ); byLength.put("Bob", 1); byLength.put("Alice", 2); byLength.put("Jo", 3); byLength.put("Eve", 4); System.out.println(byLength.keySet()); // [Jo, Bob, Eve, Alice] // Case-insensitive sorting TreeMap<String, Integer> caseInsensitive = new TreeMap<>(String.CASE_INSENSITIVE_ORDER); caseInsensitive.put("banana", 1); caseInsensitive.put("Apple", 2); caseInsensitive.put("CHERRY", 3); System.out.println(caseInsensitive.keySet()); // [Apple, banana, CHERRY]

Practical Use Cases

1. Finding Entries in a Range

java example

// Stock prices at different times
TreeMap<LocalTime, Double> prices = new TreeMap<>();
prices.put(LocalTime.of(9, 30), 150.25);
prices.put(LocalTime.of(10, 0), 151.50);
prices.put(LocalTime.of(10, 30), 149.75);
prices.put(LocalTime.of(11, 0), 152.00);
prices.put(LocalTime.of(11, 30), 153.25);

// Get prices between 10:00 and 11:00
Map<LocalTime, Double> morning = prices.subMap(
    LocalTime.of(10, 0), true,
    LocalTime.of(11, 0), true
);
System.out.println(morning);

2. Event Scheduling

java example

TreeMap<LocalDateTime, String> events = new TreeMap<>();
events.put(LocalDateTime.of(2024, 3, 15, 9, 0), "Meeting");
events.put(LocalDateTime.of(2024, 3, 15, 12, 0), "Lunch");
events.put(LocalDateTime.of(2024, 3, 15, 14, 0), "Presentation");

// What's the next event after now?
Map.Entry<LocalDateTime, String> nextEvent = events.higherEntry(LocalDateTime.now());

3. Counting Elements in Ranges

java example

TreeMap<Integer, Integer> histogram = new TreeMap<>();
int[] data = {12, 25, 37, 48, 51, 63, 72, 85, 91, 99};
for (int val : data) {
    int bucket = (val / 10) * 10;  // Round down to nearest 10
    histogram.merge(bucket, 1, Integer::sum);
}
// {10=1, 20=1, 30=1, 40=1, 50=1, 60=1, 70=1, 80=1, 90=2}

4. Implementing a Sorted Leaderboard

Example

// Use reverse order for descending scores TreeMap<Integer, List<String>> leaderboard = new TreeMap<>(Comparator.reverseOrder()); leaderboard.computeIfAbsent(95, k -> new ArrayList<>()).add("Alice"); leaderboard.computeIfAbsent(88, k -> new ArrayList<>()).add("Bob"); leaderboard.computeIfAbsent(95, k -> new ArrayList<>()).add("Charlie"); leaderboard.computeIfAbsent(72, k -> new ArrayList<>()).add("Diana"); // Top 3 scores int rank = 1; for (Map.Entry<Integer, List<String>> entry : leaderboard.entrySet()) { for (String name : entry.getValue()) { System.out.println("#" + rank + " " + name + " (" + entry.getKey() + ")"); rank++; if (rank > 3) break; } if (rank > 3) break; }

TreeMap vs HashMap vs LinkedHashMap

Feature	HashMap	LinkedHashMap	TreeMap
Ordering	None	Insertion/access	Sorted by key
get/put	O(1)	O(1)	O(log n)
Null keys	One	One	❌ None
Null values	Yes	Yes	Yes
NavigableMap	No	No	Yes
Range queries	No	No	Yes
Memory	Low	Medium	Highest
Best for	General lookup	Order preservation	Sorted data, ranges

Thread Safety

TreeMap is NOT thread-safe:

java example

// Option 1: Synchronized wrapper
SortedMap<String, Integer> syncMap = Collections.synchronizedSortedMap(new TreeMap<>());

// Option 2: ConcurrentSkipListMap (concurrent sorted map)
NavigableMap<String, Integer> concurrentSorted = new ConcurrentSkipListMap<>();
// O(log n) operations with high concurrency support

Common Mistakes

1. Null Keys

java example

TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1);  // NullPointerException! (can't compare null)

2. Inconsistent Comparator with equals()

java example

// If comparator says two keys are equal (compare returns 0),
// TreeMap treats them as the SAME key!
TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("Hello", 1);
map.put("HELLO", 2);  // OVERWRITES! Because comparator says they're equal
System.out.println(map.size());  // 1!

3. Modifying Keys After Insertion

java example

// If you use mutable objects as keys and modify them,
// the tree structure becomes corrupted
// ALWAYS use immutable keys

4. Assuming O(1) Performance

java example

// TreeMap is O(log n), not O(1)!
// For 1 million entries: log₂(1,000,000) ≈ 20 comparisons per operation
// HashMap would be ~1 (constant)

Interview Questions

Q1: How does TreeMap maintain sorted order?

A: TreeMap uses a Red-Black tree (self-balancing BST). New entries are inserted in BST order, and the tree rebalances using rotations and recoloring to maintain O(log n) height.

Q2: What is the difference between HashMap and TreeMap?

A: HashMap uses hashing (O(1), unordered). TreeMap uses a Red-Black tree (O(log n), sorted by keys). TreeMap also implements NavigableMap for range queries.

Q3: Can TreeMap have null keys?

A: No. TreeMap needs to compare keys, and comparing with null throws NullPointerException (unless you provide a custom Comparator that handles null, but this is not recommended).

Q4: What are ceiling, floor, higher, and lower in TreeMap?

A: ceiling(k): smallest key ≥ k. floor(k): largest key ≤ k. higher(k): smallest key > k. lower(k): largest key < k.

Q5: What is the time complexity of subMap()?

A: Creating the view is O(log n). Iterating the submap is O(k + log n) where k is the number of entries in the range.

Q6: How does TreeMap handle duplicate keys?

A: It doesn't store duplicates. If you put with an existing key, the value is replaced (same as HashMap).

Q7: What is ConcurrentSkipListMap and how does it relate to TreeMap?

A: ConcurrentSkipListMap is the concurrent equivalent of TreeMap. It uses a skip list (not Red-Black tree) to provide O(log n) sorted map operations with high concurrency.

Q8: Why doesn't TreeMap allow null keys?

A: TreeMap uses compareTo() or Comparator.compare() to determine key ordering and placement. Null cannot be compared — calling null.compareTo(something) throws NullPointerException. HashMap allows one null key because it handles null specially (always maps to bucket 0).

Q9: What is the time complexity of TreeMap operations?

A: All basic operations — get(), put(), remove(), containsKey() — are O(log n) because TreeMap uses a Red-Black tree. Navigation methods like firstKey(), lastKey(), ceilingKey(), floorKey() are also O(log n).

Q10: How does TreeMap maintain sorted order?

A: TreeMap uses a self-balancing Red-Black tree. After every insertion or deletion, the tree rebalances through rotations and recoloring to ensure the tree height stays O(log n). This guarantees consistent O(log n) performance regardless of insertion order.

Q11: When would you use TreeMap over HashMap?

A: Use TreeMap when you need: (1) sorted iteration by keys, (2) range queries (subMap, headMap, tailMap), (3) navigation methods (ceiling, floor, higher, lower), (4) first/last key access. Use HashMap for all other cases — it's O(1) vs O(log n).

Q12: Can you use a custom Comparator with TreeMap?

A: Yes! Pass a Comparator to the constructor: new TreeMap<>(Comparator.reverseOrder()) or new TreeMap<>((a, b) -> b.length() - a.length()). Custom Comparator overrides the keys' natural ordering (Comparable). All keys must be mutually comparable by the provided Comparator.

Summary

Aspect	TreeMap
Structure	Red-Black tree
Time complexity	O(log n) for all key operations
Ordering	Sorted by key (natural or comparator)
Null keys	Not allowed
Best for	Sorted data, range queries, navigation
Interfaces	NavigableMap, SortedMap
Thread-safe	No (use ConcurrentSkipListMap)
Key feature	ceiling/floor/subMap/headMap/tailMap

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for TreeMap in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, collections, framework, map

Continue learning this concept

PreviousLinkedHashMap in Java NextArrayDeque in Java

Java Notes

TreeMap in Java

Complete guide to Java TreeMap — Red-Black tree implementation, sorted map operations, NavigableMap methods, custom comparators, range queries, and performance analysis.

What is TreeMap?

java example

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, Serializable

Key characteristics:

Keys are always sorted (natural order or custom comparator)
O(log n) for get, put, remove, containsKey
No null keys (throws NullPointerException)
Not synchronized (not thread-safe)
Implements NavigableMap — provides ceiling, floor, higher, lower operations

Time Complexity

Operation	Time Complexity
-----------	:-:
`put(key, value)`	O(log n)
`get(key)`	O(log n)
`remove(key)`	O(log n)
`containsKey(key)`	O(log n)
`containsValue(value)`	O(n)
`firstKey()` / `lastKey()`	O(log n)
`ceilingKey()` / `floorKey()`	O(log n)
`subMap()` / `headMap()` / `tailMap()`	O(log n)
Iteration (full)	O(n)

Note: Unlike HashMap's O(1), TreeMap guarantees O(log n) — no best-case/worst-case variation.

Basic Usage

java example

import java.util.*;

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

        // Elements are sorted by key automatically
        scores.put("Charlie", 85);
        scores.put("Alice", 92);
        scores.put("Eve", 78);
        scores.put("Bob", 88);
        scores.put("Diana", 95);

        // Iterates in SORTED order by key
        System.out.println("Sorted by name:");
        scores.forEach((name, score) ->
            System.out.println("  " + name + ": " + score));

        // First and last
        System.out.println("\nFirst: " + scores.firstKey());    // Alice
        System.out.println("Last: " + scores.lastKey());         // Eve
        System.out.println("First entry: " + scores.firstEntry()); // Alice=92
        System.out.println("Last entry: " + scores.lastEntry());   // Eve=78
    }
}

Output:

Alice	92
Bob	88
Charlie	85
Diana	95
Eve	78
First	Alice
Last	Eve

NavigableMap Methods

TreeMap implements NavigableMap, providing powerful navigation operations:

Ceiling, Floor, Higher, Lower

java example

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");

// ceilingKey — smallest key >= given key
System.out.println(map.ceilingKey(25));  // 30
System.out.println(map.ceilingKey(30));  // 30 (inclusive)

// floorKey — largest key <= given key
System.out.println(map.floorKey(25));    // 20
System.out.println(map.floorKey(20));    // 20 (inclusive)

// higherKey — smallest key STRICTLY > given key
System.out.println(map.higherKey(30));   // 40

// lowerKey — largest key STRICTLY < given key
System.out.println(map.lowerKey(30));    // 20

Polling (Remove First/Last)

java example

// pollFirstEntry — removes and returns the entry with lowest key
Map.Entry<Integer, String> first = map.pollFirstEntry();  // 10=Ten (removed!)

// pollLastEntry — removes and returns the entry with highest key
Map.Entry<Integer, String> last = map.pollLastEntry();    // 50=Fifty (removed!)

SubMap, HeadMap, TailMap (Range Views)

Example

Important: These are views, not copies. Modifications reflect in the original map:

java example

sub.put(55, "New");
System.out.println(map.get(55));  // "New" — added to original map!

Descending Order

java example

// Reverse view
NavigableMap<Integer, String> descending = map.descendingMap();
System.out.println(descending.firstKey());  // 100 (highest becomes first)

// Descending key set
NavigableSet<Integer> descKeys = map.descendingKeySet();

Custom Comparator

Example

Practical Use Cases

1. Finding Entries in a Range

java example

// Stock prices at different times
TreeMap<LocalTime, Double> prices = new TreeMap<>();
prices.put(LocalTime.of(9, 30), 150.25);
prices.put(LocalTime.of(10, 0), 151.50);
prices.put(LocalTime.of(10, 30), 149.75);
prices.put(LocalTime.of(11, 0), 152.00);
prices.put(LocalTime.of(11, 30), 153.25);

// Get prices between 10:00 and 11:00
Map<LocalTime, Double> morning = prices.subMap(
    LocalTime.of(10, 0), true,
    LocalTime.of(11, 0), true
);
System.out.println(morning);

2. Event Scheduling

java example

TreeMap<LocalDateTime, String> events = new TreeMap<>();
events.put(LocalDateTime.of(2024, 3, 15, 9, 0), "Meeting");
events.put(LocalDateTime.of(2024, 3, 15, 12, 0), "Lunch");
events.put(LocalDateTime.of(2024, 3, 15, 14, 0), "Presentation");

// What's the next event after now?
Map.Entry<LocalDateTime, String> nextEvent = events.higherEntry(LocalDateTime.now());

3. Counting Elements in Ranges

java example

TreeMap<Integer, Integer> histogram = new TreeMap<>();
int[] data = {12, 25, 37, 48, 51, 63, 72, 85, 91, 99};
for (int val : data) {
    int bucket = (val / 10) * 10;  // Round down to nearest 10
    histogram.merge(bucket, 1, Integer::sum);
}
// {10=1, 20=1, 30=1, 40=1, 50=1, 60=1, 70=1, 80=1, 90=2}

4. Implementing a Sorted Leaderboard

Example

TreeMap vs HashMap vs LinkedHashMap

Feature	HashMap	LinkedHashMap	TreeMap
Ordering	None	Insertion/access	Sorted by key
get/put	O(1)	O(1)	O(log n)
Null keys	One	One	❌ None
Null values	Yes	Yes	Yes
NavigableMap	No	No	Yes
Range queries	No	No	Yes
Memory	Low	Medium	Highest
Best for	General lookup	Order preservation	Sorted data, ranges

Thread Safety

TreeMap is NOT thread-safe:

java example

// Option 1: Synchronized wrapper
SortedMap<String, Integer> syncMap = Collections.synchronizedSortedMap(new TreeMap<>());

// Option 2: ConcurrentSkipListMap (concurrent sorted map)
NavigableMap<String, Integer> concurrentSorted = new ConcurrentSkipListMap<>();
// O(log n) operations with high concurrency support

Common Mistakes

1. Null Keys

java example

TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1);  // NullPointerException! (can't compare null)

2. Inconsistent Comparator with equals()

java example

// If comparator says two keys are equal (compare returns 0),
// TreeMap treats them as the SAME key!
TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("Hello", 1);
map.put("HELLO", 2);  // OVERWRITES! Because comparator says they're equal
System.out.println(map.size());  // 1!

3. Modifying Keys After Insertion

java example

// If you use mutable objects as keys and modify them,
// the tree structure becomes corrupted
// ALWAYS use immutable keys

4. Assuming O(1) Performance

java example

// TreeMap is O(log n), not O(1)!
// For 1 million entries: log₂(1,000,000) ≈ 20 comparisons per operation
// HashMap would be ~1 (constant)

Interview Questions

Q1: How does TreeMap maintain sorted order?

A: TreeMap uses a Red-Black tree (self-balancing BST). New entries are inserted in BST order, and the tree rebalances using rotations and recoloring to maintain O(log n) height.

Q2: What is the difference between HashMap and TreeMap?

A: HashMap uses hashing (O(1), unordered). TreeMap uses a Red-Black tree (O(log n), sorted by keys). TreeMap also implements NavigableMap for range queries.

Q3: Can TreeMap have null keys?

A: No. TreeMap needs to compare keys, and comparing with null throws NullPointerException (unless you provide a custom Comparator that handles null, but this is not recommended).

Q4: What are ceiling, floor, higher, and lower in TreeMap?

A: ceiling(k): smallest key ≥ k. floor(k): largest key ≤ k. higher(k): smallest key > k. lower(k): largest key < k.

Q5: What is the time complexity of subMap()?

A: Creating the view is O(log n). Iterating the submap is O(k + log n) where k is the number of entries in the range.

Q6: How does TreeMap handle duplicate keys?

A: It doesn't store duplicates. If you put with an existing key, the value is replaced (same as HashMap).

Q7: What is ConcurrentSkipListMap and how does it relate to TreeMap?

A: ConcurrentSkipListMap is the concurrent equivalent of TreeMap. It uses a skip list (not Red-Black tree) to provide O(log n) sorted map operations with high concurrency.

Q8: Why doesn't TreeMap allow null keys?

Q9: What is the time complexity of TreeMap operations?

Q10: How does TreeMap maintain sorted order?

Q11: When would you use TreeMap over HashMap?

Q12: Can you use a custom Comparator with TreeMap?

Summary

Aspect	TreeMap
Structure	Red-Black tree
Time complexity	O(log n) for all key operations
Ordering	Sorted by key (natural or comparator)
Null keys	Not allowed
Best for	Sorted data, range queries, navigation
Interfaces	NavigableMap, SortedMap
Thread-safe	No (use ConcurrentSkipListMap)
Key feature	ceiling/floor/subMap/headMap/tailMap

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for TreeMap in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, collections, framework, map

Continue learning this concept

PreviousLinkedHashMap in Java NextArrayDeque in Java