How does TreeMap maintain sorted keys?

Q: How does TreeMap maintain sorted keys?

TreeMap uses a RedBlack tree internally. Every node stores a keyvalue pair, a reference to left and right children, a parent reference, and a color (red or black). The tree maintains the invariant that all keys in the left subtree are less than the node's key, and all keys in the right subtree are g

Q: What are common mistakes?

// TreeMap uses compareTo for equality, not equals! // If a.compareTo(b) == 0 but !a.equals(b): // TreeMap treats them as the SAME key (overwrite) // HashMap treats them as DIFFERENT keys // Always keep compareTo consistent with equals TreeMap<String, String map = new TreeMap<(); map.put("A", "1");

Q: What should a senior engineer know?

RedBlack tree guarantees. The tree is always balanced within a factor of 2: the longest path from root to leaf is at most twice the shortest. This guarantees O(log n) worst case, unlike a BST which can degrade to O(n). ConcurrentSkipListMap. The threadsafe equivalent of TreeMap. Uses a skip list (pr

Q: What are common interview follow-up questions?

"What is the internal data structure of TreeMap?" – RedBlack tree. "What happens if the key class does not implement Comparable?" – ClassCastException on the second put. "What is the time complexity of TreeMap.get?" – O(log n). "Does TreeMap allow null keys?" – No (compareTo throws NPE).

Definition

TreeMap keeps keys sorted using a Red-Black tree; keys must implement Comparable or a Comparator must be provided, otherwise ClassCastException is thrown on the second put.

Internal structure: Red-Black tree – a self-balancing binary search tree that guarantees O(log n) for get, put, and remove
Natural ordering: keys implement Comparable, and TreeMap uses key.compareTo(otherKey) for ordering
Custom ordering: pass a Comparator to the constructor: new TreeMap<>(comparator)
ClassCastException: if keys do not implement Comparable and no Comparator is provided, put() fails when comparing the second key to the first
NavigableMap: provides range operations: firstKey, lastKey, floorKey, ceilingKey, subMap, headMap, tailMap

TreeMap is an alphabetically sorted filing system. Every folder has a label, and the system places each folder in the correct alphabetical position. To do this, the system must be able to compare any two labels. If the labels are in a language the system does not understand (no Comparable, no Comparator), it cannot sort them and throws an error.

Understanding the Concepts

TreeMap uses a Red-Black tree internally. Every node stores a key-value pair, a reference to left and right children, a parent reference, and a color (red or black). The tree maintains the invariant that all keys in the left subtree are less than the node's key, and all keys in the right subtree are greater.

JAVA

package com.bank.demo;

import java.math.BigDecimal;
import java.util.*;

public class TreeMapSortedDemo {
    public static void main(String[] args) {
        // String implements Comparable → natural alphabetical order
        TreeMap<String, BigDecimal> accounts = new TreeMap<>();
        accounts.put("SAV2001", new BigDecimal("150000"));
        accounts.put("CUR3001", new BigDecimal("75000"));
        accounts.put("FD4001", new BigDecimal("500000"));
        accounts.put("LON5001", new BigDecimal("200000"));

        // Iteration: always sorted by key
        System.out.println("Sorted accounts:");
        accounts.forEach((id, balance) ->
            System.out.println("  " + id + ": " + balance));

        // NavigableMap operations
        System.out.println("\nFirst: " + accounts.firstKey());
        System.out.println("Last: " + accounts.lastKey());
        System.out.println("Before 'G': " + accounts.lowerKey("G"));
        System.out.println("After 'G': " + accounts.higherKey("G"));
    }
}

TEXT

Sorted accounts:
  CUR3001: 75000
  FD4001: 500000
  LON5001: 200000
  SAV2001: 150000

First: CUR3001
Last: SAV2001
Before 'G': FD4001
After 'G': LON5001

What happens without Comparable or Comparator?

If you use a custom class that does not implement Comparable and do not provide a Comparator, TreeMap throws ClassCastException on the second put() call. The first put succeeds because there is nothing to compare with (it becomes the root).

JAVA

package com.bank.demo;

import java.util.*;

public class ClassCastExceptionDemo {
    // Does NOT implement Comparable
    static class Account {
        String id;
        Account(String id) { this.id = id; }
    }

    public static void main(String[] args) {
        TreeMap<Account, String> map = new TreeMap<>();

        // First put: succeeds (nothing to compare with)
        map.put(new Account("SAV2001"), "Rajesh");
        System.out.println("First put succeeded");

        // Second put: ClassCastException!
        try {
            map.put(new Account("CUR3001"), "Priya");
        } catch (ClassCastException e) {
            System.out.println("Second put: " + e.getMessage());
        }

        // FIX: provide a Comparator
        TreeMap<Account, String> fixed = new TreeMap<>(
            Comparator.comparing(a -> a.id)
        );
        fixed.put(new Account("SAV2001"), "Rajesh");
        fixed.put(new Account("CUR3001"), "Priya");
        System.out.println("Fixed: " + fixed.size() + " entries");
    }
}

TEXT

First put succeeded
Second put: class Account cannot be cast to class java.lang.Comparable
Fixed: 2 entries

How do you use TreeMap with custom objects?

Two approaches: implement Comparable in the class, or pass a Comparator to TreeMap.

JAVA

package com.bank.model;

import java.math.BigDecimal;
import java.util.*;

// Approach 1: Implement Comparable
record Trade(String tradeId, java.time.LocalDate date, BigDecimal amount)
    implements Comparable<Trade> {

    @Override
    public int compareTo(Trade other) {
        return this.date.compareTo(other.date); // sort by date
    }
}

public class TreeMapCustomKeyDemo {
    public static void main(String[] args) {
        // Approach 1: Comparable key
        TreeMap<Trade, String> byDate = new TreeMap<>();
        byDate.put(new Trade("T1", java.time.LocalDate.of(2024, 3, 15), new BigDecimal("50000")), "Executed");
        byDate.put(new Trade("T2", java.time.LocalDate.of(2024, 1, 10), new BigDecimal("75000")), "Settled");
        System.out.println("By date: " + byDate.keySet());

        // Approach 2: Comparator
        TreeMap<Trade, String> byAmount = new TreeMap<>(
            Comparator.comparing(Trade::amount).reversed()
        );
        byAmount.putAll(byDate);
        System.out.println("By amount desc: " + byAmount.keySet());
    }
}

TEXT

By date: [Trade[tradeId=T2, date=2024-01-10, amount=75000], Trade[tradeId=T1, date=2024-03-15, amount=50000]]
By amount desc: [Trade[tradeId=T2, date=2024-01-10, amount=75000], Trade[tradeId=T1, date=2024-03-15, amount=50000]]

What are the NavigableMap range operations?

DIAGRAM

| Method | Returns |
|---|---|
| firstKey() / firstEntry() | Smallest key/entry |
| lastKey() / lastEntry() | Largest key/entry |
| lowerKey(k) | Greatest key strictly < k |
| floorKey(k) | Greatest key <= k |
| ceilingKey(k) | Smallest key >= k |
| higherKey(k) | Smallest key strictly > k |
| subMap(from, to) | View of keys in [from, to) |
| headMap(to) | View of keys < to |
| tailMap(from) | View of keys >= from |
| descendingMap() | Reverse-order view |
| pollFirstEntry() | Remove and return smallest |
| pollLastEntry() | Remove and return largest |

What are common mistakes?

Mistake 1: Inconsistent compareTo and equals

JAVA

// TreeMap uses compareTo for equality, not equals!
// If a.compareTo(b) == 0 but !a.equals(b):
// TreeMap treats them as the SAME key (overwrite)
// HashMap treats them as DIFFERENT keys
// Always keep compareTo consistent with equals

Mistake 2: Forgetting that subMap returns a view

JAVA

TreeMap<String, String> map = new TreeMap<>();
map.put("A", "1"); map.put("B", "2"); map.put("C", "3");

var sub = map.subMap("A", "C"); // view: {A=1, B=2}
sub.put("A2", "1.5"); // modifies the ORIGINAL map!
System.out.println(map); // {A=1, A2=1.5, B=2, C=3}

What should a senior engineer know?

- Red-Black tree guarantees. The tree is always balanced within a factor of 2: the longest path from root to leaf is at most twice the shortest. This guarantees O(log n) worst case, unlike a BST which can degrade to O(n).

- ConcurrentSkipListMap. The thread-safe equivalent of TreeMap. Uses a skip list (probabilistic balancing) instead of a Red-Black tree. Supports NavigableMap and ConcurrentMap.

- compareTo must be total. The Comparator or Comparable must define a total ordering: every pair of elements must be comparable. Returning 0 only for truly equal elements.

What are common interview follow-up questions?

"What is the internal data structure of TreeMap?" – Red-Black tree.
"What happens if the key class does not implement Comparable?" – ClassCastException on the second put.
"What is the time complexity of TreeMap.get?" – O(log n).
"Does TreeMap allow null keys?" – No (compareTo throws NPE).

Visual Overview

DIAGRAM

  TreeMap internal Red-Black tree

  Keys: CUR3001, FD4001, LON5001, SAV2001

              FD4001 (B)
             /         \
     CUR3001 (R)    SAV2001 (B)
                    /
             LON5001 (R)

  get("LON5001"): root → right → left → found! (3 comparisons = O(log 4))

  ClassCastException scenario:
  put(key1) → root (no comparison needed)
  put(key2) → compare key2 to key1
             → key1 not Comparable → ClassCastException!

  Fix: new TreeMap<>(Comparator.comparing(Key::field))

Key Takeaway

TreeMap keeps keys sorted using a Red-Black tree, guaranteeing O(log n) for all operations. Keys must implement Comparable or a Comparator must be provided at construction time. Without either, the second put throws ClassCastException because TreeMap cannot compare the new key against the existing root.

TreeMap's NavigableMap interface provides powerful range operations: firstKey, lastKey, floorKey, ceilingKey, subMap, headMap, and tailMap. These make it ideal for time-series data, sorted reports, and range queries.

In the National Bank of India's trade reporting system, Rajesh uses TreeMap for daily transaction totals. The NavigableMap lets him query "total transactions from January 10 to January 20" with subMap(jan10, true, jan20, true) in O(log n) time.

Remember one sentence: TreeMap sorts keys with a Red-Black tree and requires Comparable or a Comparator – without either, the second put throws ClassCastException.

---