java.util.TreeMap<K, V> is the sorted map — every key is automatically placed in its correct sorted position, and firstKey(), lastKey(), floorKey(), ceilingKey(), headMap(), tailMap(), and subMap() let you query ranges without any manual scanning. The price over HashMap is O(log n) per operation — always, not just worst case — because every operation traverses a Red-Black tree. When your data needs to be both keyed and sorted, TreeMap handles both requirements in one structure.

What Is Java TreeMap?

TreeMap<K, V> is a concrete class in java.util that implements NavigableMap<K, V>. It stores entries in a self-balancing Red-Black tree keyed on the natural ordering of keys (via Comparable) or a supplied Comparator. Every traversal visits nodes in ascending key order.

The diagram below shows where TreeMap fits in the Map hierarchy.

java.util.Map<K, V>                         ← key-value contract
    ├── HashMap<K, V>                        ← O(1) avg, no order
    │       └── LinkedHashMap<K, V>          ← insertion/access order
    └── java.util.SortedMap<K, V>            ← adds sorted key view
            └── java.util.NavigableMap<K, V> ← adds floor, ceiling, lower, higher
                    └── java.util.TreeMap<K,V> ← THIS CLASS: Red-Black tree

KEY FACTS:
  Package    : java.util
  Since      : Java 1.2
  Implements : NavigableMap<K,V>, Cloneable, Serializable
  Backed by  : Red-Black tree (self-balancing BST)
  Key order  : natural (Comparable) or supplied Comparator — always ascending
  Null keys  : NOT allowed — compareTo(null) throws NullPointerException
  Null values: allowed (unlimited)
  Thread-safe: NO — use Collections.synchronizedSortedMap() or ConcurrentSkipListMap
  Operations : O(log n) guaranteed — tree height is bounded by 2 × log₂(n+1)

Basic Overview — TreeMap Method Groups

TreeMap inherits put(), get(), remove() from Map, then adds two layers of navigation through SortedMap and NavigableMap.

TREEMAP COMPLETE METHOD REFERENCE:

  MAP OPERATIONS (O(log n)):
    put(key, value)       ← insert or update
    get(key)              ← lookup
    remove(key)           ← delete
    containsKey(key)      ← O(log n) — traverses tree
    containsValue(value)  ← O(n) — full scan (no tree ordering on values)

  SORTED MAP ADDITIONS — SortedMap<K,V>:
    firstKey()            ← smallest key (leftmost node)
    lastKey()             ← largest key (rightmost node)
    headMap(toKey)        ← live view of keys strictly less than toKey
    tailMap(fromKey)      ← live view of keys >= fromKey
    subMap(from, to)      ← live view of keys in [from, to)
    comparator()          ← returns Comparator or null for natural ordering

  NAVIGABLE MAP ADDITIONS — NavigableMap<K,V>:
    floorKey(key)         ← largest key <= key (null if none)
    ceilingKey(key)       ← smallest key >= key (null if none)
    lowerKey(key)         ← largest key strictly < key (null if none)
    higherKey(key)        ← smallest key strictly > key (null if none)
    floorEntry(key)       ← Entry version of floorKey
    ceilingEntry(key)     ← Entry version of ceilingKey
    firstEntry()          ← Entry with smallest key
    lastEntry()           ← Entry with largest key
    pollFirstEntry()      ← remove and return smallest entry
    pollLastEntry()       ← remove and return largest entry
    descendingMap()       ← reverse-order view of entire map
    descendingKeySet()    ← reverse-order NavigableSet of keys
    headMap(to, inclusive)← overloaded with inclusive boundary
    tailMap(from, inclusive)← overloaded with inclusive boundary
    subMap(from,fi,to,ti) ← overloaded with inclusive boundaries

ALL range views are LIVE — modifications propagate back to the backing TreeMap.

When to Use TreeMap

USE TreeMap WHEN:
  1. Keys must be iterated in sorted order
     — leaderboards, alphabetical catalogues, sorted event logs

  2. Range queries are needed
     — all keys between 100 and 500: subMap(100, true, 500, true)
     — all keys alphabetically before "P": headMap("P")
     — all keys from a given timestamp: tailMap(timestamp)

  3. Nearest-key navigation is needed
     — "what is the largest configured timeout <= my request timeout?"
       → floorKey(requestTimeout)
     — "what is the next scheduled event >= now?"
       → ceilingKey(System.currentTimeMillis())

  4. A sorted unique-key view of a dataset must be maintained live
     — price levels, time slots, route segments

CHOOSE HashMap INSTEAD WHEN:
  - Key order is irrelevant
  - O(1) is required: HashMap put/get/remove are faster than TreeMap
  - The map holds millions of entries and the O(log n) cost accumulates

CHOOSE LinkedHashMap INSTEAD WHEN:
  - Insertion order (not key-sorted order) matters
  - O(1) operations are needed alongside ordered iteration

