TreeMap
Imagine an application storing employee records using employee IDs as keys. You want fast key-based access, but you also need the keys to remain sorted automatically so that the records can be processed from the smallest ID to the largest.
This is where TreeMap becomes useful. TreeMap is a Map implementation that stores key-value mappings according to the sorted order of its keys. The ordering can come from the key's natural ordering or from a Comparator supplied when the TreeMap is created.
Core Idea: TreeMap stores unique keys in sorted order and provides efficient navigation operations such as lowerKey(), floorKey(), ceilingKey(), and higherKey().
Why Does TreeMap Exist?
Suppose you receive employee records in an arbitrary order.
103 - Priya 101 - Bibhu 104 - Ankit 102 - Rahul
With a normal HashMap, you cannot rely on iteration order. With LinkedHashMap, you can preserve insertion order. But if the requirement is to keep the keys sorted automatically, TreeMap is a better fit.
Map<Integer, String> employees =
new TreeMap<>();
employees.put(103, "Priya");
employees.put(101, "Bibhu");
employees.put(104, "Ankit");
employees.put(102, "Rahul");
System.out.println(employees);
The entries are maintained according to the sorted order of their keys.
Simple analogy: Think of TreeMap as a filing cabinet where every folder has a unique key, and the cabinet automatically keeps those keys in sorted order.
TreeMap Hierarchy
TreeMap implements the NavigableMap interface, which extends SortedMap and Map.
Map
|
+-- SortedMap
|
+-- NavigableMap
|
+-- TreeMap
This hierarchy explains why TreeMap provides both normal Map operations and sorted navigation features.
Creating a TreeMap
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Map<Integer, String> employees =
new TreeMap<>();
employees.put(103, "Priya");
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
System.out.println(employees);
}
}
The keys are maintained according to their natural ordering because no Comparator was supplied.
Keys Are Unique
Like every Map implementation, TreeMap allows only one mapping for each key.
Map<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
employees.put(101, "Bibhu Kumar");
System.out.println(
employees.get(101)
);
The second put() replaces the existing value associated with key 101.
Remember: TreeMap sorts keys, not values. Values can be duplicated and have no automatic ordering relationship.
Duplicate Values
Different keys can map to the same value.
Map<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Developer");
employees.put(102, "Developer");
employees.put(103, "Tester");
System.out.println(employees);
The keys remain unique while duplicate values are perfectly valid.
Natural Ordering
When a TreeMap is created without a Comparator, it uses the natural ordering of its keys.
TreeMap<Integer, String> numbers =
new TreeMap<>();
numbers.put(50, "Fifty");
numbers.put(10, "Ten");
numbers.put(30, "Thirty");
numbers.put(20, "Twenty");
System.out.println(numbers);
The integer keys are maintained in ascending numerical order.
For String keys, the natural ordering is based on their natural lexicographical ordering.
TreeMap<String, Integer> scores =
new TreeMap<>();
scores.put("Java", 90);
scores.put("CSharp", 85);
scores.put("Python", 88);
System.out.println(scores);
Important: TreeMap's ordering applies to keys. The values remain associated with their keys but are not automatically sorted.
Using a Comparator
Natural ordering is not always appropriate. TreeMap allows you to define a custom key ordering with a Comparator.
TreeMap<Integer, String> employees =
new TreeMap<>(
Comparator.reverseOrder()
);
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
System.out.println(employees);
The keys are now maintained in descending order.
Custom Comparator Example
You can also define a Comparator explicitly.
TreeMap<String, Integer> scores =
new TreeMap<>(
(a, b) -> b.compareTo(a)
);
scores.put("Java", 90);
scores.put("Python", 88);
scores.put("SQL", 92);
System.out.println(scores);
The Comparator determines how the keys are ordered inside the TreeMap.
Design Insight: The Comparator in TreeMap controls both key ordering and the comparison used to determine whether two keys are equivalent for Map purposes.
Getting a Value
TreeMap supports the standard Map get() operation.
Map<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
String name =
employees.get(101);
System.out.println(name);
The value associated with key 101 is returned.
containsKey()
Map<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
if (employees.containsKey(101)) {
System.out.println(
"Employee exists"
);
}
containsKey() checks whether a key exists in the map.
containsValue()
Map<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
if (employees.containsValue("Rahul")) {
System.out.println(
"Employee found"
);
}
Value lookup generally requires examining multiple entries, so it does not receive the same logarithmic search advantage as key-based operations.
Removing a Mapping
Map<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.remove(101);
System.out.println(employees);
remove() deletes the mapping associated with the specified key.
TreeMap Performance
| Operation | Typical Complexity | Purpose |
|---|---|---|
| put() | O(log n) | Add or update a key-value mapping while maintaining key order. |
| get() | O(log n) | Retrieve a value using a key. |
| containsKey() | O(log n) | Search for a key. |
| remove() | O(log n) | Remove a mapping by key. |
| containsValue() | O(n) | Search through values. |
| Iteration | O(n) | Traverse entries in sorted key order. |
TreeMap generally provides logarithmic-time key-based operations because it uses a balanced tree structure.
firstKey() and lastKey()
TreeMap makes it easy to access the smallest and largest keys.
TreeMap<Integer, String> employees =
new TreeMap<>();
employees.put(103, "Priya");
employees.put(101, "Bibhu");
employees.put(104, "Ankit");
employees.put(102, "Rahul");
System.out.println(
employees.firstKey()
);
System.out.println(
employees.lastKey()
);
firstKey() returns the smallest key, while lastKey() returns the largest key according to the map's ordering.
firstEntry() and lastEntry()
Sometimes you need both the key and value rather than only the key.
Map.Entry<Integer, String> first =
employees.firstEntry();
Map.Entry<Integer, String> last =
employees.lastEntry();
System.out.println(first);
System.out.println(last);
These methods return the entries associated with the smallest and largest keys.
pollFirstEntry() and pollLastEntry()
TreeMap also allows you to remove and return the first or last entry.
TreeMap<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
System.out.println(
employees.pollFirstEntry()
);
System.out.println(
employees.pollLastEntry()
);
System.out.println(employees);
pollFirstEntry() removes the entry with the smallest key, while pollLastEntry() removes the entry with the largest key.
lowerKey(), floorKey(), ceilingKey(), and higherKey()
These methods make TreeMap particularly powerful for navigation around a target key.
| Method | Meaning |
|---|---|
| lowerKey(key) | Greatest key strictly less than the specified key. |
| floorKey(key) | Greatest key less than or equal to the specified key. |
| ceilingKey(key) | Smallest key greater than or equal to the specified key. |
| higherKey(key) | Smallest key strictly greater than the specified key. |
TreeMap<Integer, String> employees =
new TreeMap<>();
employees.put(100, "A");
employees.put(200, "B");
employees.put(300, "C");
employees.put(400, "D");
int target = 250;
System.out.println(
employees.lowerKey(target)
);
System.out.println(
employees.floorKey(target)
);
System.out.println(
employees.ceilingKey(target)
);
System.out.println(
employees.higherKey(target)
);
For a target of 250, lowerKey() and floorKey() return 200, while ceilingKey() and higherKey() return 300.
Memory Trick: lower and higher exclude the target. floor and ceiling can include the target.
lowerEntry(), floorEntry(), ceilingEntry(), and higherEntry()
If you need the complete key-value mapping instead of just the key, TreeMap provides corresponding Entry methods.
System.out.println(
employees.lowerEntry(250)
);
System.out.println(
employees.floorEntry(250)
);
System.out.println(
employees.ceilingEntry(250)
);
System.out.println(
employees.higherEntry(250)
);
These methods follow the same boundary rules while returning Map.Entry objects.
Descending Map
TreeMap can provide a reverse-order view through descendingMap().
TreeMap<Integer, String> employees =
new TreeMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
NavigableMap<Integer, String> descending =
employees.descendingMap();
System.out.println(descending);
The returned view presents the same mappings in descending key order.
Descending Key Map
If only the keys are relevant, you can obtain a descending key view.
NavigableSet<Integer> keys =
employees.descendingKeySet();
System.out.println(keys);
This is useful when you need to process keys from largest to smallest.
headMap()
TreeMap supports range views that contain mappings below a specified key.
TreeMap<Integer, String> employees =
new TreeMap<>();
employees.put(100, "A");
employees.put(200, "B");
employees.put(300, "C");
employees.put(400, "D");
SortedMap<Integer, String> result =
employees.headMap(300);
System.out.println(result);
The traditional headMap(key) view contains keys strictly less than the specified key.
tailMap()
SortedMap<Integer, String> result =
employees.tailMap(300);
System.out.println(result);
The traditional tailMap(key) view contains keys greater than or equal to the specified key.
subMap()
SortedMap<Integer, String> result =
employees.subMap(200, 400);
System.out.println(result);
The traditional subMap(from, to) view includes the lower boundary and excludes the upper boundary.
Boundary Rule: Traditional SortedMap range methods use an inclusive lower bound and an exclusive upper bound.
Inclusive and Exclusive Range Control
NavigableMap provides overloaded range methods that let you explicitly control whether each boundary is included.
NavigableMap<Integer, String> result =
employees.subMap(
200,
true,
400,
true
);
System.out.println(result);
Both 200 and 400 are included because both boundary flags are true.
| Method | Purpose |
|---|---|
| headMap(key) | Keys strictly less than the specified key. |
| headMap(key, inclusive) | Keys less than the key, optionally including the key. |
| tailMap(key) | Keys greater than or equal to the specified key. |
| tailMap(key, inclusive) | Keys greater than the key, optionally including the key. |
| subMap(from, to) | Range with lower inclusive and upper exclusive boundaries. |
| subMap(from, fromInclusive, to, toInclusive) | Range with explicit boundary control. |
TreeMap and Custom Keys
TreeMap can store custom objects as keys, but those keys must have a meaningful ordering.
You can define the natural ordering with Comparable.
class Employee
implements Comparable<Employee> {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int compareTo(Employee other) {
return Integer.compare(
this.id,
other.id
);
}
@Override
public String toString() {
return id + " - " + name;
}
}
Now Employee objects can be used as TreeMap keys because compareTo() defines their natural ordering.
TreeMap<Employee, String> departments =
new TreeMap<>();
departments.put(
new Employee(103, "Priya"),
"Testing"
);
departments.put(
new Employee(101, "Bibhu"),
"Backend"
);
departments.put(
new Employee(102, "Rahul"),
"Frontend"
);
System.out.println(departments);
The keys are maintained according to the Employee comparison rule.
Using Comparator for Custom Keys
Instead of forcing Employee to have one natural ordering, you can define the ordering externally.
TreeMap<Employee, String> departments =
new TreeMap<>(
Comparator.comparing(
Employee::getName
)
);
This approach allows different TreeMaps to order the same domain type using different criteria.
TreeMap and Key Equality
TreeMap determines key equivalence using its ordering mechanism. If compareTo() or compare() returns zero, TreeMap treats the keys as equivalent for Map purposes.
TreeMap<String, Integer> scores =
new TreeMap<>(
String.CASE_INSENSITIVE_ORDER
);
scores.put("Java", 90);
scores.put("java", 95);
System.out.println(
scores.size()
);
The Comparator considers Java and java equivalent, so the second put() replaces the first mapping.
Critical Rule: For TreeMap, compareTo() or Comparator comparison returning zero means the keys are treated as the same key for Map purposes, even if equals() would say otherwise.
Comparable vs Comparator in TreeMap
| Aspect | Comparable | Comparator |
|---|---|---|
| Method | compareTo() | compare() |
| Ordering location | Inside the class | Outside the class |
| Main purpose | Natural ordering | Custom or alternative ordering |
| Multiple ordering strategies | Usually one natural ordering | Multiple strategies possible |
| TreeMap support | Used when no Comparator is supplied | Supplied during TreeMap creation |
Null Keys
A TreeMap using natural ordering generally does not support a null key because null cannot be naturally compared with ordinary keys.
TreeMap<Integer, String> employees =
new TreeMap<>();
// Avoid this with natural ordering.
// employees.put(null, "Unknown");
A custom Comparator that explicitly handles null can change the behavior, but using null as a sorted key should be deliberate and justified.
Null Values
TreeMap allows null values because values are not involved in the key-ordering mechanism.
TreeMap<Integer, String> employees =
new TreeMap<>();
employees.put(101, null);
employees.put(102, null);
System.out.println(employees);
The keys still determine the ordering, while the values may be null.
TreeMap vs HashMap
| Feature | HashMap | TreeMap |
|---|---|---|
| Key-value storage | Yes | Yes |
| Duplicate keys | Not allowed | Not allowed |
| Key ordering | Not guaranteed | Sorted |
| Average/basic get() | O(1) | O(log n) |
| put() | O(1) average | O(log n) |
| remove() | O(1) average | O(log n) |
| Navigation methods | No | Yes |
| Typical use | Fast key-based lookup without ordering | Sorted keys and navigational access |
TreeMap vs LinkedHashMap
| Feature | LinkedHashMap | TreeMap |
|---|---|---|
| Key-value storage | Yes | Yes |
| Insertion order | Maintained by default | No |
| Sorted keys | No | Yes |
| Typical basic lookup | O(1) average | O(log n) |
| Access-order mode | Supported | No |
| Navigation methods | No | Yes |
| Typical use | Predictable insertion/access order | Sorted keys and range navigation |
TreeMap vs HashMap vs LinkedHashMap
| Requirement | Best Fit | Reason |
|---|---|---|
| Fast lookup, ordering irrelevant | HashMap | Efficient average-case hash-based operations. |
| Fast lookup with insertion order | LinkedHashMap | Maintains predictable insertion order. |
| Fast lookup with access-order tracking | LinkedHashMap | Supports access-order mode. |
| Sorted keys | TreeMap | Maintains keys according to a defined ordering. |
| Range queries | TreeMap | Provides sorted range views. |
| Neighbor-key searches | TreeMap | Provides lower, floor, ceiling, and higher operations. |
Real-World Example: Price Lookup
Imagine an application storing product prices by product ID. The system occasionally needs to find the nearest available product ID above or below a requested ID.
TreeMap<Integer, Double> prices =
new TreeMap<>();
prices.put(1001, 499.0);
prices.put(1005, 799.0);
prices.put(1010, 999.0);
prices.put(1020, 1499.0);
int requestedId = 1007;
System.out.println(
prices.floorEntry(requestedId)
);
System.out.println(
prices.ceilingEntry(requestedId)
);
TreeMap can efficiently locate the closest available keys around 1007 without manually scanning every entry.
Real-World Example: Score Ranking
A TreeMap can also organize information by sorted scores.
TreeMap<Integer, String> ranking =
new TreeMap<>();
ranking.put(500, "Player A");
ranking.put(750, "Player B");
ranking.put(900, "Player C");
ranking.put(1000, "Player D");
System.out.println(
ranking.lastEntry()
);
The largest score can be obtained directly through lastEntry().
For more complex leaderboards where multiple players may share the same score, a different data structure may be more appropriate because TreeMap keys must be unique.
Real-World Example: Time-Based Data
TreeMap can be useful when keys represent ordered values such as timestamps, dates, versions, or numeric ranges.
TreeMap<Integer, String> events =
new TreeMap<>();
events.put(1000, "Login");
events.put(2000, "Search");
events.put(3000, "Purchase");
System.out.println(
events.floorEntry(2500)
);
The application can retrieve the latest event whose key does not exceed a specified point.
Range Queries
One of TreeMap's strongest practical features is its ability to represent a range of sorted keys as a view.
TreeMap<Integer, String> events =
new TreeMap<>();
events.put(100, "A");
events.put(200, "B");
events.put(300, "C");
events.put(400, "D");
events.put(500, "E");
NavigableMap<Integer, String> range =
events.subMap(
200,
true,
400,
false
);
System.out.println(range);
This creates a view containing keys from 200 through values below 400.
Important: TreeMap range methods generally return views backed by the original map. Changes made through a supported view operation can affect the original map.
Common Beginner Mistakes
- Expecting insertion order: TreeMap orders by key according to its comparator, not by insertion sequence.
- Thinking values are sorted: TreeMap sorts keys only.
- Expecting O(1) lookup: TreeMap key-based operations are typically O(log n), not O(1).
- Using custom keys without ordering: Keys need a compatible natural ordering or a suitable Comparator.
- Ignoring Comparator equality: compare() returning zero means TreeMap treats the keys as equivalent.
- Adding null with natural ordering: Natural ordering generally cannot compare null with normal keys.
- Forgetting key uniqueness: Two different records cannot coexist under the same logical key.
- Assuming TreeMap is thread-safe: TreeMap is not inherently synchronized.
Best Practices
- Use TreeMap when sorted key ordering is an actual application requirement.
- Use NavigableMap methods when you need nearest-key or boundary searches.
- Use Comparable when the domain type has a natural ordering.
- Use Comparator when different ordering strategies are required.
- Ensure the comparison logic correctly represents the uniqueness semantics of the Map.
- Use HashMap when sorting and navigation provide no value.
- Use LinkedHashMap when insertion order or access order is the requirement.
- Avoid mutable state that can invalidate the ordering assumptions of keys already stored in the map.
- Use appropriate concurrent data structures when shared access across threads is required.
Interview Insights
Question: What is TreeMap?
Answer: TreeMap is a NavigableMap implementation that stores key-value mappings according to the sorted order of its keys.
Question: What is the time complexity of TreeMap operations?
Answer: Basic key-based operations such as put(), get(), containsKey(), and remove() are typically O(log n).
Question: What is the difference between HashMap and TreeMap?
Answer: HashMap provides hash-based average-case O(1) key operations without a guaranteed key order, while TreeMap maintains sorted keys and typically provides O(log n) key operations.
Question: What is the difference between LinkedHashMap and TreeMap?
Answer: LinkedHashMap maintains insertion order by default, while TreeMap maintains keys according to a sorted ordering.
Question: What are lowerKey(), floorKey(), ceilingKey(), and higherKey()?
Answer: They provide neighboring-key navigation around a target. lower and higher are strict; floor and ceiling can include the target.
Question: Can TreeMap contain duplicate keys?
Answer: No. A key can have only one mapping. A new value for an existing key replaces the previous value.
Question: Can TreeMap contain null values?
Answer: Yes. Null values are allowed, although null keys generally cannot be used with natural ordering.
Quick Revision
| Concept | Key Point |
|---|---|
| TreeMap | NavigableMap implementation that maintains keys in sorted order. |
| Keys | Must be unique. |
| Values | Can be duplicated. |
| Ordering | Natural ordering or Comparator. |
| put() | Typically O(log n). |
| get() | Typically O(log n). |
| remove() | Typically O(log n). |
| firstKey() | Returns the smallest key. |
| lastKey() | Returns the largest key. |
| lowerKey() | Greatest key strictly smaller than the target. |
| floorKey() | Greatest key smaller than or equal to the target. |
| ceilingKey() | Smallest key greater than or equal to the target. |
| higherKey() | Smallest key strictly greater than the target. |
| HashMap alternative | Use when sorted ordering and navigation are unnecessary. |
| LinkedHashMap alternative | Use when insertion or access order is required. |
TreeMap completes the core Map implementations in this chapter: HashMap focuses on efficient key-based lookup, LinkedHashMap adds predictable insertion or access order, and TreeMap adds sorted keys plus powerful navigation and range operations. The key lesson is simple: choose TreeMap when sorted keys are part of the problem itself, not merely because the output happens to look nicer when sorted. With this understanding, you now have a strong foundation across Java's major Set and Map implementations.