Floor and Ceil in BST in DSA Rust - Build from Scratch

Floor and Ceil in BST

📖 Scenario: You are building a simple search feature for a sorted collection of numbers stored in a Binary Search Tree (BST). You want to find the closest smaller or equal number (floor) and the closest greater or equal number (ceil) for a given number.

🎯 Goal: Build a Rust program that creates a BST, sets a target number, finds the floor and ceil values in the BST for that target, and prints the results.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 10, 30, 5, 15, 25, 35

Set a target number variable called target with the value 16

Implement functions floor_in_bst and ceil_in_bst to find floor and ceil values

Print the floor and ceil values for the target number

💡 Why This Matters

🌍 Real World

Finding floor and ceil values is useful in search engines, recommendation systems, and databases where you want to find closest matches to a query.

💼 Career

Understanding BSTs and how to find floor and ceil values is important for software engineers working on efficient data retrieval, indexing, and real-time search features.

1

Create the BST structure and insert nodes

Create a struct called Node with fields val: i32, left: Option>, and right: Option>. Then create a function insert to add nodes to the BST. Finally, create the root node with value 20 and insert the nodes 10, 30, 5, 15, 25, and 35 into the BST.

DSA Rust

// Define Node struct and insert function
// Create root node with value 20
// Insert nodes 10, 30, 5, 15, 25, 35
// Your code here

Hint

Define the Node struct with val, left, and right. Use Option> for children. Implement insert to add values correctly. Create root and insert given values.

2

Set the target number

Create a variable called target and set it to the integer value 16.

DSA Rust

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

impl Node {
    fn new(val: i32) -> Self {
        Node { val, left: None, right: None }
    }

    fn insert(&mut self, val: i32) {
        if val  left_node.insert(val),
                None => self.left = Some(Box::new(Node::new(val))),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node::new(val))),
            }
        }
    }
}

fn main() {
    let mut root = Node::new(20);
    root.insert(10);
    root.insert(30);
    root.insert(5);
    root.insert(15);
    root.insert(25);
    root.insert(35);
    // Create target variable with value 16
    // Your code here
}

Hint

Simply create a variable named target and assign it the value 16.

3

Implement floor and ceil functions

Write two functions: floor_in_bst and ceil_in_bst. Each takes a reference to a Node and an integer target. floor_in_bst returns the greatest value in the BST less than or equal to target as Option. ceil_in_bst returns the smallest value in the BST greater than or equal to target as Option. Use recursion and BST properties to find these values efficiently.

DSA Rust

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

impl Node {
    fn new(val: i32) -> Self {
        Node { val, left: None, right: None }
    }

    fn insert(&mut self, val: i32) {
        if val  left_node.insert(val),
                None => self.left = Some(Box::new(Node::new(val))),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node::new(val))),
            }
        }
    }
}

fn floor_in_bst(node: &Node, target: i32) -> Option {
    // Your code here
}

fn ceil_in_bst(node: &Node, target: i32) -> Option {
    // Your code here
}

fn main() {
    let mut root = Node::new(20);
    root.insert(10);
    root.insert(30);
    root.insert(5);
    root.insert(15);
    root.insert(25);
    root.insert(35);
    let target = 16;
}

Hint

Use recursion. For floor: if current node value is greater than target, go left; if smaller, check right subtree or current node. For ceil: if current node value is smaller than target, go right; if greater, check left subtree or current node.

4

Print the floor and ceil values

Use println! to print the floor and ceil values for the target variable. Print exactly these two lines:
Floor value: <floor_value>
Ceil value: <ceil_value>
where <floor_value> and <ceil_value> are the results from calling floor_in_bst(&root, target) and ceil_in_bst(&root, target) respectively. Use unwrap() to get the values from the Option.

DSA Rust

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

impl Node {
    fn new(val: i32) -> Self {
        Node { val, left: None, right: None }
    }

    fn insert(&mut self, val: i32) {
        if val  left_node.insert(val),
                None => self.left = Some(Box::new(Node::new(val))),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node::new(val))),
            }
        }
    }
}

fn floor_in_bst(node: &Node, target: i32) -> Option {
    if node.val == target {
        return Some(node.val);
    } else if node.val > target {
        match &node.left {
            Some(left_node) => floor_in_bst(left_node, target),
            None => None,
        }
    } else {
        let right_floor = match &node.right {
            Some(right_node) => floor_in_bst(right_node, target),
            None => None,
        };
        match right_floor {
            Some(val) => Some(val),
            None => Some(node.val),
        }
    }
}

fn ceil_in_bst(node: &Node, target: i32) -> Option {
    if node.val == target {
        return Some(node.val);
    } else if node.val  ceil_in_bst(right_node, target),
            None => None,
        }
    } else {
        let left_ceil = match &node.left {
            Some(left_node) => ceil_in_bst(left_node, target),
            None => None,
        };
        match left_ceil {
            Some(val) => Some(val),
            None => Some(node.val),
        }
    }
}

fn main() {
    let mut root = Node::new(20);
    root.insert(10);
    root.insert(30);
    root.insert(5);
    root.insert(15);
    root.insert(25);
    root.insert(35);
    let target = 16;

    // Print floor and ceil values
    println!("Floor value: {}", floor_in_bst(&root, target).unwrap());
    println!("Ceil value: {}", ceil_in_bst(&root, target).unwrap());
}

Hint

Call floor_in_bst(&root, target) and ceil_in_bst(&root, target). Use unwrap() to get the values and print them with println!.

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