CHOOSE ConcurrentSkipListMap INSTEAD WHEN:
  - Sorted map with concurrent multi-thread access is needed
  - ConcurrentSkipListMap provides O(log n) operations with full thread safety

NEVER USE TreeMap WHEN:
  - Keys do not implement Comparable AND no Comparator is provided
    → ClassCastException on the second put() call
  - Null keys are needed → NullPointerException on any put(null, value)

How TreeMap Works Internally

Red-Black Tree Structure

Every entry in TreeMap is stored as an Entry<K, V> node in a Red-Black tree — a self-balancing binary search tree with five invariants that bound the tree height at 2 × log₂(n+1).

TREEMAP ENTRY NODE:
  K     key
  V     value
  Entry left, right  ← BST children
  Entry parent       ← parent reference (for upward traversal)
  boolean color      ← RED or BLACK (Red-Black invariant)

RED-BLACK TREE INVARIANTS:
  1. Every node is RED or BLACK
  2. The root is always BLACK
  3. No two consecutive RED nodes (RED node's parent must be BLACK)
  4. Every path from a node to a null leaf has the same number of BLACK nodes
  5. Null leaves are considered BLACK

THESE INVARIANTS GUARANTEE:
  Height <= 2 × log₂(n + 1)
  For n = 1,000,000 entries: height <= ~40 comparisons per operation

TREEMAP AFTER: put("D",4), put("B",2), put("F",6), put("A",1), put("C",3):

  In-order traversal always produces keys in ascending order.

  Tree structure (simplified, colours omitted):
            D
          /   \
        B       F
       / \
      A   C

  put() steps for "E":
    1. Compare "E" with root "D" → "E" > "D" → go right
    2. Compare "E" with "F"     → "E" < "F" → go left
    3. Null slot found → insert new node here
    4. Rebalance: check Red-Black invariants, rotate if needed
    O(log n) comparisons + O(log n) rotations (bounded)

  get("C"):
    1. Compare "C" with "D" → "C" < "D" → go left
    2. Compare "C" with "B" → "C" > "B" → go right
    3. Compare "C" with "C" → match → return value
    O(log n) comparisons — no collision chains, no hash computation

compareTo() Drives Everything

TreeMap uses compareTo() (natural ordering) or the provided Comparator for all operations. It never calls equals() or hashCode(). Two keys where compare(a, b) == 0 are treated as identical — the second put() replaces the value rather than adding a new entry.

DUPLICATE DETECTION in TreeMap:

  compare(key1, key2) == 0  →  same key — value replaced, no new node
  compare(key1, key2) != 0  →  different keys — separate nodes

  This is independent of equals(). If compare() returns 0 but equals()
  returns false, TreeMap treats them as the same key (value replaced).

  CONSISTENCY-WITH-EQUALS CONTRACT (recommended, not enforced):
    (a.compareTo(b) == 0) should equal (a.equals(b))

  BigDecimal violates this: 2.0.compareTo(2.00) == 0 but equals is false.
  In a TreeMap<BigDecimal, ...>, put(new BigDecimal("2.0"), X) followed by
  put(new BigDecimal("2.00"), Y) results in one entry with value Y.

Core Operations with Examples

put(), get(), Basic SortedMap Methods

Java

Try it out

// File: TreeMapBasicsDemo.java

import java.util.TreeMap;

public class TreeMapBasicsDemo {

    public static void main(String[] args) {

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

        // put() — always maintains sorted key order
        cityRank.put("Mumbai",     1);
        cityRank.put("Delhi",      2);
        cityRank.put("Bengaluru",  3);
        cityRank.put("Hyderabad",  4);
        cityRank.put("Chennai",    5);
        cityRank.put("Ahmedabad",  6);

        System.out.println("=== TreeMap iterates in sorted key order ===");
        cityRank.forEach((city, rank) ->
            System.out.printf("  %-12s rank %d%n", city, rank));

        System.out.println("\n=== SortedMap boundary access ===");
        System.out.println("firstKey()  : " + cityRank.firstKey());  // Ahmedabad (alphabetically first)
        System.out.println("lastKey()   : " + cityRank.lastKey());   // Mumbai (alphabetically last)
        System.out.println("firstEntry(): " + cityRank.firstEntry()); // Ahmedabad=6
        System.out.println("lastEntry() : " + cityRank.lastEntry());  // Mumbai=1

        System.out.println("\n=== pollFirstEntry / pollLastEntry ===");
        System.out.println("pollFirstEntry(): " + cityRank.pollFirstEntry()); // removes Ahmedabad
        System.out.println("pollLastEntry() : " + cityRank.pollLastEntry());  // removes Mumbai
        System.out.println("After polls     : " + cityRank.keySet());
    }
}

Output:
=== TreeMap iterates in sorted key order ===
  Ahmedabad    rank 6
  Bengaluru    rank 3
  Chennai      rank 5
  Delhi        rank 2
  Hyderabad    rank 4
  Mumbai       rank 1

=== SortedMap boundary access ===
firstKey()  : Ahmedabad
lastKey()   : Mumbai
firstEntry(): Ahmedabad=6
lastEntry() : Mumbai=1

=== pollFirstEntry / pollLastEntry ===
pollFirstEntry(): Ahmedabad=6
pollLastEntry() : Mumbai=1
After polls     : [Bengaluru, Chennai, Delhi, Hyderabad]

NavigableMap — Floor, Ceiling, Lower, Higher

Java

Try it out

// File: TreeMapNavigationDemo.java

import java.util.TreeMap;

public class TreeMapNavigationDemo {

    public static void main(String[] args) {

        // Price tier map — nearest-price queries
        TreeMap<Integer, String> priceTiers = new TreeMap<>();
        priceTiers.put(199,  "Basic");
        priceTiers.put(499,  "Standard");
        priceTiers.put(999,  "Premium");
        priceTiers.put(1999, "Pro");
        priceTiers.put(4999, "Enterprise");

        System.out.println("Price tiers: " + priceTiers);
        System.out.println();

        int userBudget = 750;

        // floorKey — largest key <= budget (best affordable tier)
        System.out.printf("Budget: Rs.%d%n", userBudget);
        System.out.printf("floorKey(%d)   : %s  (best tier within budget)%n",
            userBudget, priceTiers.floorKey(userBudget));

        // ceilingKey — smallest key >= budget (cheapest tier at or above budget)
        System.out.printf("ceilingKey(%d) : %s  (cheapest tier at or above budget)%n",
            userBudget, priceTiers.ceilingKey(userBudget));

        // lowerKey — largest key strictly < budget
        System.out.printf("lowerKey(%d)   : %s  (strictly below budget)%n",
            userBudget, priceTiers.lowerKey(userBudget));

        // higherKey — smallest key strictly > budget
        System.out.printf("higherKey(%d)  : %s  (just above budget)%n",
            userBudget, priceTiers.higherKey(userBudget));

        System.out.println();

        // Edge cases — returns null when no key satisfies the condition
        System.out.println("=== Edge cases ===");
        System.out.println("floorKey(100)    : " + priceTiers.floorKey(100));    // null — below all tiers
        System.out.println("ceilingKey(6000) : " + priceTiers.ceilingKey(6000)); // null — above all tiers
        System.out.println("floorKey(999)    : " + priceTiers.floorKey(999));    // 999 — exact match
        System.out.println("lowerKey(199)    : " + priceTiers.lowerKey(199));    // null — nothing below minimum
        System.out.println("floorEntry(750)  : " + priceTiers.floorEntry(750));  // full entry
    }
}

Output:
Price tiers: {199=Basic, 499=Standard, 999=Premium, 1999=Pro, 4999=Enterprise}

Budget: Rs.750
floorKey(750)   : 499  (best tier within budget)
ceilingKey(750) : 999  (cheapest tier at or above budget)
lowerKey(750)   : 499  (strictly below budget)
higherKey(750)  : 999  (just above budget)

=== Edge cases ===
floorKey(100)    : null
ceilingKey(6000) : null
floorKey(999)    : 999
lowerKey(199)    : null
floorEntry(750)  : 499=Standard

Range Views — headMap, tailMap, subMap

Java

Try it out

// File: TreeMapRangeDemo.java

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

public class TreeMapRangeDemo {

    public static void main(String[] args) {

        TreeMap<Long, String> eventLog = new TreeMap<>();
        eventLog.put(1_000L, "UserLogin");
        eventLog.put(2_000L, "CartUpdated");
        eventLog.put(3_000L, "PaymentInitiated");
        eventLog.put(4_000L, "PaymentConfirmed");
        eventLog.put(5_000L, "OrderPlaced");
        eventLog.put(6_000L, "OrderDispatched");
        eventLog.put(7_000L, "UserLogout");

        System.out.println("All events: " + eventLog.values());
        System.out.println();

        // headMap — strictly before timestamp 4000
        System.out.println("=== headMap(4000) — before payment confirmation ===");
        Map<Long, String> before = eventLog.headMap(4_000L);
        before.forEach((ts, event) -> System.out.println("  " + ts + ": " + event));

        // headMap with inclusive boundary
        System.out.println("\n=== headMap(4000, inclusive=true) ===");
        eventLog.headMap(4_000L, true)
                .forEach((ts, event) -> System.out.println("  " + ts + ": " + event));

        // tailMap — from timestamp 5000 (inclusive by default)
        System.out.println("\n=== tailMap(5000) — from order placed onwards ===");
        eventLog.tailMap(5_000L)
                .forEach((ts, event) -> System.out.println("  " + ts + ": " + event));

        // subMap — range [3000, 6000) exclusive
        System.out.println("\n=== subMap(3000, 6000) — payment + order events ===");
        eventLog.subMap(3_000L, 6_000L)
                .forEach((ts, event) -> System.out.println("  " + ts + ": " + event));

        // subMap with inclusive both ends
        System.out.println("\n=== subMap(3000, true, 6000, true) — inclusive both ===");
        eventLog.subMap(3_000L, true, 6_000L, true)
                .forEach((ts, event) -> System.out.println("  " + ts + ": " + event));

        // Range views are LIVE — modifications propagate to backing TreeMap
        System.out.println("\n=== Live view — remove through headMap ===");
        NavigableMap<Long, String> loginPhase = eventLog.headMap(3_000L, true);
        loginPhase.clear(); // removes events 1000, 2000, 3000 from backing TreeMap
        System.out.println("Backing TreeMap after clear: " + eventLog.values());

        // descendingMap — reverse order view
        System.out.println("\n=== descendingMap() — most recent first ===");
        eventLog.descendingMap()
                .forEach((ts, event) -> System.out.println("  " + ts + ": " + event));
    }
}

Output:
All events: [UserLogin, CartUpdated, PaymentInitiated, PaymentConfirmed, OrderPlaced, OrderDispatched, UserLogout]

=== headMap(4000) — before payment confirmation ===
  1000: UserLogin
  2000: CartUpdated
  3000: PaymentInitiated

=== headMap(4000, inclusive=true) ===
  1000: UserLogin
  2000: CartUpdated
  3000: PaymentInitiated
  4000: PaymentConfirmed

=== tailMap(5000) — from order placed onwards ===
  5000: OrderPlaced
  6000: OrderDispatched
  7000: UserLogout

=== subMap(3000, 6000) — payment + order events ===
  3000: PaymentInitiated
  4000: PaymentConfirmed
  5000: OrderPlaced

=== subMap(3000, true, 6000, true) — inclusive both ===
  3000: PaymentInitiated
  4000: PaymentConfirmed
  5000: OrderPlaced
  6000: OrderDispatched

=== Live view — remove through headMap ===
Backing TreeMap after clear: [PaymentConfirmed, OrderPlaced, OrderDispatched, UserLogout]

=== descendingMap() — most recent first ===
  7000: UserLogout
  6000: OrderDispatched
  5000: OrderPlaced
  4000: PaymentConfirmed

Custom Ordering with Comparator

Java

Try it out

// File: TreeMapComparatorDemo.java

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

public class TreeMapComparatorDemo {

    record Product(String id, String name, double price, int stock) {}

    public static void main(String[] args) {

        // Sort by price ascending, then by id as tiebreaker
        // Tiebreaker is CRITICAL — without it, equal-price products overwrite each other
        Comparator<Product> byPriceThenId =
            Comparator.comparingDouble(Product::price)
                      .thenComparing(Product::id);

        TreeMap<Product, Integer> catalogue = new TreeMap<>(byPriceThenId);
        catalogue.put(new Product("P003", "USB Hub",        799.0,  42), 42);
        catalogue.put(new Product("P001", "Mouse Pad",      199.0, 100), 100);
        catalogue.put(new Product("P005", "HDMI Cable",     399.0,  65), 65);
        catalogue.put(new Product("P002", "Keyboard Cover", 299.0,  80), 80);
        catalogue.put(new Product("P004", "Laptop Stand",   799.0,  30), 30); // same price as P003

        System.out.println("=== Sorted by price ascending (tiebreak: id) ===");
        catalogue.forEach((product, qty) ->
            System.out.printf("  Rs.%5.2f  %-18s (stock: %d)%n",
                product.price(), product.name(), qty));

        // floorKey, ceilingKey work with the Comparator
        Product probe = new Product("", "", 400.0, 0);
        System.out.println("\nfloor (<=Rs.400)   : "
            + (catalogue.floorKey(probe) != null
                ? catalogue.floorKey(probe).name() : "none"));
        System.out.println("ceiling (>=Rs.400) : "
            + (catalogue.ceilingKey(probe) != null
                ? catalogue.ceilingKey(probe).name() : "none"));

        // descendingMap — most expensive first
        System.out.println("\n=== Descending (most expensive first) ===");
        catalogue.descendingMap().forEach((product, qty) ->
            System.out.printf("  Rs.%5.2f  %s%n", product.price(), product.name()));
    }
}

Output:
=== Sorted by price ascending (tiebreak: id) ===
  Rs.199.00  Mouse Pad          (stock: 100)
  Rs.299.00  Keyboard Cover     (stock: 80)
  Rs.399.00  HDMI Cable         (stock: 65)
  Rs.799.00  USB Hub            (stock: 42)
  Rs.799.00  Laptop Stand       (stock: 30)

floor (<=Rs.400)   : HDMI Cable
ceiling (>=Rs.400) : USB Hub

=== Descending (most expensive first) ===
  Rs.799.00  Laptop Stand
  Rs.799.00  USB Hub
  Rs.399.00  HDMI Cable
  Rs.299.00  Keyboard Cover
  Rs.199.00  Mouse Pad

Real-World Example — Razorpay Transaction Range Analytics

A payments analytics service at Razorpay needs to answer range-based queries on transaction amounts: total revenue in a price band, nearest transaction amount to a given threshold, transactions above a cutoff, and the highest and lowest recorded amounts. TreeMap handles all of these in one structure without any sorting step or external index.

Java

Try it out

// File: TransactionBucket.java

public record TransactionBucket(
        double minAmount,
        double maxAmount,
        long count,
        double totalRevenue) {

    @Override
    public String toString() {
        return String.format("Rs.%7.2f - Rs.%7.2f | %3d txns | total Rs.%10.2f",
            minAmount, maxAmount, count, totalRevenue);
    }
}

Java

Try it out

// File: TransactionAnalytics.java

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

public class TransactionAnalytics {

    // Key = bucket lower bound, Value = bucket stats
    private final TreeMap<Double, TransactionBucket> buckets = new TreeMap<>();

    public void addBucket(TransactionBucket bucket) {
        buckets.put(bucket.minAmount(), bucket);
    }

    // Find the bucket that contains a given amount
    public TransactionBucket bucketFor(double amount) {
        Map.Entry<Double, TransactionBucket> entry = buckets.floorEntry(amount);
        if (entry == null) return null;
        TransactionBucket bucket = entry.getValue();
        return amount <= bucket.maxAmount() ? bucket : null;
    }

    // Revenue in a price range [from, to] (inclusive)
    public double revenueInRange(double from, double to) {
        NavigableMap<Double, TransactionBucket> range =
            buckets.subMap(from, true, to, true);
        return range.values().stream()
            .mapToDouble(TransactionBucket::totalRevenue)
            .sum();
    }

    // Buckets from a threshold amount upward
    public void printHighValueBuckets(double threshold) {
        System.out.println("  Buckets from Rs." + threshold + " upward:");
        buckets.tailMap(threshold).values()
               .forEach(b -> System.out.println("    " + b));
    }

    public void printReport() {
        System.out.println("=".repeat(72));
        System.out.println("  TRANSACTION BUCKET ANALYSIS");
        System.out.println("=".repeat(72));
        buckets.values().forEach(b -> System.out.println("  " + b));
        System.out.println("-".repeat(72));
        double grandTotal = buckets.values().stream()
            .mapToDouble(TransactionBucket::totalRevenue).sum();
        long totalTxns    = buckets.values().stream()
            .mapToLong(TransactionBucket::count).sum();
        System.out.printf("  TOTAL: %d transactions | Rs.%.2f%n", totalTxns, grandTotal);
        System.out.println("=".repeat(72));
    }

    public static void main(String[] args) {

        TransactionAnalytics analytics = new TransactionAnalytics();

        analytics.addBucket(new TransactionBucket(    0,    500,  2841, 712_650.0));
        analytics.addBucket(new TransactionBucket(  501,  2000,  1520, 1_824_000.0));
        analytics.addBucket(new TransactionBucket( 2001,  5000,   892, 3_123_400.0));
        analytics.addBucket(new TransactionBucket( 5001, 15000,   437, 4_371_000.0));
        analytics.addBucket(new TransactionBucket(15001, 50000,   128, 3_584_000.0));
        analytics.addBucket(new TransactionBucket(50001,100000,    29, 1_885_000.0));

        analytics.printReport();

        System.out.println("\n--- Range queries ---");

        // Revenue between Rs.500 and Rs.15,000
        double rangeRevenue = analytics.revenueInRange(501, 15000);
        System.out.printf("Revenue Rs.500-15000 : Rs.%.2f%n", rangeRevenue);

        // Which bucket handles a Rs.3,200 transaction
        TransactionBucket b = analytics.bucketFor(3200);
        System.out.println("Bucket for Rs.3200   : " + (b != null ? b : "none"));

        // Nearest bucket boundaries around Rs.1,800
        Double floor   = analytics.buckets.floorKey(1800.0);
        Double ceiling = analytics.buckets.ceilingKey(1800.0);
        System.out.println("floorKey(1800)       : Rs." + floor);
        System.out.println("ceilingKey(1800)     : Rs." + ceiling);

        System.out.println();
        analytics.printHighValueBuckets(5001.0);

        System.out.println("\n--- Boundary entries ---");
        System.out.println("Lowest bucket  : " + analytics.buckets.firstEntry().getValue());
        System.out.println("Highest bucket : " + analytics.buckets.lastEntry().getValue());
    }
}

Output:
========================================================================
  TRANSACTION BUCKET ANALYSIS
========================================================================
  Rs.  0.00 - Rs.  500.00 | 2841 txns | total Rs. 712650.00
  Rs.501.00 - Rs. 2000.00 | 1520 txns | total Rs.1824000.00
  Rs.2001.00 - Rs. 5000.00 |  892 txns | total Rs.3123400.00
  Rs.5001.00 - Rs.15000.00 |  437 txns | total Rs.4371000.00
  Rs.15001.00 - Rs.50000.00 |  128 txns | total Rs.3584000.00
  Rs.50001.00 - Rs.100000.00 |   29 txns | total Rs.1885000.00
------------------------------------------------------------------------
  TOTAL: 5847 transactions | Rs.15500050.00
========================================================================

--- Range queries ---
Revenue Rs.500-15000 : Rs.9318400.00
Bucket for Rs.3200   : Rs.2001.00 - Rs. 5000.00 |  892 txns | total Rs.3123400.00
floorKey(1800)       : Rs.501.0
ceilingKey(1800)     : Rs.2001.0

  Buckets from Rs.5001.0 upward:
    Rs.5001.00 - Rs.15000.00 |  437 txns | total Rs.4371000.00
    Rs.15001.00 - Rs.50000.00 |  128 txns | total Rs.3584000.00
    Rs.50001.00 - Rs.100000.00 |   29 txns | total Rs.1885000.00

--- Boundary entries ---
Lowest bucket  : Rs.  0.00 - Rs.  500.00 | 2841 txns | total Rs. 712650.00
Highest bucket : Rs.50001.00 - Rs.100000.00 |   29 txns | total Rs.1885000.00

Performance Considerations

Operation	HashMap	LinkedHashMap	TreeMap
put(k, v)	O(1) avg	O(1) avg	O(log n)
get(k)	O(1) avg	O(1) avg	O(log n)
remove(k)	O(1) avg	O(1) avg	O(log n)
firstKey / lastKey	N/A	N/A	O(log n)
floorKey / ceilingKey	N/A	N/A	O(log n)
headMap / tailMap view	N/A	N/A	O(1) view creation
Iteration	O(n + capacity)	O(n)	O(n) in-order
Memory per entry	~48 bytes	~64 bytes	~56 bytes (tree node)

O(log n) is worst-case bounded: Unlike HashMap where O(1) average can degrade to O(n) on hash collisions (mitigated by Java 8 treeification), TreeMap's O(log n) is an absolute guarantee. For n = 1,000,000 entries, worst-case height is ~40. For n = 1,000,000,000 entries, worst-case is ~60. The Red-Black invariants make this unconditional.

Range view cost: headMap(), tailMap(), and subMap() return SubMap view objects in O(1) — no copying. Iterating k elements within a range is O(k). This is extremely efficient for analytics queries that touch only a fraction of the map.

Thread safety: TreeMap is not thread-safe. For concurrent sorted map access, use ConcurrentSkipListMap from java.util.concurrent — it provides the same NavigableMap interface with O(log n) thread-safe operations and no global lock.

Best Practices

Declare the variable as NavigableMap<K, V> when range methods are needed. NavigableMap<String, Integer> prices = new TreeMap<>() exposes floor(), ceiling(), headMap(), tailMap(), subMap(), and descendingMap(). SortedMap<String, Integer> exposes only headMap(), tailMap(), subMap(), firstKey(), and lastKey(). Map<String, Integer> hides all navigation methods. Declare the narrowest interface that still exposes the methods callers need.

Always include a tiebreaker in the Comparator to prevent silent key collisions. Two keys where compare(a, b) == 0 are treated as the same key — the second put() replaces the first's value. For a TreeMap sorted by price where two products have the same price, only one is stored. Fix this by appending a secondary comparison field — typically a unique ID: Comparator.comparingDouble(Product::price).thenComparing(Product::id). This is the most common TreeMap correctness bug in production code.

Use range views instead of streaming the entire map. map.subMap(from, to) creates a live view in O(1) and iterates only the k matching entries. map.entrySet().stream().filter(e -> e.getKey() >= from && e.getKey() <= to) iterates all n entries. For large maps with narrow range queries, the subMap approach is O(k + log n) versus O(n).

Pre-build as HashMap then convert to TreeMap for one-time sorted output. Building a TreeMap from n individual inserts is O(n log n). Building a HashMap is O(n), then new TreeMap<>(hashMap) sorts all at once — also O(n log n) total, but with lower constant factors because bulk construction can use more efficient tree-building. If sorted output is only needed once, this pattern keeps the accumulation phase at O(1) per entry.

Common Mistakes

Mistake 1 — Missing Tiebreaker Causes Silent Value Overwrite

Java

Try it out

// WRONG — two products at the same price: second overwrites first
Comparator<Product> byPriceOnly = Comparator.comparingDouble(Product::getPrice);
TreeMap<Product, String> map = new TreeMap<>(byPriceOnly);

map.put(new Product("A", 599.0), "ProductA");
map.put(new Product("B", 599.0), "ProductB"); // compare returns 0 — treated as same key!

System.out.println(map.size()); // 1 — ProductA is gone!

// CORRECT — always add a tiebreaker
Comparator<Product> byPriceThenId =
    Comparator.comparingDouble(Product::getPrice)
              .thenComparing(Product::getId);
TreeMap<Product, String> safeMap = new TreeMap<>(byPriceThenId);
safeMap.put(new Product("A", 599.0), "ProductA");
safeMap.put(new Product("B", 599.0), "ProductB");
System.out.println(safeMap.size()); // 2 — both stored

Mistake 2 — Inserting null Keys

Java

Try it out

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Alpha", 1);

// WRONG — TreeMap calls compareTo() which throws on null
map.put(null, 2); // NullPointerException

// CORRECT — for null-tolerant sorted maps, use a null-accepting Comparator
TreeMap<String, Integer> nullable = new TreeMap<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
nullable.put(null, 2);   // null placed before all non-null keys
nullable.put("Alpha", 1);
System.out.println(nullable); // {null=2, Alpha=1}

Mistake 3 — Iterating a Range View While Modifying Its Bounds

Java

Try it out

TreeMap<Integer, String> scores = new TreeMap<>();
for (int i = 1; i <= 10; i++) scores.put(i * 100, "Score-" + i);

// Range view [300, 700]:
java.util.SortedMap<Integer, String> view = scores.subMap(300, 700);

// WRONG — inserting a key outside the view's range through the view throws
// IllegalArgumentException. Inserting through the BACKING map is fine but
// may or may not appear in the view depending on whether the key is in range.
try {
    view.put(800, "Score-Out"); // 800 is outside [300, 700) — throws
} catch (IllegalArgumentException e) {
    System.out.println("Exception: key outside subMap bounds");
}

// CORRECT — insert through backing map; appears in view only if in range
scores.put(500, "Score-5-updated"); // within range — visible through view
scores.put(800, "Score-8");         // outside range — not visible through view

Output:
Exception: key outside subMap bounds

Mistake 4 — Using TreeMap When HashMap Performance Is Needed

Java

Try it out

// WRONG for high-throughput lookups — O(log n) TreeMap instead of O(1) HashMap
// Processing 10 million events with a map lookup per event:
// HashMap: ~10ms; TreeMap: ~200ms — 20x difference at scale
TreeMap<String, UserProfile> userCache = new TreeMap<>();

// CORRECT — HashMap for pure key-value lookup at scale
Map<String, UserProfile> userCache2 = new HashMap<>();

// Use TreeMap ONLY when sorted iteration or range navigation is genuinely needed.
// If you only call get() and put(), HashMap is always the right choice.

Interview Questions

Q1. What is TreeMap in Java and how does it differ from HashMap?

TreeMap is a NavigableMap implementation backed by a Red-Black self-balancing binary search tree. It stores entries in ascending key order — natural ordering via Comparable or a supplied Comparator. HashMap uses a hash table, provides O(1) average put() and get(), but guarantees no iteration order. TreeMap provides O(log n) guaranteed for all operations and always iterates in sorted key order. TreeMap also adds the full NavigableMap API — floorKey(), ceilingKey(), headMap(), tailMap(), subMap() — which HashMap has no equivalent for.

Q2. How does TreeMap determine duplicate keys?

TreeMap uses compareTo() (natural ordering) or the Comparator for all comparisons — it never calls equals() or hashCode(). Two keys where compare(a, b) == 0 are treated as identical: the second put() replaces the value without creating a new tree node. This means a class can have equals() returning false for two objects while compareTo() returns 0 — TreeMap still treats them as the same key. This is why the Comparator must include a tiebreaker field (unique ID, timestamp) when the primary sort field is not unique.

Q3. What is the time complexity of TreeMap operations and why is it always O(log n)?

All TreeMap operations — put(), get(), remove(), firstKey(), lastKey(), floorKey(), ceilingKey() — are O(log n) in both average and worst case. This is guaranteed by the Red-Black tree's self-balancing invariants, which bound the tree height at 2 × log₂(n+1) regardless of insertion order. For 1,000,000 entries, every operation traverses at most ~40 nodes. This contrasts with HashMap's O(1) average that can degrade to O(n) on hash collisions (mitigated in Java 8 by treeification, but not eliminated).

Q4. What is the difference between headMap(), tailMap(), and subMap()?

All three return live NavigableMap view objects — no copying. headMap(toKey) returns all entries with keys strictly less than toKey (exclusive); the overloaded headMap(toKey, inclusive) controls the boundary. tailMap(fromKey) returns all entries with keys greater than or equal to fromKey (inclusive by default). subMap(from, to) returns entries with keys in [from, to) — from inclusive, to exclusive by default; the four-argument overload controls both boundaries. Modifications through any view are immediately reflected in the backing TreeMap. Adding a key outside a view's bounds throws IllegalArgumentException.

Q5. Why can't TreeMap have null keys?

TreeMap determines every key's position using compareTo() or the Comparator. Calling compareTo(null) on any object throws NullPointerException — the Java specification requires this. Since TreeMap must compare every new key with existing keys to find its tree position, null cannot be placed anywhere. HashMap can store one null key by placing it in bucket 0 and bypassing hashCode(). If null-tolerant sorted maps are needed, pass Comparator.nullsFirst(Comparator.naturalOrder()) to the TreeMap constructor.

Q6. When would you choose TreeMap over a sorted ArrayList of Map.Entry objects?

TreeMap maintains sorted order on every put() and remove() in O(log n). A sorted ArrayList requires Collections.sort() after each insertion — O(n log n) per sort — and O(n) for remove() by key (binary search finds position, shifting fills the gap). containsKey() on ArrayList is O(n); TreeMap.get() is O(log n). TreeMap also provides floorKey(), ceilingKey(), and range views — none of which ArrayList supports natively. For any use case with frequent insertions, deletions, and key-based lookups, TreeMap is strictly superior to a manually maintained sorted list.

FAQs

Does TreeMap allow duplicate keys?

No. When compare(a, b) == 0, TreeMap treats a and b as the same key and replaces the existing value. This is determined purely by the Comparator or compareTo() — not by equals(). Two objects can be logically different (by equals()) but treated as duplicates by TreeMap if the comparison returns 0 without a tiebreaker field.

What is the difference between TreeMap and TreeSet?

TreeSet is backed by a TreeMap where elements become keys and a shared static PRESENT object is the value. Everything about TreeMap's Red-Black tree, O(log n) operations, null rejection, and NavigableSet API (which parallels NavigableMap) applies directly to TreeSet. Use TreeMap when each key has an associated value to retrieve; use TreeSet for pure membership testing with sorted unique elements.

How do I create a TreeMap in reverse sorted order?

Pass Comparator.reverseOrder() for natural reverse ordering: new TreeMap<>(Comparator.reverseOrder()). For custom reverse ordering: myComparator.reversed(). This creates a max-first tree where firstKey() returns the largest key and lastKey() returns the smallest. descendingMap() provides a reverse-order view of an existing TreeMap without creating a new map.

Is TreeMap thread-safe?

No. Concurrent modifications from multiple threads can corrupt the tree structure. For concurrent sorted maps, use ConcurrentSkipListMap from java.util.concurrent, which implements ConcurrentNavigableMap — the full NavigableMap interface with O(log n) thread-safe operations including floorKey(), ceilingKey(), and all range views.

What is ConcurrentSkipListMap and when should it replace TreeMap?

ConcurrentSkipListMap is a thread-safe sorted map backed by a skip list (probabilistic data structure providing O(log n) expected performance). It supports the full NavigableMap interface without any external synchronisation. Use it when multiple threads need concurrent read and write access to a sorted map. TreeMap with Collections.synchronizedSortedMap() exists but holds a single lock — only one thread accesses the map at a time. ConcurrentSkipListMap allows fine-grained concurrent access at much higher throughput.

What happens if the compareTo() method is inconsistent with equals()?

TreeMap's behaviour becomes inconsistent with the Map contract. The general Map contract defines key uniqueness by equals(). If compareTo() returns 0 for two keys where equals() returns false, TreeMap treats them as one key while a HashMap would treat them as two. BigDecimal is the standard Java example: new BigDecimal("2.0").compareTo(new BigDecimal("2.00")) == 0 but equals() returns false. In a TreeMap<BigDecimal, V>, only one of them can be stored. The Java documentation recommends making compareTo() consistent with equals() for SortedMap keys.

Summary

TreeMap<K, V> is Java's sorted map — O(log n) for every operation, guaranteed by Red-Black tree invariants that bound height at 2 × log₂(n+1). Keys are always maintained in ascending order, and the full NavigableMap API — floorKey(), ceilingKey(), headMap(), tailMap(), subMap(), descendingMap() — enables range queries and nearest-key navigation that no hash-based collection provides.

Two rules prevent the most common TreeMap bugs: always include a tiebreaker in the Comparator when the primary sort field is not unique (equal keys silently overwrite), and never insert null keys (compareTo throws). Range views are live and O(1) to create — use subMap() for range queries instead of streaming and filtering the entire map.

For interviews: explain the Red-Black tree structure and O(log n) guarantee, describe how duplicates are detected via compareTo() not equals(), walk through the NavigableMap method set, explain why null keys throw, and distinguish TreeMap from ConcurrentSkipListMap for concurrent use. These questions appear consistently from fresher campus rounds through senior engineering interviews.

What to Read Next

Continue Learning Collections Framework

Next Step

ConcurrentHashMap

Learn a HashMap that's safe to use across multiple threads.

→

Lower-Bounded Wildcards (? super)

Learn how to accept a type or any of its superclasses.

→

Comparable vs Comparator

See when to use Comparable instead of Comparator.

→

Collections Overview

Get an overview of Java's built-in data structures.

→

←

PreviousLinkedHashMap

NextConcurrentHashMap

→