Why Floor and Ceil in BST in DSA Python?

The Big Idea

What if you could find the closest match instantly without checking every option?

The Scenario

Imagine you have a big phone book sorted by names. You want to find the closest name that is just before or just after a given name. Doing this by flipping pages one by one is slow and tiring.

The Problem

Looking for the closest smaller or larger name manually means checking many entries one by one. This takes a lot of time and you can easily miss the right spot or get confused.

The Solution

Using a special tree called a Binary Search Tree (BST), you can quickly jump to the closest smaller (floor) or larger (ceil) value without checking every entry. This saves time and reduces mistakes.

Before vs After

✗ Before

names = ['Alice', 'Bob', 'Charlie', 'David']
floor = None
for name in names:
    if name <= 'Carl':
        floor = name
print(floor)

✓ After

def floor_in_bst(root, key):
    floor = None
    while root:
        if root.val == key:
            return root.val
        elif root.val > key:
            root = root.left
        else:
            floor = root.val
            root = root.right
    return floor

What It Enables

This lets you find the closest smaller or larger value in a sorted structure instantly, making searching smarter and faster.

Real Life Example

When booking flights, you might want the closest earlier or later flight time than your preferred time. Floor and ceil in BST help find these quickly.

Key Takeaways

Manual search is slow and error-prone for closest smaller/larger values.

Floor and ceil in BST use tree structure to jump directly to answers.

This makes searching efficient and reliable in sorted data.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The greatest value in the BST less than or equal to the given value

B. The smallest value in the BST greater than or equal to the given value

C. The root value of the BST

D. The average of all values in the BST

Solution

1. Step 1: Understand the floor concept 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 ceil is the smallest value greater than or equal to the given value, so The smallest value in the BST greater than or equal to the given value is incorrect. Options C and D do not relate to floor.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option A

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest value ≤ target in BST [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is the smallest value
• Assuming floor is always the root

2. Which of the following is the correct Python function signature to find the ceil of a value in a BST node?

easy

A. def ceil_find(value, root):

B. def find_ceil(root, value):

C. def findCeil(value):

D. def ceil(root):

Solution

1. Step 1: Check common parameter order for BST functions

   Functions usually take the root node first, then the value to search for.

2. Step 2: Validate each option

   def find_ceil(root, value): matches this order and naming convention. Options B, C, and D either have wrong parameter order or missing parameters.

3. Final Answer:

   def find_ceil(root, value): -> Option B

4. Quick Check:

   Function(root, value) is standard [OK]

Hint: Root node first, then value in function parameters [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Using unclear function names

3. Given the BST below and value = 14, what is the floor of 14?

       15
      /  \
     10   20
    /  \    \
   8   12    25

medium

A. 14

B. 15

C. 12

D. 10

Solution

1. Step 1: Locate values less than or equal to 14 in BST

   Values ≤ 14 are 10, 8, 12. 15 and above are greater.

2. Step 2: Find the greatest among these

   The greatest value ≤ 14 is 12.

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Floor(14) = 12 [OK]

Hint: Floor ≤ value, pick largest from left subtree [OK]

Common Mistakes:

• Choosing 15 which is greater than 14
• Assuming floor equals the value if not present
• Picking smallest value instead of largest ≤ value

4. Consider this buggy Python code to find ceil in BST:

def find_ceil(root, value):
    if root is None:
        return None
    if root.val == value:
        return root.val
    if root.val < value:
        return find_ceil(root.right, value)
    else:
        ceil = find_ceil(root.left, value)
        return ceil if ceil is not None else root.val

What is the main error?

medium

A. It should check for None before recursion

B. It should return root.val when root.val == value

C. It should recurse on root.right when root.val > value

D. It should recurse on root.right when root.val < value

Solution

1. Step 1: Analyze recursion direction for ceil

   If root.val < value, ceil must be in right subtree, so recurse on root.right.

2. Step 2: Identify incorrect recursion

   Code incorrectly recurses on root.left when root.val < value, which is wrong.

3. Final Answer:

   It should recurse on root.right when root.val < value -> Option D

4. Quick Check:

   Ceil search goes right if root.val < value [OK]

Hint: Go right if node value < target for ceil [OK]

Common Mistakes:

• Recursing left instead of right
• Confusing floor and ceil logic
• Not handling None cases properly

5. You have a BST with values [5, 10, 15, 20, 25]. You want to find the floor and ceil of 17. Which pair is correct?

hard

A. Floor = 15, Ceil = 20

B. Floor = 20, Ceil = 25

C. Floor = 10, Ceil = 15

D. Floor = 17, Ceil = 17

Solution

1. Step 1: Identify floor of 17 in BST

   Floor is greatest value ≤ 17. Values ≤ 17 are 5, 10, 15. Greatest is 15.

2. Step 2: Identify ceil of 17 in BST

   Ceil is smallest value ≥ 17. Values ≥ 17 are 20, 25. Smallest is 20.

3. Final Answer:

   Floor = 15, Ceil = 20 -> Option A

4. Quick Check:

   Floor ≤ 17 = 15, Ceil ≥ 17 = 20 [OK]

Hint: Floor ≤ value, ceil ≥ value in sorted BST [OK]

Common Mistakes:

• Choosing floor or ceil outside BST values
• Assuming floor or ceil equals the value if not present
• Mixing floor and ceil values