Course contentsShow
← Computer Science
Lesson 519 of 2,87212. Binary Search TreesFree lesson

Floor and Ceiling Operations

Find floor (largest key ≤ target) and ceiling (smallest key ≥ target) by tracking candidates during search.

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 25inabookstore,buttheydon′thavethatexactprice.The∗∗floor∗∗wouldbethemostexpensivebookthatcosts25 in a bookstore, but they don't have that exact price. The **floor** would be the most expensive book that costs 25 or less (say, 23).The∗∗ceiling∗∗wouldbethecheapestbookthatcosts23). The **ceiling** would be the cheapest book that costs 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.