Course contentsShow
← Java
Lesson 999 of 2,87023. Collections Framework OverviewFree lesson

TreeMap: Sorted Map with Ordered Keys

Learn how TreeMap maintains keys in sorted order with log(n) operations using a red-black tree structure.

TreeMap: Sorted Map with Ordered Keys

You'll learn how TreeMap keeps your key-value pairs automatically sorted, making range queries and ordered traversal efficient.

What Is TreeMap?

While HashMap offers lightning-fast lookups through hashing, TreeMap provides something different: keys that are always kept in sorted order. This comes at a small performance cost, but unlocks powerful ordering capabilities.

How TreeMap Works Internally

TreeMap uses a red-black tree — a self-balancing binary search tree structure. Think of it like a library that doesn't just store books randomly, but arranges them alphabetically on shelves so you can quickly find any book and easily browse all books in order.

Because of this tree structure, TreeMap operations (put, get, remove) run in O(log n) time rather than HashMap's O(1). With 1,000 entries, a tree lookup takes about 10 steps instead of 1. That's the trade-off for maintaining sorted order.

When TreeMap Shines

Use TreeMap when you need:

  • Keys automatically sorted (by natural ordering or custom comparator)
  • Range operations: "Give me all entries between key A and key B"
  • First/last key access
  • Ordered iteration over entries

The keys stay sorted whether you insert them randomly or in reverse order — TreeMap handles the organization for you.

The Performance Trade-Off

HashMap: O(1) operations, no ordering
TreeMap: O(log n) operations, keys always sorted

For small to medium collections (hundreds or even thousands of entries), the log(n) difference is negligible. Choose TreeMap when you need the ordering guarantees it provides.

Key Takeaway: TreeMap maintains keys in sorted order using a red-black tree structure, offering O(log n) operations — slightly slower than HashMap but enabling powerful ordered access patterns and range queries.