Floor and Ceil in BST in DSA Rust - Deep Dive

Overview - Floor and Ceil in BST

What is it?

Floor and Ceil in a Binary Search Tree (BST) are two special values related to a given number. The floor is the greatest value in the BST that is less than or equal to the given number. The ceil is the smallest value in the BST that is greater than or equal to the given number. These help us quickly find close matches to a number inside a sorted tree structure.

Why it matters

Without floor and ceil, finding the closest smaller or larger value to a number in a BST would require scanning many nodes, losing the speed advantage of BSTs. These operations allow fast queries like 'find the nearest available price less than or equal to my budget' or 'find the next available appointment after a given time'. They make BSTs practical for many real-world searching problems.

Where it fits

Before learning floor and ceil, you should understand what a Binary Search Tree is and how searching works in it. After mastering floor and ceil, you can explore range queries, nearest neighbor searches, and balanced BSTs like AVL or Red-Black trees for efficient dynamic data handling.

Mental Model

Core Idea

Floor and ceil in a BST find the closest smaller-or-equal and larger-or-equal values to a target by smartly moving left or right using BST properties.

Think of it like...

Imagine a bookshelf sorted by book height. To find the tallest book not taller than your height (floor), you look left for shorter books if the current one is too tall. To find the shortest book not shorter than you (ceil), you look right for taller books if the current one is too short.

BST Node
  ┌─────────────┐
  │     15      │
  └─────┬───────┘
        │
   ┌────┴────┐
   │         │
  10        20
  / \       / \
 8  12    17  25

Floor and Ceil search for target=16:
- Floor: moves right from 15 to 20, but 20 > 16, so moves left to 17, 17 > 16, moves left (null), last floor candidate is 15.
- Ceil: moves right from 15 to 20, 20 >= 16, candidate ceil is 20, moves left to 17, 17 >= 16, better ceil candidate is 17, moves left (null), final ceil is 17.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its structure allows fast searching.

A Binary Search Tree is a tree where each node has up to two children. For any node, all values in the left subtree are smaller, and all values in the right subtree are larger. This property lets us decide to go left or right when searching for a value, making search faster than checking every node.

Result

You can find if a value exists in the BST by comparing and moving left or right, reducing search time from linear to logarithmic in balanced trees.

Understanding BST structure is key because floor and ceil rely on the ability to move left or right based on comparisons.

2

Foundation

Basic Search Operation in BST

Concept: Learn how to search for a specific value in a BST using comparisons.

To search for a value, start at the root. If the value equals the node's value, you found it. If smaller, go to the left child. If larger, go to the right child. Repeat until found or no child exists.

Result

You can quickly find if a value is present or not in the BST by following this path.

This search pattern is the foundation for floor and ceil, which extend it to find closest matches instead of exact matches.

3

Intermediate

Finding Floor Value in BST

🤔Before reading on: do you think floor is always found by going only left or only right? Commit to your answer.

Concept: Floor is the greatest value less than or equal to the target. We use BST properties to move left or right and keep track of candidates.

Start at root. If node value equals target, floor is found. If node value > target, move left (smaller values). If node value < target, record node as floor candidate and move right to find closer values. If no more nodes, last candidate is floor.

Result

Floor search returns the closest smaller or equal value to the target in the BST or None if none exists.

Knowing when to move left or right and when to update the floor candidate is crucial to efficiently find the floor without scanning all nodes.

4

Intermediate

Finding Ceil Value in BST

🤔Before reading on: do you think ceil search is just the opposite of floor search? Commit to your answer.

Concept: Ceil is the smallest value greater than or equal to the target. We move left or right and track candidates similarly to floor but reversed.

Start at root. If node value equals target, ceil is found. If node value < target, move right (larger values). If node value > target, record node as ceil candidate and move left to find closer values. If no more nodes, last candidate is ceil.

Result

Ceil search returns the closest larger or equal value to the target in the BST or None if none exists.

Understanding the mirrored logic of ceil compared to floor helps avoid confusion and errors in implementation.

5

Intermediate

Implementing Floor and Ceil in Rust

