Floor and Ceil in BST in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the floor value for 15 in this BST?

Given the BST constructed by inserting these values in order: [10, 5, 20, 12, 30], what is the floor of 15?

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
};

fn floor(root: &Option<Box<Node>>, key: i32) -> Option<i32> {
    match root {
        None => None,
        Some(node) => {
            if node.val == key {
                Some(node.val)
            } else if node.val > key {
                floor(&node.left, key)
            } else {
                let right_floor = floor(&node.right, key);
                match right_floor {
                    Some(v) if v <= key => Some(v),
                    _ => Some(node.val),
                }
            }
        }
    }
}

fn main() {
    let root = Some(Box::new(Node {
        val: 10,
        left: Some(Box::new(Node {
            val: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            val: 20,
            left: Some(Box::new(Node {
                val: 12,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                val: 30,
                left: None,
                right: None,
            })),
        })),
    }));
    let result = floor(&root, 15);
    println!("{:?}", result);
}

A Some(12)

B Some(10)

C Some(20)

D None

💡 Hint

Floor is the greatest value less than or equal to the key.

The floor of 15 is 12 because 12 is the greatest value in the BST less than or equal to 15.

❓ Predict Output

intermediate

What is the ceil value for 13 in this BST?

Given the BST constructed by inserting these values in order: [8, 4, 12, 10, 14], what is the ceil of 13?

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
};

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

fn main() {
    let root = Some(Box::new(Node {
        val: 8,
        left: Some(Box::new(Node {
            val: 4,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            val: 12,
            left: Some(Box::new(Node {
                val: 10,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                val: 14,
                left: None,
                right: None,
            })),
        })),
    }));
    let result = ceil(&root, 13);
    println!("{:?}", result);
}

A Some(14)

B Some(12)

C Some(13)

D None

💡 Hint

Ceil is the smallest value greater than or equal to the key.

The ceil of 13 is 14 because 14 is the smallest value in the BST greater than or equal to 13.

🔧 Debug

advanced

Why does this floor function return incorrect results?

Consider this Rust function to find floor in BST. It sometimes returns None incorrectly. Identify the bug.

DSA Rust

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

A It should check left subtree when node.val < key, but it checks right subtree instead.

B It returns right_floor without checking if it's <= key, causing wrong floor values.

C It does not handle the case when root is None properly.

D It returns Some(node.val) even when node.val > key, causing incorrect floor.

💡 Hint

Check the condition on right_floor before returning it.

The function returns right_floor if it exists without verifying if right_floor <= key. This can cause returning a value greater than key, which is incorrect for floor.

🧠 Conceptual

advanced

What is the time complexity of finding floor or ceil in a balanced BST?

Assuming a balanced BST with n nodes, what is the time complexity to find floor or ceil of a key?

A O(n)

B O(1)

C O(n log n)

D O(log n)

💡 Hint

Think about the height of a balanced BST.

In a balanced BST, the height is about log n, so searching for floor or ceil takes O(log n) time.

🚀 Application

expert

After inserting [25, 15, 50, 10, 22, 35, 70] into an empty BST, what is the ceil of 23?

Insert the values in order into an empty BST. Then find the ceil of 23.

A 35

B 22

C 25

D 50

💡 Hint

Ceil is the smallest value >= key. Trace the path for 23.

The ceil of 23 is 25 because 25 is the smallest value in the BST greater than or equal to 23.

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