Java

TreeMap and NavigableMap

June 10, 2026 at 07:19 AM
18 min reading
3 views

Master sorted key-value storage with TreeMap. Learn Red-Black tree fundamentals, NavigableMap operations for range queries, and real-world patterns for time-series data, autocomplete, and interval lookups.

📋 At a Glance

AspectDetails
TopicTreeMap, NavigableMap, SortedMap, Red-Black Trees
ComplexityIntermediate to Advanced
PrerequisitesPart 10 (TreeSet), Part 12 (HashMap)
Time to Master3-4 hours
Interview FrequencyHigh (NavigableMap operations, tree complexity)

🎯 What You'll Learn

After completing this article, you will be able to:

  1. Understand TreeMap's Red-Black tree implementation
  2. Use NavigableMap operations for range and proximity queries
  3. Implement time-series data handling with subMap
  4. Build autocomplete functionality with prefix matching
  5. Choose between TreeMap and HashMap for different use cases

Production Story: Time-Series Analytics Without a Time-Series Database

The Incident

Our analytics service needed to answer queries like "Show me all events between 10am and 2pm" with sub-millisecond response times. The initial implementation used HashMap and filtered all events:

JAVA(11 lines)
Code
Loading syntax highlighter...

With 10 million events, this query took 500ms - unacceptable for real-time dashboards.

The TreeMap Solution

JAVA(23 lines)
Code
Loading syntax highlighter...
Performance improvement:
  • Before: O(n) = 500ms for 10M events
  • After: O(log n + k) = 0.5ms for same data
  • 1000x faster!

How TreeMap Makes This Possible

TEXT(23 lines)
Code
Loading syntax highlighter...

Lessons Learned

  1. TreeMap excels at range queries - O(log n) to find boundaries
  2. HashMap excels at point queries - O(1) for exact key lookup
  3. Choose data structure based on query patterns, not just storage needs
  4. NavigableMap API provides powerful range operations

Mental Model: The Sorted Filing Cabinet

Think of TreeMap as a filing cabinet where folders are always in order:

TEXT(23 lines)
Code
Loading syntax highlighter...

Deep Dive: TreeMap Internals

Red-Black Tree Structure

JAVA(16 lines)
Code
Loading syntax highlighter...

Visual Tree Example

TEXT(17 lines)
Code
Loading syntax highlighter...

TreeMap Construction

JAVA(24 lines)
Code
Loading syntax highlighter...

Deep Dive: NavigableMap Operations

Entry Navigation Methods

JAVA(29 lines)
Code
Loading syntax highlighter...

Submap Views

JAVA(20 lines)
Code
Loading syntax highlighter...

Views Are Live!

JAVA(16 lines)
Code
Loading syntax highlighter...

Descending Views

JAVA(14 lines)
Code
Loading syntax highlighter...

Deep Dive: Real-World Patterns

Pattern 1: Time-Series Data

JAVA(33 lines)
Code
Loading syntax highlighter...
JAVA(32 lines)
Code
Loading syntax highlighter...

Pattern 3: Interval/Range Lookup

JAVA(27 lines)
Code
Loading syntax highlighter...

Pattern 4: Sliding Window

JAVA(34 lines)
Code
Loading syntax highlighter...

Deep Dive: Performance Characteristics

Operation Complexity

OperationTreeMapHashMap
get(key)O(log n)O(1)
put(key, value)O(log n)O(1)*
remove(key)O(log n)O(1)
containsKey(key)O(log n)O(1)
firstKey()/lastKey()O(log n)N/A
floorKey()/ceilingKey()O(log n)N/A
subMap()O(log n)N/A
IterationO(n) sortedO(n) unsorted

*O(1) amortized, O(n) worst case during resize

When to Use TreeMap

JAVA(23 lines)
Code
Loading syntax highlighter...

When to Use HashMap

