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

Challenge - 5 Problems

❓ Predict Output

intermediate

Find floor value in BST

What is the floor value of 15 in the given BST after inserting the values [10, 5, 15, 12, 18]?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def floor_bst(root, key):
    floor_val = -1
    while root:
        if root.val == key:
            return root.val
        if root.val > key:
            root = root.left
        else:
            floor_val = root.val
            root = root.right
    return floor_val

root = None
for v in [10, 5, 15, 12, 18]:
    root = insert(root, v)
print(floor_bst(root, 15))

A 15

B 12

C 10

D 18

💡 Hint

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

The floor of 15 is 15 itself because 15 exists in the BST.

❓ Predict Output

intermediate

Find ceil value in BST

What is the ceil value of 14 in the BST after inserting [20, 8, 22, 4, 12, 10, 14]?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def ceil_bst(root, key):
    ceil_val = -1
    while root:
        if root.val == key:
            return root.val
        if root.val < key:
            root = root.right
        else:
            ceil_val = root.val
            root = root.left
    return ceil_val

root = None
for v in [20, 8, 22, 4, 12, 10, 14]:
    root = insert(root, v)
print(ceil_bst(root, 14))

A 10

B 12

C 20

D 14

💡 Hint

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

14 exists in the BST, so ceil is 14 itself.

🧠 Conceptual

advanced

Floor and Ceil when key not present

In a BST with values [5, 10, 15, 20, 25], what are the floor and ceil values for key = 17?

A Floor: 15, Ceil: 20

B Floor: 15, Ceil: 25

C Floor: 10, Ceil: 15

D Floor: 20, Ceil: 25

💡 Hint

Floor is largest smaller or equal, ceil is smallest greater or equal.

17 is between 15 and 20, so floor is 15 and ceil is 20.

🔧 Debug

advanced

Identify error in floor function

What error will this floor function produce when called with key=7 on BST with [5, 10, 15]? ```python def floor_bst(root, key): floor_val = None while root: if root.val == key: return root.val if root.val < key: floor_val = root.val root = root.left else: root = root.right return floor_val ```

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

root = None
for v in [5, 10, 15]:
    root = insert(root, v)
print(floor_bst(root, 7))

A Infinite loop

B Returns 5

C Returns None

D AttributeError

💡 Hint

Check the direction of traversal when root.val < key.

The code incorrectly moves left when root.val < key, missing larger values on right. For key=7, it returns None.

🚀 Application

expert

Count nodes between floor and ceil in BST

Given a BST with values [8, 3, 10, 1, 6, 14, 4, 7, 13], how many nodes have values between floor(5) and ceil(11) inclusive?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def floor_bst(root, key):
    floor_val = -1
    while root:
        if root.val == key:
            return root.val
        if root.val > key:
            root = root.left
        else:
            floor_val = root.val
            root = root.right
    return floor_val

def ceil_bst(root, key):
    ceil_val = -1
    while root:
        if root.val == key:
            return root.val
        if root.val < key:
            root = root.right
        else:
            ceil_val = root.val
            root = root.left
    return ceil_val

def count_in_range(root, low, high):
    if root is None:
        return 0
    if root.val < low:
        return count_in_range(root.right, low, high)
    if root.val > high:
        return count_in_range(root.left, low, high)
    return 1 + count_in_range(root.left, low, high) + count_in_range(root.right, low, high)

root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)
floor_val = floor_bst(root, 5)
ceil_val = ceil_bst(root, 11)
print(count_in_range(root, floor_val, ceil_val))

A 4

B 6

C 7

D 5

💡 Hint

Find floor and ceil first, then count nodes in that range.

Floor(5) = 4, Ceil(11) = 13. Nodes in [4,13] are 4,6,7,8,10,13 → 6 nodes.

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