> Java > TreeMap

TreeMap class in Java

Last Updated: 24 June, 2023

The TreeMap class is a child class of AbstractMap, and it implements the NavigableMap interface, which is a child interface of SortedMap. The TreeMap class was introduced in JDK 1.2 and is found in the java.util package.

The TreeMap class is used to store the data in the form of key-value pairs, and its implementation is based on red-black tree concepts.

TreeMap does not allow duplicate keys, but values may be duplicated.
TreeMap does not allow null keys but allows null values.
TreeMap stores data by default in ascending order based on the keys.
TreeMap class is not synchronized.

👉 Java TreeMap Class Hierarchy

As we can see from the complete hierarchy above, TreeMap extends the AbstractMap class and implements the NavigableMap interface.

👉 TreeMap Class Declaration

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

Here, K is the key Object type and V is the value Object type.

👉 Example: A sample Java program of TreeMap

  
  import java.util.TreeMap;
  public class TreeMapExample {
    public static void main(String[] args) {
      // Creating a TreeMap
      TreeMap<Integer, String> fruitsTree = new TreeMap<>();
  
      // Inserting data in the form of key-value pair using put() method
      fruitsTree.put(10, "Apple");
      fruitsTree.put(20, "Banana");
      fruitsTree.put(30, "Mango");
      fruitsTree.put(40, "Payaya");
      fruitsTree.put(50, "Grapes");
  
      // Printing the elements of TreeMap
      System.out.println("TreeMap Elements: " + fruitsTree);
    }
  }

Output

TreeMap Elements:{10=Apple, 20=Banana, 30=Mango, 40=Payaya, 50=Grapes}

👉 Java TreeMap Class Constructors

Constructor	Description
TreeMap()	Constructs a new, empty tree map, using the natural ordering of its keys.
TreeMap(Comparator<? super K> comparator)	Constructs a new, empty tree map, ordered according to the given comparator.
TreeMap(Map<? extends K,? extends V> m)	Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.
TreeMap(SortedMap<K,? extends V> m)	Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.

👉 Java TreeMap Class Methods

Methods	Description
Map.Entry<K,V> ceilingEntry(K key)	It returns the key-value pair having the least key, greater than or equal to the specified key, or null if there is no such key.
K ceilingKey(K key)	It returns the least key, greater than the specified key or null if there is no such key.
void clear()	It removes all the key-value pairs from a map.
Object clone()	It returns a shallow copy of TreeMap instance.
Comparator<? super K> comparator()	It returns the comparator that arranges the key in order, or null if the map uses the natural ordering.
NavigableSet<K> descendingKeySet()	It returns a reverse order NavigableSet view of the keys contained in the map.
NavigableMap<K,V> descendingMap()	It returns the specified key-value pairs in descending order.
Map.Entry firstEntry()	It returns the key-value pair having the least key.
Map.Entry<K,V> floorEntry(K key)	It returns the greatest key, less than or equal to the specified key, or null if there is no such key.
void forEach(BiConsumer<? super K,? super V> action)	It 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)	It returns the key-value pairs whose keys are strictly less than toKey.
NavigableMap<K,V> headMap(K toKey, boolean inclusive)	It returns the key-value pairs whose keys are less than (or equal to if 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.
K higherKey(K key)	It is used to return true if this map contains a mapping for the specified key.
Set keySet()	It returns the 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.
Map.Entry<K,V> lowerEntry(K key)	It returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
K lowerKey(K key)	It returns the greatest key strictly less than the given key, or null if there is no such key.
NavigableSet<K> navigableKeySet()	It returns a NavigableSet view of the keys contained in this map.
Map.Entry<K,V> pollFirstEntry()	It removes and returns a key-value mapping associated with the least key in this 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, or null if the map is empty.
V put(K key, V value)	It inserts the specified value with the specified key 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 replaces 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.
void replaceAll(BiFunction<? super K,? super V,? extends V> function)	It 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 whose keys range from fromKey to toKey.
SortedMap<K,V> subMap(K fromKey, K toKey)	It returns key-value pairs whose keys range from fromKey, inclusive, to toKey, exclusive.
SortedMap<K,V> tailMap(K fromKey)	It returns key-value pairs whose keys are greater than or equal to fromKey.
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)	It returns key-value pairs whose keys are greater than (or equal to, if inclusive is true) fromKey.
boolean containsKey(Object key)	It returns true if the map contains a mapping for the specified key.
boolean containsValue(Object value)	It returns true if the map maps one or more keys to the specified value.
K firstKey()	It is used to return the first (lowest) key currently in this sorted map.
V get(Object key)	It is used to return the value to which the map maps the specified key.
K lastKey()	It is used to return the last (highest) key currently in the sorted map.
V remove(Object key)	It removes the key-value pair of the specified key from the map.
int size()	It returns the number of key-value pairs exists in the hashtable.
Collection values()	It returns a collection view of the values contained in the map.

TreeMap Class Methods Examples

