Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
TreeMap
2.1.
Features
2.2.
Constructors
2.3.
Methods/Functions
2.4.
 
2.5.
 
2.6.
 
2.7.
 
2.8.
 
2.9.
Basic Operations
2.10.
Navigation Operations
3.
Frequently Asked Questions
4.
Key Takeaways
Last Updated: Mar 27, 2024

TreeMap in Java

Author Yashesvinee V
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A tree is a well-known data structure used to organise and represent hierarchical data. It is a collection of objects, known as nodes, linked together in a non-linear manner. A red-black tree is a self-balancing binary search tree in which every path from a node to any of its descendent null nodes should have the same number of black nodes.

A TreeMap is a red-black tree based NavigableMap implementation. The Navigable Map Interface is a member of the Java Collections framework and an extension of the SortedMap class that provides convenient navigation methods to traverse a map. TreeMap also implements the Map interface and the AbstractMap class.

Also read, Duck Number in Java and Hashcode Method in Java

TreeMap

Declaration:

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

 

Initialisation:

TreeMap<K, V> objectName = new TreeMap<K, V>();

 

K - Key object type   V - Value object type

Features

  • TreeMap contains key-value mappings sorted in the natural ordering of their keys by default. The mappings can also be sorted using a comparator at map creation time.
  • TreeMap implementation is not synchronised, i.e. if multiple threads access a Map concurrently where at least one thread makes structural modifications, it must be synchronised externally.
  • TreeMap allows the use of null values but not null keys.
  • Its implementation has a time cost of log(n) on all insertion, deletion and access operations.
  • It does not support the Entry.setValue method. All entry pairs returned by methods in this class represent the mappings at the time they were produced.

Constructors

  • TreeMap()
    • It constructs a new, empty treemap with the natural ordering of its keys.
TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>();
  • TreeMap(Comparator<? super K> comparator)
    • It constructs a new, empty treemap, whose keys are ordered according to the given comparator.
import java.util.*;
import java.util.concurrent.*;
// Comparator implementation
class Sort_keys implements Comparator<K> 
{
     // Comparator code
}
// Main class
public class Main 
{
    public static void main(String[] args)
    {
       TreeMap<K, V> tree_map = new TreeMap<K, V>(new Sort_keys());
     }
}
  • TreeMap(Map<? extends K,? extends V> m)
    • It constructs a new tree map containing the same mappings as the given map, with the natural ordering of its keys.
import java.util.*;
public class Main 
{
public static void main(String[] args)
   {
      Map<Integer, String> hash_map  = new HashMap<Integer, String>();

      // code to perform operations on hash_map

      TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>(hash_map);
    }
}
  • TreeMap(SortedMap<K,? extends V> m)
    • It constructs a new tree map containing the same mappings and ordering as the specified sorted map.
import java.util.*;
import java.util.concurrent.*;
public class Main 
{
public static void main(String[] args)
   {
     SortedMap<Integer, String> sorted_map  = new ConcurrentSkipListMap<Integer, String>();


     // code to perform operations on sorted_map


     TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>(sorted_map);
   }
}

Methods/Functions

Method

Type

Description

clear() void It removes all the mappings from a specified map.
clone() Object It returns a shallow copy of the identity hash map but does not clone its key-value pairs.
containsKey(Object Key)

boolean

 

