Java TreeMap lowerEntry: Find the Predecessor Entry

TreeMap.lowerEntry(K key) returns the key-value mapping associated with the greatest key strictly less than the given key, or null if no such key exists. It 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 uses the red-black tree backing TreeMap to locate the predecessor in O(log n) time. It compares the given key with the keys in the tree and returns the entry whose key is the maximum among all keys 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 the navigation methods, including lowerEntry, run in O(log n) time, where n is the number of entries in the map. The method does not iterate over the entire map; it walks the tree from the root to the appropriate position, comparing keys along the way.

Because lowerEntry returns a Map.Entry object, it does not modify the map. If you only need the key, use lowerKey(K key), which returns the key directly and has the same O(log n) time complexity.

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

With the default natural ordering, TreeMap cannot contain null keys. Passing null to lowerEntry on a non-empty map causes the internal key comparison to throw a NullPointerException. 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. If the map was created with a custom Comparator that permits null keys, the behavior depends on that comparator.

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. 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, use headMap 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 is 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.