Floor and Ceiling Operations in a BST
You'll learn how to find the floor (largest key ≤ target) and ceiling (smallest key ≥ target) in a Binary Search Tree by tracking candidates during search.
The Core Idea
Imagine you're searching for a book priced at 25 or less (say, 25 or more (say, $27).
In a BST, we use the same logic. The floor is the largest key that doesn't exceed our target, and the ceiling is the smallest key that meets or exceeds it.
How It Works
Finding Floor:
- Start at the root and move toward the target
- When you go right (current key < target), the current node is a floor candidate — it's ≤ target, but maybe there's something larger
- When you go left (current key > target), the current node is too big; ignore it
- Keep the best candidate seen so far
Finding Ceiling:
- Start at the root and move toward the target
- When you go left (current key > target), the current node is a ceiling candidate — it's ≥ target, but maybe there's something smaller
- When you go right (current key < target), the current node is too small; ignore it
- Keep the best candidate seen so far
Example
In a BST with keys [3, 7, 10, 15, 20], searching for target 12:
- Floor of 12 → 10 (largest ≤ 12)
- Ceiling of 12 → 15 (smallest ≥ 12)
The search path updates candidates as you traverse, similar to how regular BST search works but tracking "closest valid" instead of "exact match."
Key Takeaway: Floor and ceiling operations find the closest bounding keys in a BST by maintaining the best candidate during a modified search traversal.