Java TreeMap lowerEntry: Find the Predecessor Entry

java treemap lowerentry requires a clear understanding of the core syntax, runtime behavior, and practical implementation patterns demonstrated in the examples below.

The lowerEntry(K key) method in java.util.TreeMap returns the key-value mapping associated with the greatest key strictly less than the given key, or null if no such key exists. This navigation method is part of the NavigableMap interface and is useful whenever you need to find the predecessor of a key in a sorted map.

How lowerEntry Works

lowerEntry performs a binary search on the red-black tree that backs TreeMap. It compares the given key with the keys in the tree and returns the entry whose key is the maximum among all keys that are strictly less than the input key. The method signature is:

Map.Entry<K, V> lowerEntry(K key)

The method returns null when the map is empty or when there is no key in the map that is strictly less than the given key. For example, if the smallest key in the map is 5 and you call lowerEntry(5), the result is null because there is no key less than 5.

Example: Finding the Predecessor Entry

Consider a TreeMap that maps integer scores to player names. To find the player with the highest score that is still below a certain threshold, lowerEntry is the right tool.

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

public class ScoreLookup {
    public static void main(String[] args) {
        TreeMap<Integer, String> scores = new TreeMap<>();
        scores.put(85, "Alice");
        scores.put(92, "Bob");
        scores.put(77, "Carol");
        scores.put(88, "David");

        Map.Entry<Integer, String> entry = scores.lowerEntry(90);
        if (entry != null) {
            System.out.println("Highest score below 90: " + entry.getKey() + " -> " + entry.getValue());
        } else {
            System.out.println("No score below 90");
        }
    }
}

In this example, the keys are 77, 85, 88, and 92. The greatest key strictly less than 90 is 88, so the output is Highest score below 90: 88 -> David. Note that lowerEntry does not consider the key 90 itself; it only looks for keys that are strictly smaller.

Comparing lowerEntry with floorEntry, ceilingEntry, and higherEntry

TreeMap provides four navigation methods that differ in whether they include the given key itself. The table below summarizes the behavior for a key k:

Each method returns null when no matching key exists. The choice between them depends on whether you want to include the exact key when it is present. For instance, if you need the entry for the exact key or the one just below it, floorEntry is appropriate. If you need an entry that is strictly less than the key, lowerEntry is the correct method.

Performance and Complexity

TreeMap is implemented as a red-black tree, so all navigation methods, including lowerEntry, run in O(log n) time, where n is the number of entries in the map. This makes it efficient even for large maps. The method does not iterate over the entire map; it traverses the tree from the root to the appropriate leaf, comparing keys along the way.

Because lowerEntry returns a Map.Entry object, it does not modify the map. If you only need the key, you can use lowerKey(K key), which returns the key itself rather than the entire entry. The lowerKey method has the same time complexity and is slightly more efficient when you do not need the value.

Edge Cases: Empty Map, Null Keys, and No Predecessor

TreeMap does not allow null keys, so calling lowerEntry(null) will throw a NullPointerException. This is consistent with the natural ordering contract of TreeMap. If the map is empty, lowerEntry returns null. Similarly, if the given key is less than or equal to the smallest key in the map, the method returns null because there is no strictly smaller key.

Consider a map with keys {10, 20, 30}:

• lowerEntry(10) returns null because no key is strictly less than 10.
• lowerEntry(15) returns the entry for 10.
• lowerEntry(30) returns the entry for 20.
• lowerEntry(35) returns the entry for 30.

These edge cases are important when writing defensive code. Always check the return value for null before dereferencing the entry.

Practical Use Cases and Alternatives

lowerEntry is useful in scenarios where you need to find the previous element in a sorted collection. For example, in a scheduling system, you might want to find the last event that occurred before a given time. Or in a range query, you might need to find the boundary below a certain value.

If you need to iterate over all entries that are less than a key, you could use the headMap method instead. headMap(K toKey, boolean inclusive) returns a view of the map whose keys are less than (or equal to, if inclusive is true) toKey. However, headMap returns a submap view, not a single entry. For a single predecessor lookup, lowerEntry is more direct and avoids creating a view object.

Another alternative is to manually iterate with an Iterator, but that would be O(n) in the worst case. lowerEntry is the idiomatic and efficient choice when you need exactly one predecessor entry.

When you need both the predecessor and successor, you can combine lowerEntry and higherEntry to navigate the map in both directions. This is common in implementing balanced navigation logic, such as finding the closest key to a given value.

The method is part of the NavigableMap interface, so it is also available in other implementations like ConcurrentSkipListMap, though the underlying data structure and concurrency behavior differ. For single-threaded use cases, TreeMap is typically sufficient; for concurrent access, consider ConcurrentSkipListMap and its lowerEntry implementation.