Range queries with TreeMap
Range queries with TreeMap, NavigableMap predecessor and successor methods, live range views, time windows, booking conflicts, nearest slots, order books, duplicates, concurrency and complexity trade-offs.
On this page
- Picture it first: keys on a number line
- NavigableMap under the hood: pick the exact method
- Live views: useful, sharp and not snapshots
- Sliding time windows
- Booking conflicts with floorEntry and ceilingEntry
- Order books, leaderboards and descending views
- Advanced: limits, duplicates and when not to use it
- How to say it in the interview
🧭 What are range queries with TreeMap?
A range query asks about ordered keys, not just one exact key: the nearest price below 108, all events between 10:00 and 10:05, or whether a new meeting overlaps an existing one. TreeMap is useful here because it keeps keys sorted and implements NavigableMap, so it can jump to predecessor, successor and bounded views in O(log n) time. Think of it like a street with house numbers in order: if you are standing at 45, you can quickly find the closest house before you, the closest after you, or every house on one block.
For this lesson, we'll focus on the range-query playbook: recognition clues, NavigableMap methods, live range views, time windows, booking conflicts, nearest-slot lookup, order-book shape, duplicate keys, count-in-range limitations and concurrency. We will not re-explain red-black tree rotations or comparator rules here. If you need that foundation, read TreeMap and red-black trees first.
Below the line (out of scope)
- Red-black tree internals and comparator equality traps: TreeMap and red-black trees
- Exact lookup and hash-table trade-offs: How HashMap works
- Concurrent map choices, including
ConcurrentSkipListMap: Hashtable, synchronizedMap and the concurrent maps - This lesson treats interval booking at the data-structure level, not time-zone policy, recurrence rules or distributed locking.
The 30-second answer
Use TreeMap when the prompt needs sorted-key navigation: nearest, previous, next, at most, at least, between, sliding time window, intervals, bookings or price levels. floorEntry(k) gives the greatest key <= k, ceilingEntry(k) gives the least key >= k, lowerEntry(k) and higherEntry(k) are strict versions, and subMap, headMap and tailMap give bounded views with explicit inclusive flags. Core navigation, put and remove are O(log n), then iterating a range is O(k) for k returned entries. Range views are live write-through views, so headMap(cutoff).clear() deletes from the original map, and putting a key outside a subMap throws IllegalArgumentException. Use HashMap for exact lookup only, a sorted array plus Arrays.binarySearch for static data, and ConcurrentSkipListMap when multiple threads need sorted range access.
What you’ll learn
- Recognize range-query clues such as nearest, at most, at least, between, sliding windows, intervals and booking conflicts
- Choose the right
NavigableMapmethod:floor,ceiling,lower,higher,headMap,tailMapandsubMap - Explain why
TreeMaprange views are live write-through views, not snapshots - Implement time-window cleanup with
headMap(cutoff).clear()and handle duplicate timestamps safely - Solve booking overlap checks with
floorEntryandceilingEntry, including endpoint conventions - State the count-in-range limitation:
subMap(...).size()is O(k), so use a Fenwick tree or order-statistic tree when counts dominate - Know when not to use
TreeMap: exact lookups only, static sorted data, or concurrent access withoutConcurrentSkipListMap
Interview radar
Asked often: My Calendar I, nearest available slot, values in the last N minutes, order-book price levels.
Senior rounds probe: endpoint inclusivity, duplicate timestamps, live views, count-in-range complexity and concurrent updates.
Common trap: treating subMap(...).size() like an O(log n) count query. It is not.
01Picture it first: keys on a number line
Let's get the picture right first. A TreeMap is not a bucket table that happens to print nicely. It is an ordered index, so every operation has a direction: closest key on the left, closest key on the right, or a slice between two boundaries.
The diagram uses four stored keys and a query at 45. The map can jump to the neighbors without scanning all keys. A bounded range still has to be walked entry by entry once you ask for the contents.
A number line showing TreeMap keys, a query at 45, floor and ceiling neighbors, and a subMap window from 20 to 60
Recognition clues are the part I want you to train. When the prompt says nearest, at most, at least, between, last five minutes, interval, booking, next available or price ladder, you should at least consider NavigableMap. It may not be the final answer, but it belongs in the conversation.
02NavigableMap under the hood: pick the exact method
Premium lesson
Keep reading with the Java Pass
The rest of this lesson is part of Java One-Stop Interview Prep: in-depth explanations, diagrams, model answers and how to say them in the interview.
- Live views: useful, sharp and not snapshots
- Sliding time windows
- Booking conflicts with floorEntry and ceilingEntry
- Order books, leaderboards and descending views
- Advanced: limits, duplicates and when not to use it
- How to say it in the interview
From ₹199 · one-time payment · No auto-renewal