The Java TreeMap class provided methods are implemented in the below given examples. Let's go through the examples one by one and understand the uses for each method.

Example 1 : Methods for Adding elements in TreeMap

  import java.util.TreeMap;
  public class AddElementsInTreeMap {
    public static void main(String args[]) {
  
      // Creating TreeMap
      TreeMap<Integer, String> map = new TreeMap<>();
  
      map.put(44, "C");
      map.put(55, "C++");
      map.put(11, "Java");
      map.put(77, "Python");
  
      System.out.println("TreeMap Elements: " + map);
  
      // Add element if Key is unique
      map.putIfAbsent(22, "Go Lang");
      // Adding duplicate Key
      map.putIfAbsent(44, "HTML");
      System.out.println("\nAfter calling putIfAbsent(): " + map);
  
      // Creating another HashMap
      TreeMap<Integer, String> childMap = new TreeMap<>();
      childMap.put(66, "MySQL");
      childMap.put(33, "MongoDB");
  
      // Copies all of the mappings from the specified map to this map
      map.putAll(childMap);
  
      System.out.println("\nTreeMap Elements after adding another TreeMap:");
      System.out.println(map);
    }
  }

Output

TreeMap Elements: {11=Java, 44=C, 55=C++, 77=Python}

After calling putIfAbsent(): {11=Java, 22=Go Lang, 44=C, 55=C++, 77=Python}

TreeMap Elements after adding another TreeMap: {11=Java, 22=Go Lang, 33=MongoDB, 44=C, 55=C++, 66=MySQL, 77=Python}

Example 2 : Methods for Accessing elements from TreeMap

  import java.util.Collection;
  import java.util.TreeMap;
  import java.util.Map;
  public class AccessElementsFromTreeMap {
    public static void main(String args[]) {
      
      // Creating TreeMap
      TreeMap<Integer, String> map = new TreeMap<>();
      map.put(55, "C");
      map.put(44, "C++");
      map.put(11, "Java");
      map.put(33, "Python");
      map.put(22, "Go Lang");
      
      System.out.println("TreeMap Elements: " + map);
      
      // Iterate the map using for-each loop
      System.out.println("\nIterate the map using for-each loop");
      for (Map.Entry<Integer, String> e : map.entrySet())
        System.out.println("Key: " + e.getKey() + " Value: " + e.getValue());
      
      // Access element by key
      System.out.println("\nAfter called map.get(22): " + map.get(22));
      
      // Returns a Collection view of the values contained in this map.
      System.out.println("\nReturns a Collection view of the values contained in map");
      Collection<String> values = map.values();
      for(String str : values)
        System.out.println(str);
    }
  }

Output

TreeMap Elements: {11=Java, 22=Go Lang, 33=Python, 44=C++, 55=C}

Iterate the map using for-each loop
Key: 11 Value: Java
Key: 22 Value: Go Lang
Key: 33 Value: Python
Key: 44 Value: C++
Key: 55 Value: C

After called map.get(22): Go Lang

Returns a Collection view of the values contained in this map
Java
Go Lang
Python
C++
C

Example 3 : Methods for Updating elements in TreeMap

  import java.util.TreeMap;
  public class UpdateElementsInTreeMap {
    public static void main(String args[]) {
  
      // Creating TreeMap
      TreeMap<Integer, String> map = new TreeMap<>();
      map.put(22, "C");
      map.put(44, "C++");
      map.put(11, "Java");
      map.put(33, "Python");
      map.put(55, "Go Lang");
  
      System.out.println("TreeMap Elements: " + map);
  
      // Replaces the entry for the specified key
      map.replace(55, "MySQL");
      System.out.println("\nAfter called map.replace(55, \"MySQL\"):");
      System.out.println(map);
      
      // Replaces the entry for the specified key and value
      map.replace(11, "Java", "JAVA/J2EE");
      System.out.println("\nAfter called map.replace(11, \"Java\", \"JAVA/J2EE\"):");
      System.out.println(map);
      
      // Replace all the values
        map.replaceAll((k,v) -> "MongoDB");
        System.out.println("\nAfter called map.replaceAll((k,v) -> \"MongoDB\"):");
        System.out.println(map);
    }
  }

Output

TreeMap Elements: {11=Java, 22=C, 33=Python, 44=C++, 55=Go Lang}

After called map.replace(55, "MySQL"):
{11=Java, 22=C, 33=Python, 44=C++, 55=MySQL}

After called map.replace(11, "Java", "JAVA/J2EE"):
{11=JAVA/J2EE, 22=C, 33=Python, 44=C++, 55=MySQL}

After called map.replaceAll((k,v) -> "MongoDB"):
{11=MongoDB, 22=MongoDB, 33=MongoDB, 44=MongoDB, 55=MongoDB}

