What is TreeMap in java?

What is TreeMap in java

Java TreeMap is one of the implementation class of Map interface in Java. Java TreeMap class is an implementation based on red-black tree.

public class TreeMap<K,V>

extends AbstractMap<K,V>

implements NavigableMap<K,V>, Cloneable, Serializable

Treemap implements NavigableMap interface and NavigableMap interface extends Map interface .

The SortedMap interface of Collection provides functionalities to maintain the ordering of keys exist in the Map. The NavigableMap interface provides many methods and navigable functionalities to navigate through the map. Navigable functionalities incluses : Finding any entry close to the provided entry ; greater than or just less than the given key, finding the first and last entry in the TreeMap etc.

What is TreeMap in Java
What is TreeMap in Java

Since  TreeMap in Java implements NavigableMap interface, it has the functionalities of both the NavigableMapas well as the SortedMap; TreeMap IS-A Map with navigable and sorting properties.

The elements in TreeMap are sorted by natural order. Remember, In Collection , all classes that starts with word ‘Tree’ are always sorted in natural order.

Some Important points to remember about TreeMap in Java :

  • Java TreeMap contains values in pair of the key and the value. It implements the NavigableMap interface and extends AbstractMap class.
  • Java TreeMap does not allows duplicate elements. It contains only unique elements.
  • Unlike HashMap, Java TreeMap cannot contain a null key but it can have multiple null values.
  • Java TreeMap is a non synchronized class hence it is not thread-safe but we can make it thread-safe by applying synchronization technique explicitly.
  • Java TreeMap maintains natural order of elements : ascending order.

TreeMap in Java

Constructors in Java TreeMap class

Constructor Description
TreeMap() The default constructor of TreeMap constructs and returns an empty tree map. It will be sorted using the natural order of its key.
TreeMap(Comparator<? super K> comparator) This constructor also constructs and returns an empty tree map but this will be sorted on the basis of provided comparator.
TreeMap(Map<? extends K,? extends V> m) It constructs treemap initialized with the entries from m (existing Map). Elements in this tree map will be sorted using the natural order of the keys.
TreeMap(SortedMap<K,? extends V> m) It constructs treemap initialized with the entries from the SortedMap sm (Existing SortedMap). Elements in this tree map will be sorted in the same order as sm.

Methods in Java TreeMap class

