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

Floor and Ceil in BST

📖 Scenario: You are working with a phone book application that stores contacts in a Binary Search Tree (BST) by their phone numbers. You want to find the closest existing phone number that is less than or equal to a given number (floor), and the closest existing phone number that is greater than or equal to a given number (ceil).

🎯 Goal: Build a program that creates a BST with given phone numbers, then finds the floor and ceil values for a specific phone number query.

📋 What You'll Learn

Create a BST by inserting given phone numbers in order

Implement functions to find floor and ceil values in the BST for a given number

Print the floor and ceil values for the query number

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases often use BSTs to store sorted data for quick search and retrieval of closest matches.

💼 Career

Understanding BST operations like floor and ceil is important for software engineers working on search engines, databases, and real-time data processing.

1

Create BST Node class and insert function

Create a class called Node with attributes data, left, and right. Then create a function called insert that takes a root node and a key integer, and inserts the key into the BST following BST rules. Insert these phone numbers in order: 50, 30, 70, 20, 40, 60, 80. Store the root node in a variable called root.

DSA Python

# Define Node class and insert function
# Insert the numbers 50, 30, 70, 20, 40, 60, 80 into BST
# Store the root in variable root
# Your code here

Hint

Remember, in BST insertion, smaller values go to the left subtree, larger values to the right subtree.

2

Create floor and ceil helper variables

Create two variables called floor_val and ceil_val and set both to None. These will store the floor and ceil values found in the BST.

DSA Python

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

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

root = None
for number in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, number)

# Create floor_val and ceil_val variables set to None
# Your code here

Hint

Initialize both variables to None before searching.

3

Implement floor and ceil functions

Write two functions: find_floor(root, key) and find_ceil(root, key). Each function takes the BST root and a key integer. find_floor returns the greatest value in the BST less than or equal to the key, or None if none exists. find_ceil returns the smallest value in the BST greater than or equal to the key, or None if none exists. Use BST properties to traverse efficiently.

DSA Python

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

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

root = None
for number in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, number)

floor_val = None
ceil_val = None

# Define find_floor(root, key) function
# Define find_ceil(root, key) function
# Your code here

Hint

Use a loop to traverse the BST. Update floor when current node is less than key, update ceil when current node is greater than key.

4

Find and print floor and ceil for query

Set a variable called query to 65. Use the find_floor and find_ceil functions with root and query to find floor and ceil values. Store results in floor_val and ceil_val. Print the floor and ceil values exactly as: Floor: <floor_val> and Ceil: <ceil_val>.

DSA Python

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key  key:
            current = current.left
        else:
            floor = current.data
            current = current.right
    return floor

def find_ceil(root, key):
    ceil = None
    current = root
    while current:
        if current.data == key:
            return current.data
        if current.data < key:
            current = current.right
        else:
            ceil = current.data
            current = current.left
    return ceil

# Set query to 65
# Find floor_val and ceil_val using find_floor and find_ceil
# Print floor_val and ceil_val as shown
# Your code here

Hint

Use the functions to get floor and ceil, then print them exactly as shown.

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