Floor and Ceil in BST in DSA Python

Mental Model

Floor is the biggest value smaller or equal to target; ceil is the smallest value bigger or equal to target in a BST.

Analogy: Imagine standing on a number line with houses numbered in order. Floor is the closest house number you can stand on or just before your target, ceil is the closest house number you can reach or just after your target.

       8
      / \
     4   12
    / \   / \
   2   6 10  14

Dry Run Walkthrough

Input: BST: 8->4->12->2->6->10->14, find floor and ceil of 5

Goal: Find the floor (largest ≤5) and ceil (smallest ≥5) values in the BST

Step 1: Start at root node 8, compare 5 with 8

Current node: 8

Why: We start from the root to find floor and ceil

Step 2: Since 5 < 8, move to left child 4; update ceil to 8

Current node: 4, ceil=8

Why: 5 is less than 8, so 8 could be ceil; floor not updated

Step 3: Since 5 > 4, move to right child 6; update floor to 4

Current node: 6, floor=4, ceil=8

Why: 5 is greater than 4, so 4 could be floor

Step 4: Since 5 < 6, move to left child which is null; update ceil to 6

Current node: null, floor=4, ceil=6

Why: 5 less than 6, so 6 could be ceil; no more nodes to check

Result:

Floor: 4, Ceil: 6

Annotated Code

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_ceil_bst(root, target):
    floor = None
    ceil = None
    curr = root
    while curr:
        if curr.val == target:
            floor = curr.val
            ceil = curr.val
            break
        elif target < curr.val:
            ceil = curr.val  # update ceil to current node
            curr = curr.left  # move left to find smaller or equal
        else:
            floor = curr.val  # update floor to current node
            curr = curr.right  # move right to find bigger or equal
    return floor, ceil

# Driver code
root = None
for v in [8,4,12,2,6,10,14]:
    root = insert(root, v)

floor_val, ceil_val = floor_ceil_bst(root, 5)
print(f"Floor: {floor_val}, Ceil: {ceil_val}")

while curr:

loop through nodes until no more to check

if curr.val == target:

exact match found, floor and ceil are target

elif target < curr.val:

target less than current, update ceil and go left

ceil = curr.val # update ceil to current node

record current node as possible ceil

curr = curr.left # move left to find smaller or equal

go left to find closer floor or ceil

else:

target greater than current, update floor and go right

floor = curr.val # update floor to current node

record current node as possible floor

curr = curr.right # move right to find bigger or equal

go right to find closer floor or ceil

Output

Floor: 4, Ceil: 6

Complexity Analysis

Time: O(h) where h is the height of the BST because we traverse from root down to a leaf at most once

Space: O(1) because we use only a few variables and no extra data structures

vs Alternative: Compared to scanning all nodes (O(n)), this approach is faster because BST properties let us skip large parts of the tree

Edge Cases

target smaller than all nodes

floor remains None, ceil is smallest node

DSA Python

elif target < curr.val:

target larger than all nodes

ceil remains None, floor is largest node

DSA Python

else:

target equals a node value

floor and ceil both equal target

DSA Python

if curr.val == target:

When to Use This Pattern

When you need closest smaller or larger values in a sorted tree, use floor and ceil in BST to quickly find them using tree traversal.

Common Mistakes

Mistake: Not updating floor or ceil correctly when moving left or right
Fix: Update floor when moving right and ceil when moving left to keep track of closest candidates

Summary

Finds the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a BST.

Use when you want to quickly find bounds around a value in a sorted tree structure.

The key is to update floor and ceil while traversing down the tree based on comparisons.

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