Method Description
Map.Entry<K,V> ceilingEntry(K key) This method returns the key-value pair having the key  greater than or equal to the specified key, or null if there is no such key present in the map.
K ceilingKey(K key) This method returns the least key, greater than the specified key or null if there is no such key present in the map.
void clear() It  is used to remove all the key-value pairs from a map, it empties the TreeMap.
Object clone() It returns the shallow copy of invoking TreeMap instance.
Comparator<? super K> comparator() This method returns the comparator which arranges the key in order, or null if the map uses the natural ordering.
NavigableSet<K> descendingKeySet() It returns a NavigableSet view with reverse order of the keys contained in the map.
NavigableMap<K,V> descendingMap() It  sorts and returns the specified key-value pairs in descending order.
Map.Entry<k,v> firstEntry()</k,v> It fetches and returns the key-value pair having the least key i.e the first element of TreeMap.
Map.Entry<K,V> floorEntry(K key) It  retrieves and returns the greatest key, less than or equal to the specified key, or null if there is no such key present in the map.
void forEach(BiConsumer<? super K,? super V> action) This method basically performs the given action for each entry in the map until all entries have been processed or the action throws an exception.
SortedMap<K,V> headMap(K toKey) This method returns the key-value pairs whose keys are strictly less than parameter : toKey.
NavigableMap<K,V> headMap(K toKey, boolean inclusive) This returns the key-value pairs whose keys are less than (or equal to if parameter : inclusive is true) toKey.
Map.Entry<K,V> higherEntry(K key) It returns the least key strictly greater than the given key, or null if there is no such key present in the map.
K higherKey(K key) It is used to return true if the invoking map contains a mapping for the specified key.
Set keySet() It returns the whole collection of keys exist in the map.
Map.Entry<K,V> lastEntry() It returns the key-value pair having the greatest key, or null if there is no such key present in the map.
Map.Entry<K,V> lowerEntry(K key) This method returns a key-value mapping associated with the greatest key strictly less than the provided key, or null if there is no such key present in the map.
K lowerKey(K key) This method returns the greatest key strictly less than the given key, or null if there is no such key present in the map.
NavigableSet<K> navigableKeySet() It returns a NavigableSet view of the keys contained in the invoking map.
Map.Entry<K,V> pollFirstEntry() It removes and returns a key-value mapping associated with the least key in this map (first entry of the map), or null if the map is empty.
Map.Entry<K,V> pollLastEntry() It removes and returns a key-value mapping associated with the greatest key in this map (last entry of the map), or null if the map is empty.
V put(K key, V value) It is used to insert the key,value pair in the map.
void putAll(Map<? extends K,? extends V> map) It is used to copy all the key-value pair from one map to another map.
V replace(K key, V value) It  is used to replace the specified value for a specified key.
boolean replace(K key, V oldValue, V newValue) It replaces the old value with the new value for a specified key, returns false if it does not contain key.
void replaceAll(BiFunction<? super K,? super V,? extends V> function) This method replaces each entry’s value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) It returns key-value pairs  from the map whose keys range lies between fromKey to toKey.
SortedMap<K,V> subMap(K fromKey, K toKey) It returns key-value pairs  from the map whose keys range lies between fromKey, inclusive, and toKey, exclusive.
SortedMap<K,V> tailMap(K fromKey) This method returns the sub sorted map i.e key-value pairs whose keys are greater than or equal to fromKey.
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) This method returns key-value pairs whose keys are greater than (or equal to, if parameter : inclusive is true) fromKey.
boolean containsKey(Object key) It returns true if the map contains the specified key.
boolean containsValue(Object value) It returns true if the map contains the specified value.
K firstKey() This method returns the first (lowest) key currently in this sorted map.
V get(Object key) It returns the value associated with the specified key in the map.
K lastKey() It returns the last (highest) key currently in the sorted map.
V remove(Object key) This method removes the key-value pair of the specified key from the map.
Set<Map.Entry<K,V>> entrySet() It returns a set view of the mappings exists in the map.
int size() This method returns the number of key-value pairs / elements exists in the map.
Collection values() This method returns a collection view of  allthe values contained in the map.

How to create a TreeMap in Java : Simple TreeMap

This example illustrates the steps to create a simple TreeMap and add new key-value pairs to it. The entries in the TreeMap will be sorted based on the natural ordering of keys –

import java.util.SortedMap;
import java.util.TreeMap;

 

public class TreeMapExample1 {

public static void main(String[] args) {

// Creating a simple TreeMap
SortedMap<String, Integer> articleNumbers = new TreeMap<>();

 

// Adding new elements to the TreeMap
articleNumbers.put(“D”, 1);
articleNumbers.put(“A”, 3);
articleNumbers.put(“C”, 2);
articleNumbers.put(“B”, 6);
articleNumbers.put(“F”, 5);

 

// Printing the TreeMap (Output will be sorted based on keys / natural ordering)
System.out.println(articleNumbers);
}

}

 

Output :

 

{A=3, B=6, C=2, D=1, F=5}

How to create a TreeMap in Java : TreeMap with a custom Comparator (Descending Order)

This example illustrates how to create a TreeMap with a custom comparator that orders the TreeMap entries in the descending order of keys –

import java.util.Comparator;
import java.util.SortedMap;
import java.util.TreeMap;

 

public class TreeMapExample2 {

public static void main(String[] args) {

// Code to create a TreeMap with a Custom comparator (Descending order)
SortedMap<String, Integer> articleNumbers = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s2.compareTo(s1);
}
});

 

// Or use the below code instead of above mentioned code
/*
SortedMap<String, String> articleNumbers = new TreeMap<>(Comparator.reverseOrder());
*/

 

// Adding new elements to the TreeMap
articleNumbers.put(“D”, 1);
articleNumbers.put(“A”, 3);
articleNumbers.put(“C”, 2);
articleNumbers.put(“B”, 6);
articleNumbers.put(“F”, 5);

 

// Printing the TreeMap (The keys will be sorted based on the supplied comparator)
System.out.println(articleNumbers);

 

}
}

 

Output :

{F=5, D=1, C=2, B=6, A=3}

How to create a TreeMap in Java : TreeMap with a custom Comparator (Case Insensitive Order)