JAVA(12 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Missing Comparable/Comparator

JAVA(21 lines)
Code
Loading syntax highlighter...

Mistake 2: Inconsistent compareTo and equals

JAVA(28 lines)
Code
Loading syntax highlighter...

Mistake 3: Modifying Keys After Insertion

JAVA(14 lines)
Code
Loading syntax highlighter...

Mistake 4: SubMap Range Violations

JAVA(12 lines)
Code
Loading syntax highlighter...

Mistake 5: Null Keys

JAVA(13 lines)
Code
Loading syntax highlighter...

🐛 Debug This

Challenge 1: The Missing Entry

JAVA(8 lines)
Code
Loading syntax highlighter...
✅ Answer:
Output is unpredictable! Double.NaN violates comparison contract because NaN.compareTo(x) is always inconsistent (NaN is not equal to anything, including itself).

The tree structure becomes corrupted. You might get wrong results or exceptions.

Fix: Never use NaN as a TreeMap key.

Challenge 2: The Overwritten Entry

JAVA(13 lines)
Code
Loading syntax highlighter...
✅ Answer:

Output:

TEXT(2 lines)
Code
Loading syntax highlighter...
Both keys have name "Alice", so compareTo returns 0. TreeMap considers them equal and overwrites the first entry. The id field is ignored because it's not in compareTo.

Challenge 3: The Submap Surprise

JAVA(9 lines)
Code
Loading syntax highlighter...
✅ Answer:
Output: {1=v1, 2=v2, 8=v8, 9=v9, 10=v10}

The submap is a live view. Clearing it removes entries 3-7 from the original map!

💻 Exercises

Exercise 1: Price Band Lookup

Implement a price band system that returns the discount for a given order amount:

JAVA(4 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(15 lines)
Code
Loading syntax highlighter...

Exercise 2: Version Range Finder

Implement a system that finds the latest compatible version:

JAVA(6 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(24 lines)
Code
Loading syntax highlighter...

Exercise 3: Rate Limiter with Time Windows

Implement a rate limiter using TreeMap:

JAVA(5 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(40 lines)
Code
Loading syntax highlighter...

Exercise 4: Calendar Event Finder

Implement a calendar that finds events overlapping with a time range:

JAVA(5 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(29 lines)
Code
Loading syntax highlighter...

Implement a 1D nearest neighbor search:

JAVA(5 lines)
Code
Loading syntax highlighter...
✅ Solution:
JAVA(34 lines)
Code
Loading syntax highlighter...

🎤 Senior-Level Interview Questions

Question 1: TreeMap vs HashMap Performance

Q: When would you choose TreeMap over HashMap despite the O(log n) vs O(1) difference?
A:

Choose TreeMap when:

  1. Range queries needed: subMap, headMap, tailMap are O(log n) in TreeMap, require O(n) scan in HashMap
  2. Sorted iteration: TreeMap iterates in key order naturally
  3. Proximity queries: floorKey, ceilingKey have no HashMap equivalent
  4. First/last access: firstKey, lastKey are O(log n)
JAVA(7 lines)
Code
Loading syntax highlighter...

Question 2: Red-Black Tree Properties

Q: Why does TreeMap use a Red-Black tree instead of an AVL tree?
A:

Red-Black trees have:

  1. Faster insertion/deletion: Fewer rotations needed (at most 2 rotations per operation vs O(log n) for AVL)
  2. Slightly slower lookup: AVL is more strictly balanced
  3. Better for modification-heavy workloads: Java collections often modify frequently

Trade-off: Red-Black trees have height up to 2*log(n), AVL trees have height exactly log(n). This means RB lookups can be up to 2x slower in worst case, but modifications are faster.

Question 3: NavigableMap Memory Views

Q: Are NavigableMap submaps views or copies? What are the implications?
A:
They are views backed by the original map:
JAVA(16 lines)
Code
Loading syntax highlighter...

Question 4: TreeMap Comparator Consistency

Q: What happens if compareTo/Comparator is inconsistent with equals?
A:

TreeMap uses compareTo for all key equality, ignoring equals():

JAVA(17 lines)
Code
Loading syntax highlighter...

Question 5: Submap Thread Safety

Q: If you create a submap view and another thread modifies the original map, what happens?
A:

TreeMap (and its views) are not thread-safe:

JAVA(17 lines)
Code
Loading syntax highlighter...

Question 6: Ceiling vs Floor Use Cases

Q: Give a real-world example where you'd use ceilingEntry vs floorEntry.
A:
JAVA(13 lines)
Code
Loading syntax highlighter...

📝 Summary & Key Takeaways

TreeMap Fundamentals

  • Red-Black tree: O(log n) for all operations
  • Keys must be Comparable or provide Comparator
  • No null keys (usually), null values allowed
  • Sorted iteration order
  • floorEntry/ceilingEntry: Closest match ≤ / ≥
  • lowerEntry/higherEntry: Strictly < / >
  • subMap/headMap/tailMap: Range views (live!)
  • descendingMap: Reverse order view

Performance Trade-offs

  • TreeMap: O(log n) everything, sorted, range queries
  • HashMap: O(1) point operations, unsorted, no ranges
  • Choose based on query patterns, not just storage

Common Patterns

  • Time-series: subMap for time ranges
  • Autocomplete: subMap for prefix matching
  • Price bands: floorEntry for threshold lookup
  • Nearest neighbor: floor + ceiling comparison

🏁 Conclusion

TreeMap is the go-to collection when you need sorted key-value storage with range query capabilities. The NavigableMap interface provides elegant solutions to problems that would require complex code with HashMap.

Key takeaways:

  1. TreeMap excels at range queries - O(log n) vs O(n) for HashMap
  2. NavigableMap operations are powerful - floor, ceiling, subMap enable elegant solutions
  3. Views are live - changes propagate bidirectionally
  4. compareTo consistency matters - TreeMap ignores equals()
  5. Use HashMap for point queries - when you don't need sorting or ranges

In the next article, we'll explore LinkedHashMap - the hybrid that combines HashMap's O(1) performance with predictable iteration order, plus the secret to implementing LRU caches.

📅 Review Schedule

To solidify your understanding, review this material:

  • Tomorrow: Re-read NavigableMap operations section
  • In 3 days: Implement Exercise 3 (Rate Limiter) again
  • In 1 week: Explain TreeMap vs HashMap trade-offs to a colleague
  • In 2 weeks: Review the time-series production story
Next in Series: Part 15: LinkedHashMap & LRU Cache
Series Navigation: Part 0: How to Use This Series | Full Index

Tags:

JavaRed-black TreeTreemapNavigablemapSortedmap
Last updated: June 10, 2026 at 11:12 AM