🤔Before reading on: do you think recursion or iteration is better for floor and ceil in Rust? Commit to your answer.

Concept: Translate the floor and ceil logic into Rust code using safe, clear iteration or recursion.

Use a loop starting at root. Keep an Option variable for candidate floor or ceil. Compare target with current node value. Update candidate and move left or right accordingly. Return candidate at end. Rust's Option type cleanly represents possible absence of floor or ceil.

Result

Rust functions that return Option for floor and ceil, correctly handling all cases.

Implementing in Rust teaches careful handling of ownership and Option types, reinforcing safe and idiomatic code.

6

Advanced

Handling Edge Cases and Empty Trees

🤔Before reading on: do you think floor or ceil can exist if the BST is empty? Commit to your answer.

Concept: Consider what happens when the BST is empty or when target is outside the range of BST values.

If BST is empty, floor and ceil do not exist (return None). If target is smaller than all nodes, floor is None; if larger than all nodes, ceil is None. Code must handle these gracefully without errors.

Result

Robust floor and ceil functions that never panic and correctly return None when no valid floor or ceil exists.

Anticipating and coding for edge cases prevents runtime errors and ensures reliable behavior in all inputs.

7

Expert

Optimizing Floor and Ceil in Balanced BSTs

🤔Before reading on: do you think balancing the BST affects floor and ceil performance? Commit to your answer.

Concept: Balanced BSTs keep height low, improving worst-case floor and ceil search times from linear to logarithmic.

In balanced BSTs like AVL or Red-Black trees, floor and ceil searches remain the same logically but run faster due to guaranteed tree height. Understanding this helps in choosing data structures for performance-critical applications.

Result

Floor and ceil operations run in O(log n) time in balanced BSTs, making them efficient even for large datasets.

Knowing how tree balance affects floor and ceil performance guides data structure choice and optimization in real systems.

Under the Hood

Floor and ceil searches use BST's ordering property to prune search space. At each node, comparing target with node value decides direction: left subtree has smaller values, right subtree has larger. By tracking candidates when moving right (for floor) or left (for ceil), the algorithm remembers the best match so far. This avoids scanning all nodes and leverages BST's sorted nature.

Why designed this way?

BSTs were designed to allow fast search by ordering nodes. Floor and ceil extend this by using the same ordering to find closest matches. Alternatives like linear search or unsorted trees would be slower. The design balances simplicity and efficiency, making these operations intuitive and fast.

Start at root
  │
  ├─ If node == target: return node
  ├─ If node > target:
  │    ├─ For floor: go left
  │    └─ For ceil: record node, go left
  └─ If node < target:
       ├─ For floor: record node, go right
       └─ For ceil: go right
Keep track of candidate during traversal
Return candidate if no exact match

Myth Busters - 4 Common Misconceptions

Quick: Is floor always found by going only left in the BST? Commit yes or no.

Common Belief: Floor is always found by moving left because floor is smaller than or equal to target.

Reality: Floor may require moving right to find a closer smaller value after passing nodes smaller than target.

Why it matters: Assuming floor is only on the left leads to missing correct floor values and incorrect results.

Quick: Does ceil always exist for any target in a BST? Commit yes or no.

Common Belief: Ceil always exists because you can always find a value greater than or equal to target.

Reality: Ceil may not exist if target is larger than all values in the BST.

Why it matters: Ignoring this causes bugs or crashes when code assumes ceil is always present.

Quick: Is floor search logic just the exact opposite of ceil search? Commit yes or no.

Common Belief: Floor and ceil searches are mirror images and use the same logic reversed.

Reality: They are similar but differ in when to update candidates and which subtree to explore, requiring careful implementation.

Why it matters: Treating them as exact opposites causes subtle bugs and incorrect candidate tracking.

Quick: Can floor or ceil be found in an empty BST? Commit yes or no.

Common Belief: Floor or ceil can be found even if the BST is empty by returning some default value.

Reality: No values exist in an empty BST, so floor and ceil do not exist and must return None or equivalent.

Why it matters: Failing to handle empty trees leads to runtime errors or invalid results.

