Floor and Ceil in BST in DSA Rust - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root node

↓

Compare target with current node value

↓

Go left

↓

Update floor

↓

Repeat until leaf or no child

↓

Return floor and ceil values

Start at the root, compare target with node value, move left or right updating floor or ceil accordingly until no more moves, then return results.

Execution Sample

DSA Rust

fn floor_ceil_bst(root: &Option<Box<Node>>, target: i32) -> (Option<i32>, Option<i32>) {
    let mut floor = None;
    let mut ceil = None;
    let mut current = root;
    while let Some(node) = current {
        if node.val == target {
            return (Some(node.val), Some(node.val));
        } else if node.val > target {
            ceil = Some(node.val);
            current = &node.left;
        } else {
            floor = Some(node.val);
            current = &node.right;
        }
    }
    (floor, ceil)
}

Find floor and ceil of target in BST by traversing from root, updating floor and ceil based on comparisons.

Execution Table

Step	Operation	Current Node Value	Target	Floor	Ceil	Pointer Move	Visual State
1	Start at root	8	6	None	None	Compare 6 with 8	8 / \ 3 10 / \ 1 6 14
2	6 < 8, update ceil	8	6	None	8	Move left to 3	8 / \ 3 10 / \ 1 6 14
3	Compare 6 with 3	3	6	3	8	3 < 6, update floor	8 / \ 3 10 / \ 1 6 14
4	Move right to 6	3	6	3	8	Move right to 6	8 / \ 3 10 / \ 1 6 14
5	Compare 6 with 6	6	6	3	8	Equal, set floor and ceil to 6	8 / \ 3 10 / \ 1 6 14
6	Return result	6	6	6	6	Stop	8 / \ 3 10 / \ 1 6 14

💡 Found node with value equal to target 6 at step 5, so floor and ceil both are 6.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
floor	None	None	3	3	3	6
ceil	None	8	8	8	8	6
current node	8	3	3	6	6	None (end)

Key Moments - 3 Insights

Why do we update floor when current node value is less than target?

Because floor is the greatest value less than or equal to target. When node.val < target, node.val is a candidate for floor. See execution_table step 3 and 4 where floor updates to 3.

Why do we update ceil when current node value is greater than or equal to target?

Because ceil is the smallest value greater than or equal to target. When node.val >= target, node.val is a candidate for ceil. See execution_table step 2 where ceil updates to 8.

What happens when we find a node equal to target?

We set both floor and ceil to that node's value and stop searching. See execution_table step 5 where node.val == target 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the floor value?

A 3

B None

C 6

D 8

💡 Hint

Check the 'Floor' column at step 4 in execution_table.

At which step does the algorithm stop searching?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where current node value equals target in execution_table.

If the target was 5 instead of 6, what would happen to the ceil value at step 2?

A It would remain None

B It would update to 8

C It would update to 3

D It would update to 6

💡 Hint

See how ceil updates when node.val >= target in execution_table step 2.

Concept Snapshot

Floor and Ceil in BST:
- Floor: greatest value <= target
- Ceil: smallest value >= target
- Start at root, compare target with node
- Move left if node.val > target (update ceil)
- Move right if node.val <= target (update floor)
- Stop when node.val == target or no child

Full Transcript

This visualization shows how to find floor and ceil values in a Binary Search Tree (BST) for a given target. Starting at the root node, we compare the target with the current node's value. If the current node's value is less than the target, we update the floor to this value and move to the right child. If the current node's value is greater than the target, we update the ceil to this value and move to the left child. If we find a node with value equal to the target, we set both floor and ceil to this value and stop. The execution table traces these steps with the current node, floor, and ceil values. The variable tracker shows how floor, ceil, and current node change at each step. Key moments clarify why floor and ceil update as they do and what happens when the target is found. The quiz tests understanding of these steps and updates. This method efficiently finds floor and ceil in O(h) time, where h is the tree height.

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