1. What is TreeMap

TreeMap is a data structure that provides an ordered collection of key-value pairs. It is essentially a binary search tree sorted by its keys, allowing for efficient searching, insertion, and deletion operations. A TreeMap is implemented using a Red-Black tree, which is a type of self-balancing binary search tree.

TreeMap is commonly used when there is a need for a map implementation that maintains its keys in sorted order. Below is an example of a binary tree.

In the best and average cases binary search tree guarantees O(log n) time to insert, search and delete elements, and in the worst case Binary search tree takes O(n) time for insertion, search, and deletion operations.

2. TreeMap in Java

The TreeMap in Java is a member of the Java Collections Framework which implements Map interface and NavigableMap along with the AbstractMap Class. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

TreeMap in Java does not allow null keys (like Map) and thus a NullPointerException is thrown. However, multiple null values can be associated with different keys.

3. A use case of TreeMap

In 2022, I worked on a fintech platform using TreeMap to store the daily price of stocks (or securities) returned by the Australian Securities Exchange System via a SOAP method, this price data will be used to calculate the value of security transactions. We also use Redis to cache this TreeMap since it is used very frequently, additionally, the cost to build this TreeMap is quite high because a stock may contain a thousand daily pricing records (I will not demo Redis in this article cause we focus on only TreeMap : ) ).

A stock may have no price data on some days, in this case, we will use the price data of the nearest day. Let’s dig into an example with the daily pricing of stock “NT2” from 01-Jan-2023 to 15-Jan-2023 as below.

Within this example, if we bought 50 units of this stock on 07/01/2023, the value of this transaction is 99*50=4,950$. However, if we bought 30 units on 11/01/2023, there is no price data on 11/01/2023 so the price data on 09/01/2023 is selected (the nearest day of 11/01/2023). Hence, the value of this transaction is 102*30=3,060$.

The below DailyPricingService simulates how we utilize TreeMap to handle this use case with Java 11.

import java.math.BigDecimal;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class DailyPricingService {
  private static final Map<String, TreeMap<Date, BigDecimal>> MAP_SECURITY_DAILY_PRICING = new HashMap<>();

  public void add(String securityCode, Date date, BigDecimal price) {
    TreeMap<Date, BigDecimal> treeMapDailyPricing = MAP_SECURITY_DAILY_PRICING.get(securityCode);
    if (treeMapDailyPricing == null) {
      treeMapDailyPricing = new TreeMap<>();
      MAP_SECURITY_DAILY_PRICING.put(securityCode, treeMapDailyPricing);
    }
    treeMapDailyPricing.put(date, price);
  }

  public BigDecimal getPrice(String securityCode, Date date) {
    TreeMap<Date, BigDecimal> treeMapDailyPricing = MAP_SECURITY_DAILY_PRICING.get(securityCode);
    if (treeMapDailyPricing == null) {
      throw new IllegalArgumentException(String.format("No pricing data for security code %s", securityCode));
    }

    Entry<Date, BigDecimal> entry = treeMapDailyPricing.floorEntry(date);
    if (entry == null) {
      throw new IllegalArgumentException(String.format("No pricing data found for security code %s and date %s", securityCode, date));
    }
    return entry.getValue();
  }
}

Cause we need to maintain the daily pricing of multiple stocks so we use a Map<String, TreeMap<Date, BigDecimal>> with the key is stock code (or security code) and the value is its daily pricing data.

The add method is used to store price data on a day of a specific stock and the getPrice method is used to retrieve price data of a stock on a specific day.

We can easily write a unit test to test this service based on the original example.

import java.math.BigDecimal;
import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class DailyPricingServiceTest {
  @Test
  public void get_price_success() throws ParseException {
    DailyPricingService dailyPricingService = new DailyPricingService();
    DateFormat dateFormat = new SimpleDateFormat("dd/MM/yyyy");
    dailyPricingService.add("NT2", dateFormat.parse("01/01/2023"), BigDecimal.valueOf(100.5));
    dailyPricingService.add("NT2", dateFormat.parse("02/01/2023"), BigDecimal.valueOf(100.6));
    dailyPricingService.add("NT2", dateFormat.parse("03/01/2023"), BigDecimal.valueOf(100.7));
    dailyPricingService.add("NT2", dateFormat.parse("07/01/2023"), BigDecimal.valueOf(99));
    dailyPricingService.add("NT2", dateFormat.parse("09/01/2023"), BigDecimal.valueOf(102));
    dailyPricingService.add("NT2", dateFormat.parse("15/01/2023"), BigDecimal.valueOf(87.4));

    Assertions.assertEquals(dailyPricingService.getPrice("NT2", dateFormat.parse("11/01/2023")), BigDecimal.valueOf(102),
      "No price data on 11/01/2023, so the date on 09/01/2023 must be selected");
    Assertions.assertEquals(dailyPricingService.getPrice("NT2", dateFormat.parse("07/01/2023")), BigDecimal.valueOf(99),
      "The price data on 07/01/2023 must be 99");
  }
}

The example code can be found on GitHub.