Floor and Ceil in BST in DSA Rust

Mental Model

Floor is the biggest value smaller or equal to target; ceil is the smallest value bigger or equal to target in the BST.

Analogy: Imagine a bookshelf sorted by book height. Floor is the tallest book not taller than your target height; ceil is the shortest book not shorter than your target height.

       8
      / \
     4   12
    / \   / \
   2   6 10  14

Dry Run Walkthrough

Input: BST: 8->4->12->2->6->10->14, find floor and ceil of 5

Goal: Find the floor and ceil values for 5 in the BST

Step 1: Start at root node 8, compare 5 with 8

Current node: 8

Why: We start from the root to find floor and ceil

Step 2: Since 5 < 8, move to left child 4

8 -> [curr->4] -> 12 -> ...

Why: 5 is smaller than 8, so floor and ceil must be in left subtree or 4

Step 3: Compare 5 with 4, since 5 > 4, floor candidate updated to 4, move to right child 6

8 -> 4 -> [curr->6] -> 12 -> ...

Why: 5 is greater than 4, so floor could be 4, but maybe bigger floor in right subtree

Step 4: Compare 5 with 6, since 5 < 6, ceil candidate updated to 6, move to left child null

8 -> 4 -> 6 -> null [curr->null]

Why: 5 is less than 6, so ceil could be 6, but check left subtree for smaller ceil

Step 5: Reached null, stop search

Floor = 4, Ceil = 6

Why: No more nodes to check, floor and ceil found

Result:

Floor: 4
Ceil: 6

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn floor_ceil_bst(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> (Option<i32>, Option<i32>) {
    let mut floor = None;
    let mut ceil = None;
    let mut curr = root;

    while let Some(node_rc) = curr {
        let node = node_rc.borrow();
        if node.val == target {
            floor = Some(node.val);
            ceil = Some(node.val);
            break;
        } else if node.val < target {
            floor = Some(node.val); // update floor candidate
            curr = node.right.clone(); // move right to find bigger floor
        } else {
            ceil = Some(node.val); // update ceil candidate
            curr = node.left.clone(); // move left to find smaller ceil
        }
    }
    (floor, ceil)
}

fn main() {
    // Build BST
    let root = TreeNode::new(8);
    let node4 = TreeNode::new(4);
    let node12 = TreeNode::new(12);
    let node2 = TreeNode::new(2);
    let node6 = TreeNode::new(6);
    let node10 = TreeNode::new(10);
    let node14 = TreeNode::new(14);

    root.borrow_mut().left = Some(node4.clone());
    root.borrow_mut().right = Some(node12.clone());
    node4.borrow_mut().left = Some(node2.clone());
    node4.borrow_mut().right = Some(node6.clone());
    node12.borrow_mut().left = Some(node10.clone());
    node12.borrow_mut().right = Some(node14.clone());

    let target = 5;
    let (floor, ceil) = floor_ceil_bst(Some(root), target);
    println!("Floor: {}", floor.map_or("None".to_string(), |v| v.to_string()));
    println!("Ceil: {}", ceil.map_or("None".to_string(), |v| v.to_string()));
}

while let Some(node_rc) = curr {

loop through nodes to find floor and ceil

if node.val == target { floor = Some(node.val); ceil = Some(node.val); break; }

exact match found, floor and ceil are target

else if node.val < target { floor = Some(node.val); curr = node.right.clone(); }

update floor and move right to find bigger floor

else { ceil = Some(node.val); curr = node.left.clone(); }

update ceil and move left to find smaller ceil

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) because we traverse from root down to leaf at most once, where h is tree height

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Compared to scanning all nodes O(n), this uses BST property to reduce to O(h)

Edge Cases

target smaller than all nodes

floor is None, ceil is smallest node

DSA Rust

else { ceil = Some(node.val); curr = node.left.clone(); }

target larger than all nodes

floor is largest node, ceil is None

DSA Rust

else if node.val < target { floor = Some(node.val); curr = node.right.clone(); }

target equals a node value

floor and ceil both equal target

DSA Rust

if node.val == target { floor = Some(node.val); ceil = Some(node.val); break; }

When to Use This Pattern

When asked to find closest smaller or larger values in a BST, use floor and ceil search by moving left or right based on comparisons.

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly when moving left or right
Fix: Update floor when moving right (node.val < target), update ceil when moving left (node.val > target)

Summary

Finds the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a BST.

Use when you need nearest bounds for a value in a sorted tree structure.

The key is to move left or right while updating floor or ceil candidates based on comparisons.

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