Example 4 : Methods for Removing elements from TreeMap

  import java.util.TreeMap;
  public class RemoveElementsFromTreeMap {
    public static void main(String args[]) {
  
      // Creating TreeMap
      TreeMap<Integer, String> map = new TreeMap<>();
      map.put(33, "C");
      map.put(55, "C++");
      map.put(11, "Java");
      map.put(44, "Python");
      map.put(22, "Go Lang");
  
      System.out.println("TreeMap Elements: " + map);
  
      // Remove element by key
      map.remove(22);
      System.out.println("\nAfter called map.remove(22): " + map);
      
      // Remove element by key-value
      map.remove(44, "Python");
      System.out.println("\nAfte called map.remove(44, \"Python\"):");
      System.out.println(map);
      
      // Remove element by correct key and wrong value.
      map.remove(11, "C++");
      System.out.println("\nAfter called map.remove(11, \"C++\"):");
      System.out.println(map);
      
      // Remove all the elements
      map.clear();
      System.out.println("\nAfter called map.clear(): " + map);
    }
  }

Output

TreeMap Elements: {11=Java, 22=Go Lang, 33=C, 44=Python, 55=C++}

After called map.remove(22): {11=Java, 33=C, 44=Python, 55=C++}

Afte called map.remove(44, "Python"):
{11=Java, 33=C, 55=C++}

After called map.remove(11, "C++"):
{11=Java, 33=C, 55=C++}

After called map.clear(): {}

Example 5 : Utility methods of TreeMap

  import java.util.TreeMap;
  public class TreeMapUtilityMethods {
    public static void main(String args[]) {
  
      // Creating TreeMap
      TreeMap<Integer, String> map = new TreeMap<>();
      map.put(22, "C");
      map.put(44, "C++");
      map.put(11, "Java");
      map.put(33, "Python");
  
      System.out.println("TreeMap Elements: " + map);
  
      // Returns the number of key-value mappings in this map.
      System.out.println("TreeMap Size: " + map.size());
      
      // Returns true if this map contains no key-value mappings.
      System.out.println("Is Map is Empty: " + map.isEmpty());
      
      // Returns true if this map contains a mapping for the specified key.
      System.out.println("map.containsKey(22): " + map.containsKey(22));
      
      // Returns true if this map maps one or more keys to the specified value.
      System.out.println("map.containsValue(\"Java\"): " + map.containsValue("Java"));
      
      // Remove all the elements from the map
      map.clear();
      System.out.println("After calling map.clear(): " + map);
    }
  }

Output

TreeMap Elements: {11=Java, 22=C, 33=Python, 44=C++}
TreeMap Size: 4
Is Map is Empty: false
map.containsKey(22): true
map.containsValue("Java"): true
After calling map.clear(): {}

Reference: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/TreeMap.html

That's all guys, hope this Java article is helpful for you.

Happy Learning... 😀

Please share this article on social media to help others.

If you have any query or suggestion regarding this artical please share with us
feedback@javabytechie.com

TreeMap - Interview Questions and Answers

Can TreeMap contain null keys or values?

No, TreeMap does not allow null keys. However, it can have null values. This is because TreeMap uses the keys to determine the ordering of elements, and null keys cannot be compared.

What is the time complexity of common operations in TreeMap?

Ans. The time complexity of common operations in TreeMap is as follows:

Insertion: O(log n)
Deletion: O(log n)
Search: O(log n)
Retrieval of minimum/maximum element: O(log n)

What is the difference between HashMap and TreeMap?

Ans. HashMap and TreeMap are implementations of the Map interface in Java, and both are by default synchronised classes and available in the java.util package. There are many differences between the HashMap and TreeMap classes. Let's look at those differences in the below-given table:

HashMap	TreeMap
HashMap is a hashtable-based implementation of the Map interface.	TreeMap is a tree-structure-based (internally, it uses a Red-Black tree) implementation of the NavigableMap interface.
HashMap implements the Map, Cloneable, and Serializable interfaces.	TreeMap implements the NavigableMap, Cloneable, and Serializable interfaces.
HashMap allows only one null key and multiple null values.	TreeMap does not allow null keys but can have multiple null values.
HashMap does not maintain the insertion order of elements.	TreeMap elements are sorted in natural order (ascending).
HashMap uses the equals() method of the Object class to compare keys. The equals() method of the Map class overrides it.	TreeMap uses the compareTo() method to compare keys.
HashMap allows heterogeneous elements because it does not perform sorting on keys.	TreeMap allows homogeneous values as a key because of sorting.
HashMap is much faster than TreeMap.	In comparison to HashMap, TreeMap is slower.
HashMap contains only basic functions.	TreeMap is rich in functionality.
The HashMap should be used when we do not require key-value pairs in sorted order.	The TreeMap should be used when we require key-value pairs in sorted (ascending) order.

TreeMap class in Java

👉 Java TreeMap Class Hierarchy

👉 TreeMap Class Declaration

👉 Example: A sample Java program of TreeMap

👉 Java TreeMap Class Constructors

👉 Java TreeMap Class Methods

TreeMap Class Methods Examples

TreeMap - Interview Questions and Answers

Currently No Video available