Floor and Ceil in BST in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a value into the BST.

DSA Rust

fn insert(root: &mut Option<Box<TreeNode>>, val: i32) {
    match root {
        None => *root = Some(Box::new(TreeNode { val, left: None, right: None })),
        Some(node) => {
            if val < node.val {
                insert(&mut node.left, [1]);
            } else {
                insert(&mut node.right, val);
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Aval

Bval + 1

Cval - 1

Dnode.val

Attempts:

3 left

💡 Hint

Common Mistakes

Passing a modified value instead of the original 'val'.

Using node.val instead of val.

We must pass the value to insert unchanged to the recursive call.

2fill in blank

medium

Complete the code to find the floor value in BST for a given key.

DSA Rust

fn floor(root: &Option<Box<TreeNode>>, 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 {
                    [1]
                }
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

ASome(node.val)

BNone

CSome(key)

DSome(node.right.as_ref()?.val)

Attempts:

3 left

💡 Hint

Common Mistakes

Returning None instead of current node's value.

Returning key or right child's value incorrectly.

If right subtree has no floor, current node's value is the floor.

3fill in blank

hard

Fix the error in the ceil function to correctly find the ceil value in BST.

DSA Rust

fn ceil(root: &Option<Box<TreeNode>>, 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);
                if left_ceil.is_some() {
                    left_ceil
                } else {
                    [1]
                }
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

ASome(node.left.as_ref()?.val)

BNone

CSome(key)

DSome(node.val)

Attempts:

3 left

💡 Hint

Common Mistakes

Returning None instead of current node's value.

Returning left child's value incorrectly.

If left subtree has no ceil, current node's value is the ceil.

4fill in blank

hard

Fill both blanks to complete the function that finds floor and ceil in BST.

DSA Rust

fn floor_ceil(root: &Option<Box<TreeNode>>, key: i32) -> (Option<i32>, Option<i32>) {
    match root {
        None => (None, None),
        Some(node) => {
            if node.val == key {
                (Some(node.val), Some(node.val))
            } else if node.val > key {
                let (floor, ceil) = floor_ceil(&node.left, key);
                (floor, [1])
            } else {
                let (floor, ceil) = floor_ceil(&node.right, key);
                ([2], ceil)
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

ASome(node.val)

BNone

CSome(key)

DSome(node.left.as_ref()?.val)

Attempts:

3 left

💡 Hint

Common Mistakes

Returning None instead of node.val for floor or ceil.

Mixing floor and ceil values.

When node.val > key, ceil is node.val; when node.val < key, floor is node.val.

5fill in blank

hard

Fill all three blanks to complete the function that prints floor and ceil for a list of keys.

DSA Rust

fn print_floor_ceil(root: &Option<Box<TreeNode>>, keys: &[i32]) {
    for &key in keys {
        let (floor, ceil) = floor_ceil(root, key);
        println!("Key: {}, Floor: {:?}, Ceil: {:?}", [1], [2], [3]);
    }
}

Drag options to blanks, or click blank then click option'

Afloor.unwrap_or(-1)

Bceil.unwrap_or(-1)

Ckey

Dfloor

Attempts:

3 left

💡 Hint

Common Mistakes

Printing Option types directly without unwrap_or.

Mixing order of floor and ceil in print.

Print key, floor (or -1 if None), and ceil (or -1 if None) for each key.

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