Expert Zone

1

Floor and ceil candidate updates must happen before moving subtrees to avoid missing better matches deeper in the tree.

2

In threaded or augmented BSTs, floor and ceil can be found even faster by using extra pointers or stored subtree info.

3

When duplicates exist, floor and ceil definitions depend on whether duplicates are allowed on left or right subtree, affecting search logic.

When NOT to use

Floor and ceil in BSTs are not ideal when data is unsorted or changes frequently without rebalancing. In such cases, balanced trees like AVL or Red-Black trees or other data structures like segment trees or binary indexed trees may be better.

Production Patterns

Floor and ceil are used in database indexing to find nearest keys, in scheduling systems to find next available slots, and in financial systems to find closest prices or rates. Implementations often combine floor and ceil in a single function for efficiency.

Connections

Binary Search

Floor and ceil in BST build on the binary search principle of dividing search space by comparisons.

Understanding binary search helps grasp how floor and ceil prune the BST search path efficiently.

Interval Trees

Interval trees extend BSTs to handle ranges, where floor and ceil concepts help find overlapping intervals.

Knowing floor and ceil aids in understanding how interval trees quickly locate intervals intersecting a query.

Real Estate Pricing

Floor and ceil mimic finding closest lower or higher prices in real estate listings sorted by price.

Seeing floor and ceil as price brackets helps appreciate their practical use in matching budgets to options.

Common Pitfalls

#1 Not updating floor candidate before moving right subtree.

Wrong approach:

if node.value < target {
go right;
} else {
go left;
}
// No candidate update

Correct approach:

if node.value < target {
floor_candidate = node.value;
go right;
} else {
go left;
}

Root cause:

Misunderstanding that floor candidate must be recorded before exploring right subtree to find closer values.

#2 Assuming ceil always exists and returning a value without checking.

Wrong approach:

return ceil_candidate.unwrap(); // unwrap without checking

Correct approach:

return ceil_candidate; // return Option and handle None safely

Root cause:

Ignoring that target may be larger than all BST values, so no ceil exists.

#3 Using recursion without base case for empty subtree causing stack overflow.

Wrong approach:

fn floor(node: &Option>, target: i32) -> Option {
if node.is_none() {
floor(node, target) // recursive call without base case
} else {
...
}
}

Correct approach:

fn floor(node: &Option>, target: i32) -> Option {
if node.is_none() {
return None;
}
...
}

Root cause:

Forgetting to stop recursion on empty nodes leads to infinite recursion.

Key Takeaways

Floor and ceil in BST find closest smaller-or-equal and larger-or-equal values efficiently by leveraging BST ordering.

They extend basic BST search by tracking candidates and deciding direction based on comparisons with the target.

Handling edge cases like empty trees and targets outside the BST range is essential for robust code.

Balanced BSTs improve floor and ceil performance by keeping tree height low, ensuring fast queries.

Careful candidate updates and subtree traversal logic prevent common bugs and ensure correct results.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The root value of the BST

B. The smallest value in the BST greater than or equal to the given value

C. The greatest value in the BST less than or equal to the given value

D. The average of all values in the BST

Solution

1. Step 1: Understand the definition of floor in BST

   The floor of a value is the largest value in the BST that is less than or equal to the given value.

