Floor and Ceil in BST in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the floor value in a BST.

DSA Python

def floor_in_bst(root, key):
    floor_val = None
    current = root
    while current:
        if current.val == key:
            return current.val
        elif current.val > key:
            current = current.[1]
        else:
            floor_val = current.val
            current = current.right
    return floor_val

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

Aparent

Bright

Cleft

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Going right when current value is greater than key causes wrong floor value.

Returning None too early without checking left subtree.

To find the floor, if current node's value is greater than key, move to left child to find smaller values.

2fill in blank

medium

Complete the code to find the ceil value in a BST.

DSA Python

def ceil_in_bst(root, key):
    ceil_val = None
    current = root
    while current:
        if current.val == key:
            return current.val
        elif current.val < key:
            current = current.[1]
        else:
            ceil_val = current.val
            current = current.left
    return ceil_val

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

Aleft

Broot

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Going left when current value is smaller than key causes wrong ceil value.

Returning None too early without checking right subtree.

If current node's value is less than key, move right to find bigger values for ceil.

3fill in blank

hard

Fix the error in the code to correctly find floor in BST.

DSA Python

def floor_in_bst(root, key):
    floor_val = None
    current = root
    while current:
        if current.val == key:
            return current.val
        elif current.val < key:
            floor_val = current.val
            current = current.[1]
        else:
            current = current.left
    return floor_val

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

Aright

Bleft

Cparent

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Going left when current value is less than key causes missing closer floor values.

Not updating floor_val correctly.

When current value is less than key, move right to find a closer floor value.

4fill in blank

hard

Fill both blanks to complete the code that finds ceil in BST.

DSA Python

def ceil_in_bst(root, key):
    ceil_val = None
    current = root
    while current:
        if current.val == key:
            return current.val
        elif current.val [1] key:
            current = current.[2]
        else:
            ceil_val = current.val
            current = current.left
    return ceil_val

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

A>

B<

Cright

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operator causes wrong traversal.

Going left instead of right when current value is less than key.

If current value is less than key, go right to find bigger values for ceil.

5fill in blank

hard

Fill all three blanks to complete the code that finds floor in BST.

DSA Python

def floor_in_bst(root, key):
    floor_val = None
    current = root
    while current:
        if current.val == key:
            return current.val
        elif current.val [1] key:
            floor_val = current.val
            current = current.[2]
        else:
            current = current.[3]
    return floor_val

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

A<

Bright

Cleft

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping left and right child traversal.

Not updating floor_val when current value is less than key.

If current value is less than key, update floor and go right; else go left.

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