skip to content

Explain the NavigableSet navigation methods (floor, ceiling, lower, higher) and how they differ.

level: middleimportance: should knowfreq 60%

answer

  1. floor ≤ , ceiling ≥ (inclusive)
  2. lower < , higher > (strict)
  3. Target need not be in the set
  4. All four return null when nothing qualifies
  5. pollFirst/pollLast remove the ends; descendingSet reverses

basics

~20 s

They find the nearest element to a given value. ceiling returns the smallest element >= the value; floor the largest <= it; higher is strictly greater; lower is strictly less. They return null if no such element exists.

solid answer

~40 s

TreeSet implements NavigableSet, which adds nearest-neighbour lookups. Given a target value: floor(x) returns the greatest element <= x; ceiling(x) returns the least element >= x; lower(x) returns the greatest element strictly < x; higher(x) returns the least element strictly > x. The 'floor/ceiling' pair is inclusive of an exact match, while 'lower/higher' are strict (exclusive). Each runs in O(log n) by walking the red-black tree. All four return null when no qualifying element exists — and note the target itself need not be a member of the set. NavigableSet also gives pollFirst/pollLast (retrieve-and-remove the ends), descendingSet/descendingIterator for reverse traversal, and the range views headSet/tailSet/subSet, all of which can take inclusive/exclusive boundary flags. These methods make TreeSet ideal for problems like 'find the closest price at or below budget'.

go deeper

for a junior

Can roughly say these find nearby elements and that ceiling is the next-up value.

for a middle

States the exact ≤/≥/strict semantics of floor/ceiling/lower/higher and that they return null when empty.

for a senior

Connects them to O(log n) tree descents, knows pollFirst/pollLast and descendingSet, and applies them to range/proximity problems.

for a principal

Chooses TreeSet over alternatives based on the access pattern (ordered + nearest-neighbour) and reasons about API ergonomics like null-returning navigation vs Optional.

## Setup A **NavigableSet** is a `SortedSet` with extra methods for finding elements *near* a given value. `TreeSet` is the standard implementation. Because the elements are kept sorted in a balanced tree, the set can answer 'what's the nearest element to X?' in **O(log n)** by descending the tree. ## The four nearest-neighbour methods Imagine the sorted set `{10, 20, 30, 40}` and a target value `t`: | Method | Meaning | Inclusive of exact match? | |---|---|---| | `floor(t)` | greatest element **≤ t** | yes | | `ceiling(t)` | least element **≥ t** | yes | | `lower(t)` | greatest element **< t** (strictly) | no | | `higher(t)` | least element **> t** (strictly) | no | Worked examples on `{10,20,30,40}`: - `floor(25)` → 20, `ceiling(25)` → 30 (25 isn't present; we get the neighbours). - `floor(30)` → 30, `ceiling(30)` → 30 (exact match, inclusive). - `lower(30)` → 20, `higher(30)` → 40 (strict, so they skip 30 itself). - `floor(5)` → **null** (nothing is ≤ 5), `higher(40)` → **null** (nothing > 40). **Key points:** (1) the target `t` does **not** have to be in the set; (2) all four return **null** when no element qualifies — always null-check the result. ## Memory aid - **Floor** = the floor is *below* you → largest value not above the target. - **Ceiling** = the ceiling is *above* you → smallest value not below the target. - **lower / higher** = the *strict* versions (never equal to the target). ## Related NavigableSet members - `first()` / `last()` — smallest / largest element (from SortedSet). - `pollFirst()` / `pollLast()` — return **and remove** the smallest/largest; great for using a TreeSet as a priority structure. - `descendingSet()` — a reverse-order **view** of the same set; `descendingIterator()` iterates high→low. - `headSet`, `tailSet`, `subSet` — range views (covered separately), each with inclusive/exclusive flags in the NavigableSet overloads. ## Why it matters These turn a TreeSet into a tool for **range and proximity queries**: 'cheapest item at or above my minimum', 'last event before timestamp T', 'next available slot after now'. A HashSet cannot do any of this. ## Complexity Each navigation call is **O(log n)** — one root-to-leaf descent. Returning a range *view* is O(log n) to locate the boundary; iterating it is proportional to the number of elements visited.

  • On TreeSet {10,20,30}, what do ceiling(20) and higher(20) return?
    ceiling(20) returns 20 (inclusive of the exact match); higher(20) returns 30 (strictly greater, so it skips 20).
  • How would you pop the smallest element off a TreeSet efficiently?
    Use pollFirst(), which returns and removes the least element in O(log n); pollLast() does the same for the greatest.

saying these in an interview costs you the question

  • Mixing up floor (≤) and ceiling (≥)
  • Thinking lower/higher are inclusive
  • Assuming the target must already be in the set
  • Forgetting these can return null and dereferencing it (NPE)
  • Believing HashSet offers these (it doesn't)

context

resolving links…