2. Step 2: Compare with other options

   The smallest value in the BST greater than or equal to the given value describes the ceil, not the floor. Options C and D are unrelated to floor.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option C

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest ≤ value in BST, ceil is smallest ≥ value [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is the smallest value
• Assuming floor is always the root

2. Which Rust function signature correctly represents a function to find the floor value in a BST node structure?

easy

A. fn floor(root: &Node, key: i32) -> i32

B. fn floor(root: &Option, key: i32) -> Option<i32>

C. fn floor(root: Box<Node>, key: i32) -> i32

D. fn floor(root: Option<Node>, key: i32) -> Option<i32>

Solution

1. Step 1: Analyze Rust ownership and references

   Using &Option allows borrowing the BST root without taking ownership, which is common in tree traversal.

2. Step 2: Check return type suitability

   Returning Option<i32> is correct because floor may not exist (None). Other options either take ownership or return plain i32 which may cause errors.

3. Final Answer:

   fn floor(root: &Option, key: i32) -> Option<i32> -> Option B

4. Quick Check:

   Borrow root & return Option<i32> for floor [OK]

Hint: Use &Option and Option<i32> for safe BST floor function [OK]

Common Mistakes:

• Taking ownership of root causing move errors
• Returning plain i32 without Option for missing floor
• Using incorrect parameter types

3. Given the BST below and key = 14, what is the floor value?

       15
      /  \
    10    20
   /  \     \
  8   12    25

medium

A. 12

B. 15

C. 14

D. 10

Solution

1. Step 1: Locate floor for key 14 in BST

   Floor is greatest value ≤ 14. Values ≤ 14 are 8, 10, 12. 15 and above are > 14.

2. Step 2: Identify the greatest among candidates

   Among 8, 10, 12, the greatest is 12.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   Floor(14) = 12 [OK]

Hint: Floor ≤ key, pick largest smaller value [OK]

Common Mistakes:

• Choosing 15 which is greater than key
• Confusing floor with ceil
• Picking 10 instead of 12

4. Consider this Rust function snippet to find ceil in BST:

fn ceil(root: &Option, key: i32) -> Option<i32> {
    match root {
        None => None,
        Some(node) => {
            if node.val == key {
                Some(node.val)
            } else if node.val > key {
                ceil(&node.left, key)
            } else {
                let right_ceil = ceil(&node.right, key);
                if right_ceil.is_some() {
                    right_ceil
                } else {
                    Some(node.val)
                }
            }
        }
    }
}

What is the bug in this code?

medium

A. It does not recurse on the right subtree when node.val > key

B. It does not handle the case when left_ceil is None correctly

C. It should check node.val > key instead of node.val < key

D. It incorrectly returns floor instead of ceil

Solution

1. Step 1: Recall correct ceil recursion logic

   For ceil: when node.val < key recurse right subtree; when node.val > key, recurse left and return left_ceil or node.val.

2. Step 2: Examine code branches

   Code uses else if node.val > key { ceil(&node.left, key) } (go left when > key) and else (< key) recurse right or node.val. This matches floor logic: go left when > key, right when < key updating candidate.

3. Step 3: Verify with trace

   In Q3 BST, key=14: path 15(>14) → left 10(<14) → right 12(<14) → None → 12 → 12. Returns 12 (floor), not 15 (ceil).

4. Final Answer:

   It incorrectly returns floor instead of ceil -> Option D

5. Quick Check:

   Branches match floor logic [OK]

Hint: Check recursion direction matches ceil logic [OK]

Common Mistakes:

• Confusing floor and ceil logic
• Misreading recursion branches
• Assuming missing recursion where none exists

5. You want to find both floor and ceil of a key in a BST efficiently. Which approach is best to implement in Rust?

hard

A. Traverse the BST once, updating floor and ceil candidates during the same recursion

B. Traverse the BST twice: once for floor and once for ceil separately

C. Convert BST to sorted array and use binary search twice

D. Use BFS traversal to find floor and ceil

Solution

1. Step 1: Consider efficiency of traversals

   Traversing twice (Traverse the BST twice: once for floor and once for ceil separately) doubles time. Converting to array (Convert BST to sorted array and use binary search twice) adds extra space and time. BFS (Use BFS traversal to find floor and ceil) is not suitable for ordered search.

2. Step 2: Single traversal updating floor and ceil

   During one recursion, compare node value with key and update floor if node.val ≤ key, update ceil if node.val ≥ key. This is efficient and uses BST properties.

3. Final Answer:

   Traverse the BST once, updating floor and ceil candidates during the same recursion -> Option A

4. Quick Check:

   One traversal updating floor & ceil is optimal [OK]

Hint: Update floor and ceil in one BST traversal [OK]

Common Mistakes:

• Doing two separate traversals wasting time
• Using BFS ignoring BST order
• Converting BST to array unnecessarily