The below example illustrates how to create a Case Insensitive Map i.e The TreeMap will ignore case while ordering the keys. It can be done by passing a custom CASE_INSENSITIVE_ORDER comparator to the TreeMap.  See How :

import java.util.Comparator;
import java.util.SortedMap;
import java.util.TreeMap;

 

public class TreeMapExample3 {
public static void main(String[] args) {

// Code to create a TreeMap with key sorted by ignoring case
SortedMap<String, Integer> articleNumbers = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.compareToIgnoreCase(s2);
}
});

// Or use the below code instead of above mentioned code
/*
SortedMap<String, Integer> articleNumbers = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
*/

// Adding new elements to the TreeMap
articleNumbers.put(“D”, 1);
articleNumbers.put(“a”, 3);
articleNumbers.put(“C”, 2);
articleNumbers.put(“b”, 6);
articleNumbers.put(“F”, 5);

// Printing the TreeMap
System.out.println(articleNumbers);

}
}

 

Output :

{a=3, b=6, C=2, D=1, F=5}

How to create a TreeMap in java : TreeMap with key as user-defined object

This is a very important interview question that what steps are required when we are using objects of user-defined classes as key in TreeMap. As we know, TreeMap sorts the map on basis of key in ascending order so if we are creating a TreeMap with key as user-defined object then below mentioned steps are required :

  • The class should implement Comparator interface.
  • compare method should be overridden.

See How :

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapExample {

public static void main(String a[]){

//create a TreeMap using name comparator (String comparison)

TreeMap<Users,String> tm = new TreeMap<Users, String>(new NameComp());

tm.put(new Users(“Rachel”,3000), “Rachel”);
tm.put(new Users(“Ross”,6000), “Ross”);
tm.put(new Users(“Chandler”,2000), “Chandler”);
tm.put(new Users(“Joey”,2400), “Joey”);

Set<Users> keys = tm.keySet();
for(Users key:keys){
System.out.println(key+” ==> “+tm.get(key));
}
System.out.println(“*************************”);

//create a TreeMap using salary comparator (int comparison)
TreeMap<Users,String> trmap = new TreeMap<Users, String>(new SalComp());

trmap.put(new Users(“Rachel”,3000), “Rachel”);
trmap.put(new Users(“Ross”,6000), “Ross”);
trmap.put(new Users(“Chandler”,2000), “Chandler”);
trmap.put(new Users(“Joey”,2400), “Joey”);

Set<Users> ks = trmap.keySet();

for(Users key:ks){
System.out.println(key+” ==> “+trmap.get(key));
}
}
}

class NameComp implements Comparator<Users>{

@Override
public int compare(Users e1, Users e2) {
return e1.getName().compareTo(e2.getName());
}
}

class SalComp implements Comparator<Users>{

@Override
public int compare(Users e1, Users e2) {
if(e1.getSal() > e2.getSal()){
return 1;
} else {
return -1;
}
}
}

class Users{

private String name;
private int sal;

public Users(String name, int sal){
this.name = name;
this.sal = sal;
}

public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getSal() {
return sal;
}
public void setSalary(int sal) {
this.sal = sal;
}
public String toString(){
return “Name: “+this.name+”:: Salary: “+this.sal;
}
}

 

Output :

 

Name: Chandler:: Salary: 2000 ==> Chandler

Name: Joey:: Salary: 2400 ==> Joey

Name: Rachel:: Salary: 3000 ==> Rachel

Name: Ross:: Salary: 6000 ==> Ross

*************************

Name: Chandler:: Salary: 2000 ==> null

Name: Joey:: Salary: 2400 ==> null

Name: Rachel:: Salary: 3000 ==> null

Name: Ross:: Salary: 6000 ==> null

How to access entries of a TreeMap in java

The below example illustrates –

  • How to find the size of a TreeMap.
  • How to check if a given key exists in a TreeMap or not.
  • How to retrieve the first entry / least entry from the TreeMap.
  • How to retrieve the last entry from the TreeMap.
  • How to retrieve the entry whose key is just lower than the given key.
  • How to retrieve the entry whose key is just higher than the given key.

import java.util.Map;
import java.util.TreeMap;

 

