101
0/276
Loading content...
Standard BST search answers a simple question: Is this value in the tree? But many real-world scenarios require more nuanced queries:
These are floor and ceiling queries—and Binary Search Trees are perfectly designed to answer them efficiently. Understanding these operations unlocks a powerful class of bounded searches that appear throughout systems programming, databases, and competitive programming.
By the end of this page, you will understand the precise definitions of floor and ceiling in the context of BSTs, master iterative and recursive implementations for both operations, analyze their time and space complexity, and recognize real-world applications of bounded searches.
Before implementing these operations, let's establish precise definitions:
Floor(x): The largest value in the BST that is less than or equal to x.
Ceiling(x): The smallest value in the BST that is greater than or equal to x.
If x itself exists in the BST, both floor(x) and ceiling(x) return x.
| Query Value (x) | Floor(x) | Ceiling(x) | Explanation |
|---|---|---|---|
| 25 | 20 | 30 | 25 not in tree; 20 is largest ≤ 25; 30 is smallest ≥ 25 |
| 50 | 50 | 50 | 50 exists; floor and ceiling both return 50 |
| 55 | 50 | 60 | 55 not in tree; 50 is largest ≤ 55; 60 is smallest ≥ 55 |
| 10 | None | 20 | No value ≤ 10 exists; 20 is smallest in tree |
| 90 | 80 | None | 80 is largest ≤ 90; no value ≥ 90 exists |
| 60 | 60 | 60 | 60 exists; both operations return 60 |
When no valid floor or ceiling exists, the operation returns a sentinel value (null, None, or -1 depending on implementation). Always clarify expected behavior for out-of-range queries.
Finding the floor requires a careful search that tracks candidates as we navigate the tree. The key insight is:
Every time we find a node whose value is ≤ x, it becomes a potential floor candidate. However, a larger value might exist in its right subtree, so we must continue searching.
The Algorithm Logic:
If the current node equals x: We've found an exact match—return it immediately (or store it and return, as no larger valid floor exists).
If the current node's value > x: The floor must be in the left subtree (current node is too large).
If the current node's value < x: This node is a valid floor candidate. But a larger floor might exist in the right subtree, so we record this candidate and continue right.
Visual Walkthrough: Finding floor(55)
Starting from root 50:
Result: floor(55) = 50
Notice how we tracked 50 as a candidate, then continued searching for something larger. When the search failed to find a valid larger candidate, we returned 50.
Floor search is like a hiring process: every qualifying candidate (value ≤ x) is kept on the shortlist, but we keep looking for someone better (larger). Only when the search exhausts does the best candidate win.
Let's implement floor using both iterative and recursive approaches:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
def floor(root, x): """ Find the floor of x in the BST. Floor is the largest value in the tree that is <= x. Returns None if no such value exists. Time Complexity: O(h) - traverse one root-to-leaf path Space Complexity: O(1) - only tracking candidate """ result = None current = root while current: if current.val == x: # Exact match found - this is the floor return current.val elif current.val > x: # Current node too large - floor must be in left subtree current = current.left else: # current.val < x # This is a valid floor candidate # But a larger floor might exist in the right subtree result = current.val current = current.right return result def floor_recursive(root, x): """ Recursive implementation of floor. Time Complexity: O(h) Space Complexity: O(h) - recursion stack """ def helper(node, x, candidate): if node is None: return candidate if node.val == x: return node.val elif node.val > x: # Go left, keep current candidate return helper(node.left, x, candidate) else: # node.val < x: update candidate, go right return helper(node.right, x, node.val) return helper(root, x, None) # Variant: Floor that returns the node, not just the valuedef floor_node(root, x): """ Find the floor node (not just value). Useful when you need the node reference for further operations. """ result_node = None current = root while current: if current.val == x: return current elif current.val > x: current = current.left else: result_node = current current = current.right return result_nodeCeiling search is the mirror image of floor search:
Every time we find a node whose value is ≥ x, it becomes a potential ceiling candidate. However, a smaller value might exist in its left subtree, so we must continue searching.
The Algorithm Logic:
If the current node equals x: We've found an exact match—return it immediately.
If the current node's value < x: The ceiling must be in the right subtree (current node is too small).
If the current node's value > x: This node is a valid ceiling candidate. But a smaller ceiling might exist in the left subtree, so we record this candidate and continue left.
Visual Walkthrough: Finding ceiling(55)
Starting from root 50:
Result: ceiling(55) = 60
Notice the symmetry with floor—we track candidates and seek improvements in the opposite direction.
Floor and ceiling are mirror operations. If you understand one, you understand both. In floor, we track candidates while going right; in ceiling, we track candidates while going left. The update condition is reversed (< vs >), but the structure is identical.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
def ceiling(root, x): """ Find the ceiling of x in the BST. Ceiling is the smallest value in the tree that is >= x. Returns None if no such value exists. Time Complexity: O(h) - traverse one root-to-leaf path Space Complexity: O(1) - only tracking candidate """ result = None current = root while current: if current.val == x: # Exact match found - this is the ceiling return current.val elif current.val < x: # Current node too small - ceiling must be in right subtree current = current.right else: # current.val > x # This is a valid ceiling candidate # But a smaller ceiling might exist in the left subtree result = current.val current = current.left return result def ceiling_recursive(root, x): """ Recursive implementation of ceiling. Time Complexity: O(h) Space Complexity: O(h) - recursion stack """ def helper(node, x, candidate): if node is None: return candidate if node.val == x: return node.val elif node.val < x: # Go right, keep current candidate return helper(node.right, x, candidate) else: # node.val > x: update candidate, go left return helper(node.left, x, node.val) return helper(root, x, None) def ceiling_node(root, x): """ Find the ceiling node (not just value). """ result_node = None current = root while current: if current.val == x: return current elif current.val < x: current = current.right else: result_node = current current = current.left return result_nodeBoth floor and ceiling operations share identical complexity characteristics:
| Operation | Time (Balanced) | Time (Skewed) | Space (Iterative) | Space (Recursive) |
|---|---|---|---|---|
| Floor | O(log n) | O(n) | O(1) | O(h) |
| Ceiling | O(log n) | O(n) | O(1) | O(h) |
Time Complexity: O(h)
Both operations traverse at most one root-to-leaf path. At each node, we perform O(1) work (comparison, candidate update, child selection). The path length is bounded by the tree height h:
Space Complexity:
The iterative approach is preferred for production code due to its constant space usage and no risk of stack overflow.
In a sorted array, floor and ceiling require O(log n) using binary search. In a balanced BST, we achieve the same O(log n) complexity. The BST advantage is that insertion and deletion are also O(log n), whereas sorted arrays require O(n) for these operations.
Sometimes you need strict versions of floor and ceiling:
Strict Floor (Predecessor): The largest value strictly less than x (not equal).
Strict Ceiling (Successor): The smallest value strictly greater than x (not equal).
These are also called predecessor and successor operations in BST terminology.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
def strict_floor(root, x): """ Find the largest value strictly less than x. Also known as 'predecessor' of x. Key difference from floor: we DON'T return x if x exists. """ result = None current = root while current: if current.val >= x: # Current node is equal or greater - go left current = current.left else: # current.val < x: valid candidate, try to find larger result = current.val current = current.right return result def strict_ceiling(root, x): """ Find the smallest value strictly greater than x. Also known as 'successor' of x. Key difference from ceiling: we DON'T return x if x exists. """ result = None current = root while current: if current.val <= x: # Current node is equal or smaller - go right current = current.right else: # current.val > x: valid candidate, try to find smaller result = current.val current = current.left return result # Alternative: Finding successor of a given nodedef successor_of_node(node, root): """ Find the inorder successor of a given node. Two cases: 1. Node has right child: successor is leftmost node in right subtree 2. Node has no right child: successor is lowest ancestor for which the node is in the left subtree """ if node.right: # Case 1: Go right, then all the way left current = node.right while current.left: current = current.left return current # Case 2: Need to find ancestor successor = None current = root while current: if node.val < current.val: successor = current current = current.left elif node.val > current.val: current = current.right else: # Found the node break return successorWhen asked for 'floor' or 'ceiling' in an interview, always clarify: 'Should I include x itself if it exists in the tree, or do you want strictly less than / greater than?' This prevents ambiguity and shows attention to detail.
Floor and ceiling often work together. A common pattern is finding the nearest neighbor—the value in the BST closest to a given target:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
def nearest_neighbor(root, target): """ Find the value in the BST closest to target. Uses floor and ceiling to find the two candidates, then returns whichever is closer. Time Complexity: O(h) - can be optimized to single pass Space Complexity: O(1) """ floor_val = floor(root, target) ceiling_val = ceiling(root, target) if floor_val is None: return ceiling_val if ceiling_val is None: return floor_val # Both exist - return the closer one if abs(target - floor_val) <= abs(ceiling_val - target): return floor_val return ceiling_val def nearest_neighbor_optimized(root, target): """ Single-pass nearest neighbor search. Track both floor and ceiling candidates simultaneously for better cache locality and fewer traversals. """ floor_candidate = None ceiling_candidate = None current = root while current: if current.val == target: return current.val elif current.val < target: floor_candidate = current.val current = current.right else: ceiling_candidate = current.val current = current.left # Determine the closer candidate if floor_candidate is None: return ceiling_candidate if ceiling_candidate is None: return floor_candidate if abs(target - floor_candidate) <= abs(ceiling_candidate - target): return floor_candidate return ceiling_candidate def values_between(root, low, high): """ Find all values in [low, high] range. Uses ceiling(low) as starting point, then collects all values until we exceed high. Time: O(h + k) where k is number of values in range Space: O(k) for result storage """ result = [] def inorder_bounded(node): if node is None: return # Prune left if all values would be < low if node.val >= low: inorder_bounded(node.left) # Include current if in range if low <= node.val <= high: result.append(node.val) # Prune right if all values would be > high if node.val <= high: inorder_bounded(node.right) inorder_bounded(root) return resultThe nearest_neighbor_optimized function demonstrates how floor and ceiling can be combined in a single traversal. As we navigate the tree:
At termination, we have both candidates with only one traversal.
Floor and ceiling operations power numerous real-world systems:
Example: Java's TreeMap
Java's TreeMap (a Red-Black Tree, which is a balanced BST) provides exactly these operations:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");
map.floorKey(25); // Returns 20 (largest key ≤ 25)
map.ceilingKey(25); // Returns 30 (smallest key ≥ 25)
map.lowerKey(20); // Returns 10 (largest key < 20, strict floor)
map.higherKey(20); // Returns 30 (smallest key > 20, strict ceiling)
These methods are backed by the exact algorithms we've studied, running in O(log n) time.
Floor and ceiling are fundamental BST operations that extend exact search to bounded queries. Let's consolidate the key insights:
Looking Ahead:
Floor and ceiling find individual boundary values. But what about extracting all values within a range? The next page explores range queries in BSTs—efficiently finding all values between two bounds. This builds directly on floor/ceiling concepts while introducing new pruning strategies for optimal performance.
You now understand floor and ceiling operations in BSTs—both the intuition behind them and their implementation. You can recognize when these operations apply to real-world problems and choose between inclusive and strict variants. Next, we'll extend this knowledge to full range queries.