It returns true if the given object is a key in the map.
containsValue(Object value) It returns true if the given object is mapped to one or more keys in the map.
entrySet() Set<Map.Entry<K, V>> It returns a set-view of all the mappings present in the map.
forEach(action) void It performs a given action for each key-value pair.
get(Object key) V It returns the value of the given key if it is present in the map else, it returns null.
keySet() KeySetView<K, V> It returns a set-view of the keys present in the map
put(K key, V value) V It adds a key-value pair to the identity hash map. If the key already exists, then its value is updated.
putAll(Map m)  void It copies all the key-value mappings of a given map and replaces the original content of the map
remove(Object key) V It removes the mapping for a given key if it is present in the map.
replace(K key,V value) V It replaces the value of a given key only if it is currently mapped to some value.
replace(K key, V oldValue, V newValue) boolean It replaces the value of a given key only if it is currently mapped to the specified value.
replaceAll(function) void It replaces the values of every key with a value generated by a given function.
size() int It returns the number of key-value pairs in the identity hash map.
values() Collection<V> It returns a collection view of the values present in the map.
ceilingEntry(K key) Map.Entry<K, V> It returns the mapping associated with the least key greater than or equal to the given key or null if absent.
ceilingKey(K key) K It returns the least key greater than or equal to the given key or null if absent.
comparator() Comparator<? super K> It returns the comparator used to order the keys in the TreeMap.
descendingKeySey() NavigableSet<K> It returns a reverse order of the NavigableSet view of keys in the map.
navigableKetSet() NavigableSet<K> It returns a NavigableSet view of all the keys in the map.
descendingMap() NavigableMap<K,V> It returns a reverse order view of all mappings in the map.
firstEntry() Map.Entry<K, V> It returns the mapping associated with the least key in the map.
firstKey() K It returns the first key in the map.
floorEntry(K key) Map.Entry<K, V> It returns the mapping associated with the greatest key less than or equal to the given key or null if absent.
floorKey(K key) K It returns the greatest key less than or equal to the given key or null if absent.
headMap(K toKey) SortedMap<K, V> It returns a portion of the map whose keys are strictly less than the given key, excluding the key itself.
higherEntry(K key) Map.Entry<K, V> It returns the mapping associated with the least key strictly greater than the given key or null if absent.
higherKey(K key) K It returns the least key strictly greater than the given key or null if absent.
lastEntry() Map.Entry<K, V> It returns the mapping associated with the greatest key in the map.
lastKey() K It returns the last key in the map.
lowerEntry<K key) Map.Entry<K, V> It returns the mapping associated with the greatest key strictly less than the given key or null if absent.
lowerkey(K key) K It returns the greatest key strictly less than the given key or null if absent.
pollFirstEntry()

Map.Entry<K, V>

 

It removes and returns the mapping associated with the least key in the map, or null is absent.
pollLastEntry() It removes and returns the mapping associated with the greatest key in the map, or null is absent.
subMap(K keyA, K keyB)

SortedMap<K, V>

 

It returns the map portion containing mappings whose keys range from keyA to keyB, including keyA but excluding keyB.
tailMap(K keyA) It returns the mappings of keys greater than keyA and keyA itself.

 

 

 

 

 

 


Also see,  Swap Function in Java

Basic Operations

  • Adding elements using put() and putAll() functions.
  • Removing elements using remove() function.
  • Accessing elements using entrySet(), values(), keySet() and get() functions.
  • Replacing elements using replace() and replaceAll() functions.
     
import java.util.TreeMap;

public class Main
 {
  public static void main(String[] args) 
     {
      TreeMap<String, String> India = new TreeMap<>();

      // Adding or insertion
      India.put("India","New Delhi");

      TreeMap<String, String> country = new TreeMap<>();
      country.putAll(India);

      country.put("Australia","Canberra");
      country.put("Germany","Berlin");
      country.put("France", "London");

        // Accessing elements
      System.out.println("TreeMap of country-capital: " + country.entrySet());
      System.out.println("\nList of keys (Country): " + country.keySet());
      System.out.println("List of values (Capitals): " + country.values());
      System.out.println("\nThe capital of France is :" + country.get("France"));
      System.out.println();

      // Replacing elements
      country.replace("France","Paris");
      System.out.println("Correcting the capital the of France to " + country.replace("France","Paris"));
      System.out.println(country);
      System.out.println("\nAbbreviating the names of all capitals.");
      country.replaceAll((key , oldValue) -> oldValue.substring(0, 3));
      System.out.println(country + "\n");

      //Removing elements
      System.out.println("Removing Australia: " + country.remove("Australia"));
      System.out.println(country);
  }
}

 

Output:

TreeMap of country-capital: [Australia=Canberra, France=London, Germany=Berlin, India=New Delhi]

List of keys Country): [Australia, France, Germany, India]
List of values (Capitals): [Canberra, London, Berlin, New Delhi]

The capital of France is :London

Correcting the capital the of France to Paris
{Australia=Canberra, France=Paris, Germany=Berlin, India=New Delhi}

Abbreviating the names of all capitals.
{Australia=Can, France=Par, Germany=Ber, India=New}

Removing Australia: Can
{France=Par, Germany=Ber, India=New}


Practice by yourself on online java compiler.

Navigation Operations

  • Obtain first and last mappings or keys.
  • Obtain highest and lowest mappings or keys.
  • Use of ceiling and floor methods.
  • Use of pollFirstEntry() and pollLastEntry() methods.
     
import java.util.TreeMap;