public class TreeMapExample4 {

public static void main(String[] args) {

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

 

friends.put(3, “Rachel”);
friends.put(1, “Ross”);
friends.put(2, “Chandler”);
friends.put(5, “Monica”);
friends.put(6, “Phoebe”);
friends.put(4, “Joey”);

 

System.out.println(“Friend map : ” + friends);

 

// Code to find the size of a TreeMap
System.out.println(“Total number of Friends : ” + friends.size());

 

// Code to check if a given key exists in a TreeMap
Integer id = 4;
if(friends.containsKey(id)) {

// Code to Get the value associated with a given key in a TreeMap
String name = friends.get(id);

System.out.println(“Friend with id ” + id + ” : ” + name);

} else {

System.out.println(“Friend does not exist with id : ” + id);
}

 

// Code to find the first and last entry
System.out.println(“First entry in Friends map : ” + friends.firstEntry());
System.out.println(“Last entry in Friends map : ” + friends.lastEntry());

 

// Code to find the entry whose key is just less than the given key
Map.Entry<Integer, String> friendJustBelow = friends.lowerEntry(5);

System.out.println(“Friend just below id 5 : ” + friendJustBelow);

 

// Code to find the entry whose key is just higher than the given key

Map.Entry<Integer, String> friendJustAbove = friends.higherEntry(5);
System.out.println(“Friend just above id 5 : ” + friendJustAbove);
}
}

 

Output :

 

Friend map : {1=Ross, 2=Chandler, 3=Rachel, 4=Joey, 5=Monica, 6=Phoebe}

Total number of Friends : 6

Friend with id 4 : Joey

First entry in Friends map : 1=Ross

Last entry in Friends map : 6=Phoebe

Friend just below id 5 : 4=Joey

Friend just above id 5 : 6=Phoebe

How to remove entries from a TreeMap in java

The below example illustrates –

  • How to remove a key from a TreeMap.
  • How to remove a key from a TreeMap only if it is associated with a given value.
  • How to remove the first entry of the TreeMap.
  • How to remove the last entry of the TreeMap.

import java.util.Map;
import java.util.TreeMap;

 

public class TreeMapExample5 {

public static void main(String[] args) {

TreeMap<String, String> friendsRating = new TreeMap<>();

 

friendsRating.put(“Joey”, “Best”);
friendsRating.put(“Monica”, “Good”);
friendsRating.put(“Chandler”, “Better”);
friendsRating.put(“Rachel”, “Fine”);

System.out.println(“Friends Rating : ” + friendsRating);

 

// Code to remove the mapping for a given key
String friendName = “Monica”;
String rating = friendsRating.remove(friendName);

if(rating != null) {

System.out.println(“Removed (” + friendName + ” => ” + rating + “) from the TreeMap. New TreeMap ” + friendName);

} else {

System.out.println(friendName + ” does not exist, or it is mapped to a null value”);

}

// Code to remove the mapping for the given key only if it is mapped to the given value

friendName = “Joey”;

boolean isRemoved = friendsRating.remove(friendName, “Good”);

System.out.println(“Was the mapping removed for ” + friendName + “? : ” + isRemoved);

 

// Code to remove the first entry from the TreeMap
Map.Entry<String, String> firstEntry = friendsRating.pollFirstEntry();

System.out.println(“Removed firstEntry : ” + firstEntry + “, New TreeMap : ” + friendsRating);

 

// Remove the last entry from the TreeMap
Map.Entry<String, String> lastEntry = friendsRating.pollLastEntry();

System.out.println(“Removed lastEntry : ” + lastEntry + “, New TreeMap : ” + friendsRating);
}
}

 

Output :

 

Friends Rating : {Chandler=Better, Joey=Best, Monica=Good, Rachel=Fine}

Removed (Monica => Good) from the TreeMap. New TreeMap Monica

Was the mapping removed for Joey? : false

Removed firstEntry : Chandler=Better, New TreeMap : {Joey=Best, Rachel=Fine}

Removed lastEntry : Rachel=Fine, New TreeMap : {Joey=Best}

Conclusion

TreeMap in java stores elements in  natural sorted order basis on Keys. It stores key-value pair. We can store custom object as key provided it should be of Comparable type.

For more interview questions and answers for Java : Go here .

For complete understanding of HashMap in Java : Go here .

For other Java concepts : Go here .

Thanks a lot for reading this article.

Please share your queries / suggestions / questions in below comment box. You can also directly connect with me through social media accounts.

Leave a Reply

Your email address will not be published. Required fields are marked *