On this page
Description
Plain search answers "is this key here?" Floor and ceil answer the question you usually have when it isn't: what's the nearest value on the right side of my limit? The floor of a key is the largest value at or below it. The ceil is the smallest value at or above it. Both lie on the path a search for the key follows, so they cost no more than the search. Range queries, with a bound on each side, come from the same idea.
We'll go from simple to more technical:
- The pattern: walk down and record a candidate on the safe side.
- A second flavor: range queries with both bounds, pruning whole subtrees.
- Where nearest-match queries run in production (time series, prices, versions).
- What breaks it: stopping early, the wrong side, sentinels, and no pruning.
The approach
Walk down from the root as if you were searching for the key. For the floor, every node smaller than the key is a candidate. Record it, then go right to look for a closer one. A node larger than the key can't be the floor, so go left without recording. The last candidate you recorded is the answer.
Find the floor of 55 in this tree:
| Node | Compared with 55 | Floor so far | Next step |
|---|---|---|---|
| 40 | smaller | 40 | right |
| 60 | larger | 40 | left |
| 50 | smaller | 50 | right |
| (none) | 50 | stop: the floor is 50 |
Java
int floorBST(TreeNode root, int key) {
int floor = -1;
TreeNode cur = root;
while (cur != null) {
if (cur.val == key) return cur.val;
if (cur.val < key) { floor = cur.val; cur = cur.right; } // <= key: a candidate - look for a closer one
else cur = cur.left;
}
return floor;
}
Python
def floor_bst(root: TreeNode | None, key: int) -> int:
floor = -1
cur = root
while cur is not None:
if cur.val == key:
return cur.val
if cur.val < key:
floor = cur.val # <= key: a candidate - look for a closer one
cur = cur.right
else:
cur = cur.left
return floor
Ceil is the mirror image. Record a node when it's larger than the key and go left; go right without recording when it's smaller. For 55 the ceil walk records 60 and ends with 60. Recording a candidate never ends the walk, since a closer value can sit further down. The walk ends on an exact match or when it falls off the tree. If nothing was recorded, the answer is -1: every value is on the wrong side of the key.
Floor and ceil lie on the same path, so one walk can track both. The value closest to a key is always one of the two.
A second flavor: both bounds at once
Floor and ceil each use one bound. A range query, such as "sum every value in [lo, hi]", uses both. The BST order lets it skip whole subtrees:
Java
long rangeSum(TreeNode node, int lo, int hi) {
if (node == null) return 0;
if (node.val < lo) return rangeSum(node.right, lo, hi); // node and its left subtree are all too small
if (node.val > hi) return rangeSum(node.left, lo, hi); // node and its right subtree are all too large
return node.val + rangeSum(node.left, lo, hi) + rangeSum(node.right, lo, hi);
}
Python
def range_sum(node: TreeNode | None, lo: int, hi: int) -> int:
if node is None:
return 0
if node.val < lo:
return range_sum(node.right, lo, hi) # node and its left subtree are all too small
if node.val > hi:
return range_sum(node.left, lo, hi) # node and its right subtree are all too large
return node.val + range_sum(node.left, lo, hi) + range_sum(node.right, lo, hi)
A node below lo rules out its whole left subtree. A node above hi rules out its whole right subtree. Only nodes inside the range explore both sides. So the walk visits the m values in range plus O(h) nodes along the edges. On a balanced tree of 65,535 nodes, a range holding 11 values touched 28 nodes, not 65,535.
Where you'll see it
Floor and ceil are the "nearest match" queries of every ordered index. Think of the latest event at or before a timestamp, or the price tier that applies to an order total. Java's TreeMap.floorKey and ceilingKey are exactly these walks. A database range scan (WHERE t BETWEEN lo AND hi) starts with a ceil lookup for lo and stops once it passes hi.
Which tool for which job?
| You need | Use |
|---|---|
| Largest value at or below the key | floor: record on right steps |
| Smallest value at or above the key | ceil: record on left steps |
| Strictly below or above | predecessor / successor: keep walking on a match |
| The value closest to the key | track both in one walk; compare differences in long |
Everything in [lo, hi] | a range walk that prunes subtrees outside the bounds |
| Java / Python | floorKey / ceilingKey; bisect_right(s, k) - 1 / bisect_left(s, k) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Returning the first candidate | misses a closer value further down (40 instead of 50 above) | keep walking until a match or the end |
| Recording a floor on a left step | records a value above the key | floor records on right steps only |
| -1 as "none" with negative values | a real answer and "none" look the same | null / None or a found flag |
| A range query with no pruning | O(n) even for a tiny range | skip the side that's out of range |
int differences for "closest" | the difference wraps and a far value wins | compute in long |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. In [8, 5, 10, 3, 6, null, 12], what are the floor and ceil of 7, and which nodes does the floor walk record?
Show answer
Floor 6, ceil 8. The floor walk goes left at 8 without recording, since 8 is too big. It records 5 and goes right, records 6 and goes right, then falls off. The ceil walk records 8 at the root and goes left. 5 and 6 are too small, so 8 stands.
2. Why can the closest value to a key always be found in one O(h) walk?
Show answer
The closest value is either the floor or the ceil. Nothing else can be closer. Both are recorded along the search path for the key, so one walk that tracks the best difference finds it.
3. A range sum over [lo, hi] reaches a node below lo. What can it skip, and why?
Show answer
The node and its whole left subtree. Everything there is smaller than the node, so it's smaller than lo too. Only the right subtree can still hold values in range. This pruning makes a range query O(h + m) instead of O(n).
Key takeaways
- The floor is the largest value at or below the key, and the ceil the smallest at or above. Both cost O(h).
- Record a candidate on a step in the safe direction (right for floor, left for ceil) and keep walking.
- The closest value to a key is its floor or its ceil. Compare differences in
long. - A range query uses both bounds to skip whole subtrees: O(h + m) for m values in range.
- The strict versions are the predecessor and successor. On an exact match they keep walking.