public class Main 
{
  public static void main(String[] args) 
     {      
      TreeMap<String, String> country = new TreeMap<>();

      country.put("India","New Delhi");
      country.put("Australia","Canberra");
      country.put("Germany","Berlin");
      country.put("France", "Paris");
      country.put("Japan", "Tokyo");
      country.put("Russia", "Moscow");
      country.put("Brazil", "Brasilia");

      System.out.println("TreeMap contents: " + country);

      // First and last
      System.out.println("First key: " + country.firstKey());
      System.out.println("First entry " + country.firstEntry());
      System.out.println("Last key " + country.lastKey());
      System.out.println("Last entry :" + country.lastEntry());
      System.out.println();

      // Highest and lowest
      System.out.println("Higher key: " + country.higherKey("Japan"));
      System.out.println("Higher entry: " + country.higherEntry("Japan"));
      System.out.println("Lower key: " + country.lowerKey("Japan"));
      System.out.println("Lower entry: " + country.lowerEntry("Japan"));
      System.out.println();

      //Ceiling and floor
      System.out.println("Ceiling key: " + country.ceilingKey("Japan"));
      System.out.println("Ceiling entry: " + country.ceilingEntry("Japan"));
      System.out.println("Floor key: " + country.floorKey("Japan"));
      System.out.println("Floor entry: " + country.floorEntry("Japan"));
      System.out.println();

      // poll first and last entry
      System.out.println("Poll first entry: " + country.pollFirstEntry());
      System.out.println("Poll last entry: " + country.pollLastEntry());
      System.out.println(country);
      System.out.println();
    }
}    

 

Output:

TreeMap contents: {Australia=Canberra, Brazil=Brasilia, France=Paris, Germany=Berlin, India=New Delhi, Japan=Tokyo, Russia=Moscow}
First key: Australia
First entry Australia=Canberra
Last key Russia
Last entry :Russia=Moscow

Higher key: Russia
Higher entry: Russia=Moscow
Lower key: India
Lower entry: India=New Delhi

Ceiling key: Japan
Ceiling entry: Japan=Tokyo
Floor key: Japan
Floor entry: Japan=Tokyo

Poll first entry: Australia=Canberra
Poll last entry: Russia=Moscow
{Brazil=Brasilia, France=Paris, Germany=Berlin, India=New Delhi, Japan=Tokyo}

 

  • Use of headMap(), tailMap() and subMap() functions.
import java.util.TreeMap;

public class Main 
{
  public static void main(String[] args) 
  {      
      TreeMap<String, String> country = new TreeMap<>();

      country.put("India","New Delhi");
      country.put("Australia","Canberra");
      country.put("Germany","Berlin");
      country.put("France", "Paris");
      country.put("Japan", "Tokyo");
      country.put("Russia", "Moscow");
      country.put("Brazil", "Brasilia");

      System.out.println("TreeMap contents: " + country);

      // First and last
      System.out.println("\nHeadMap: " + country.headMap("Germany"));
      System.out.println("\nTailMap: " + country.tailMap("Germany"));
      System.out.println("\nSubMap: " + country.subMap("Germany","Japan"));
    }
}

 

Output:

TreeMap contents: {Australia=Canberra, Brazil=Brasilia, France=Paris, Germany=Berlin, India=New Delhi, Japan=Tokyo, Russia=Moscow}

HeadMap: {Australia=Canberra, Brazil=Brasilia, France=Paris}

TailMap: {Germany=Berlin, India=New Delhi, Japan=Tokyo, Russia=Moscow}

SubMap: {Germany=Berlin, India=New Delhi}
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Q: What is the SortedMap interface, and how is it different from TreeMap?

The SortedMap interface provides a natural ordering of its keys for easy traversal. Its parent interface is the Map interface, and its subinterface is the NavigableMap.

SortedMap cannot be used to create objects as it is an interface. The implementation of the sortedMap is the TreeMap using which objects can be created. While the SortedMap restricts the use of null keys and null values, the TreeMap imposes restrictions only on the use of null keys.

Q: What is a comparator?

A comparator is a comparison function that imposes a total ordering on a collection of objects that do not have a natural ordering. They are used to control the sorting order of a set of elements or objects. It is an interface that is a member of the Java Collections Framework.

Key Takeaways

TreeMaps are special and extremely useful. The mappings they store can be arranged in the ascending order of its keys or by using the comparator as discussed. Since the mappings are already sorted, they quickly access its key-value pairs. This blog explains the TreeMap class in detail, along with its features and constructors. It also lists out the various functions and methods provided by this class to work with key-value mappings. 

Check out this problem - Reverse Nodes In K Group

Related Links:

Red-Black Trees

entryset java

Binary Search Tree

Check out the official Coding Ninjas Blog site and visit our Library for more.

Previous article
SortedMap
Next article
flatMap() Method in Java
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass