Floor and Ceil in BST in DSA Python - Deep Dive

Overview - Floor and Ceil in BST

What is it?

Floor and Ceil in a Binary Search Tree (BST) are two special values related to a given number. The floor is the greatest value in the BST that is less than or equal to the given number. The ceil is the smallest value in the BST that is greater than or equal to the given number. These help us quickly find close matches to a number in a sorted tree structure.

Why it matters

Without floor and ceil, finding the closest smaller or larger value to a number in a BST would require checking many nodes manually, which is slow. Floor and ceil let us answer these questions fast, which is useful in many real-world tasks like searching, range queries, and decision making. They make BSTs more powerful and practical.

Where it fits

Before learning floor and ceil, you should understand what a Binary Search Tree is and how it organizes data. After mastering floor and ceil, you can explore more complex tree queries like range searches, predecessor and successor nodes, and balanced BSTs like AVL or Red-Black trees.

Mental Model

Core Idea

Floor and ceil in a BST find the closest smaller-or-equal and larger-or-equal values to a target by using the tree's sorted structure to skip unnecessary parts.

Think of it like...

Imagine a bookshelf sorted by book height. If you want a book closest in height to a certain size, floor is the tallest book not taller than your size, and ceil is the shortest book not shorter than your size.

          [Root]
          /    \
     [Left]    [Right]

Floor search:
- If node value == target, floor is node value.
- If node value > target, go left.
- If node value < target, record node value as floor candidate, go right.

Ceil search:
- If node value == target, ceil is node value.
- If node value < target, go right.
- If node value > target, record node value as ceil candidate, go left.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how it organizes data to allow fast searching.

A Binary Search Tree is a tree where each node has up to two children. For every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This property helps us find values quickly by deciding to go left or right at each step.

Result

You can find if a number exists in the BST by comparing it to nodes and moving left or right accordingly.

Understanding BST structure is essential because floor and ceil rely on this sorted order to work efficiently.

2

Foundation

What Are Floor and Ceil Values?

Concept: Define floor and ceil in the context of numbers and BSTs.

Floor of a number is the greatest number less than or equal to it. Ceil is the smallest number greater than or equal to it. In a BST, these correspond to nodes closest to the target number without crossing it on either side.

Result

You know what floor and ceil mean and why they are useful to find close matches in sorted data.

Grasping these definitions helps you understand the goal of the search algorithms in the BST.

3

Intermediate

Finding Floor in a BST

🤔Before reading on: If the current node value is greater than the target, do you think we should go left or right? Commit to your answer.

Concept: Use BST properties to find the floor by moving left or right and keeping track of candidates.

Start at the root. If the node value equals the target, return it as floor. If node value is greater than target, move left because floor must be smaller or equal. If node value is less than target, record it as a floor candidate and move right to find a closer value.

Result

You get the largest value in the BST that is less than or equal to the target.

Knowing when to move left or right and when to record candidates is key to efficiently finding floor without checking all nodes.

4

Intermediate

Finding Ceil in a BST

🤔Before reading on: If the current node value is less than the target, should we go left or right? Commit to your answer.

Concept: Similar to floor, but reversed logic to find the smallest value greater than or equal to the target.

Start at the root. If node value equals target, return it as ceil. If node value is less than target, move right because ceil must be greater or equal. If node value is greater than target, record it as a ceil candidate and move left to find a closer value.

Result

You get the smallest value in the BST that is greater than or equal to the target.

This step shows the mirror logic of floor and how to use BST structure to find ceil efficiently.

5

Intermediate

Implementing Floor and Ceil in Python

🤔Before reading on: Do you think recursion or iteration is better for implementing floor and ceil? Commit to your answer.

Concept: Write clear Python functions to find floor and ceil using iterative BST traversal.

Define two functions floor_bst(root, target) and ceil_bst(root, target). Use a loop starting at root. For floor, if node value <= target, update floor candidate and go right; else go left. For ceil, if node value >= target, update ceil candidate and go left; else go right. Return candidate or None if not found.

Result

You have runnable Python code that returns floor and ceil values or None if no suitable value exists.

Implementing these functions solidifies understanding of the search logic and prepares you for practical use.

6

Advanced

Handling Edge Cases and Empty Subtrees

🤔Before reading on: What should floor or ceil return if no suitable value exists? Commit to your answer.

Concept: Learn how to handle cases where floor or ceil does not exist in the BST.

If all nodes are greater than target, floor does not exist and should return None. If all nodes are less than target, ceil does not exist and should return None. Also handle empty BST by returning None immediately. This avoids errors and clarifies function behavior.

Result

Your floor and ceil functions behave correctly even when no valid floor or ceil exists.

Knowing how to handle these cases prevents bugs and makes your code robust in real-world scenarios.

7

Expert

Optimizing Floor and Ceil for Balanced BSTs

🤔Before reading on: Do you think balancing the BST affects floor and ceil search speed? Commit to your answer.

Concept: Explore how balanced BSTs improve floor and ceil search time and how to maintain balance.

Balanced BSTs like AVL or Red-Black trees keep height low, ensuring floor and ceil searches run in O(log n) time. Unbalanced BSTs can degrade to linked lists with O(n) time. Maintaining balance during insertions and deletions keeps floor and ceil queries efficient.

Result

You understand the importance of tree balance for performance and how floor and ceil benefit from it.

Recognizing the impact of tree shape on search efficiency guides better data structure choices in production.

Under the Hood

Floor and ceil searches use BST's ordering to prune search paths. At each node, comparisons decide whether to move left or right, skipping entire subtrees that cannot contain valid answers. This reduces the search space from all nodes to a path from root to leaf, making the search efficient.

Why designed this way?

BSTs were designed to keep data sorted in a tree structure to allow fast search, insert, and delete. Floor and ceil leverage this design by using the ordering property to avoid scanning all nodes. Alternatives like unsorted trees or lists require full scans, which are slower.

Root
 │
 ├─ If node == target: return node
 ├─ If node > target: go left (possible floor/ceil candidate on left)
 └─ If node < target: go right (possible floor/ceil candidate on right)

Search path prunes subtrees that can't contain floor or ceil.

Myth Busters - 4 Common Misconceptions

Quick: If the target is smaller than all BST values, does floor exist? Commit to yes or no.

Common Belief: Floor always exists for any target in a BST.

Reality: Floor may not exist if the target is smaller than all values in the BST.

Why it matters: Assuming floor always exists can cause errors or wrong results when the target is very small.

Quick: Does floor always equal the target if the target is in the BST? Commit to yes or no.

Common Belief: If the target is in the BST, floor is always the target itself.

Reality: Yes, floor equals the target if it exists in the BST because floor is defined as less than or equal to target.

Why it matters: This is a true belief but learners often confuse floor with predecessor, which is strictly less than target.

Quick: Can you find floor or ceil by just doing an inorder traversal and picking values? Commit to yes or no.

Common Belief: You must traverse the entire BST inorder to find floor or ceil.

Reality: You can find floor and ceil efficiently by traversing only one path from root to leaf using BST properties.

Why it matters: Not using BST properties wastes time and defeats the purpose of using a BST.

Quick: Is floor always less than ceil for any target? Commit to yes or no.

Common Belief: Floor is always less than ceil for any target in BST.

Reality: Floor can equal ceil if the target exists in the BST or if floor and ceil are the same closest value.

Why it matters: Misunderstanding this can cause confusion in algorithms relying on floor and ceil.

Expert Zone

1

Floor and ceil searches can be implemented recursively or iteratively; iterative versions avoid call stack overhead in large trees.

2

In balanced BSTs, floor and ceil queries guarantee O(log n) time, but in skewed trees, worst-case time is O(n).

3

When duplicates exist in BST, floor and ceil definitions depend on whether duplicates go left or right; this affects which node is returned.

When NOT to use

If the data is not stored in a BST or is unsorted, floor and ceil searches require different approaches like binary search on arrays or linear scans. For very large datasets, balanced trees or specialized data structures like segment trees or interval trees may be better.

Production Patterns

Floor and ceil are used in database indexing to find range boundaries, in autocomplete systems to find closest matches, and in financial systems to find nearest price points. They are often combined with balanced BSTs or augmented trees for fast dynamic queries.

Connections

Binary Search on Sorted Arrays

Floor and ceil in BST are similar to finding insertion points using binary search in arrays.

Understanding floor and ceil in BST helps grasp how binary search finds closest smaller or larger elements in sorted lists.

Predecessor and Successor in BST

Floor and ceil relate closely to predecessor (largest smaller) and successor (smallest larger) nodes but include equality.

Knowing floor and ceil clarifies the difference between exact matches and strictly smaller or larger neighbors in BST.

Decision Boundaries in Machine Learning

Floor and ceil mimic finding thresholds or boundaries that separate data points in classification tasks.

Recognizing floor and ceil as boundary finders helps understand how algorithms decide class membership based on nearest values.

Common Pitfalls

#1 Returning None when target equals a node value instead of that node's value.

Wrong approach:

def floor_bst(root, target):
if root is None:
return None
if root.val == target:
return None # Wrong: should return root.val
if root.val > target:
return floor_bst(root.left, target)
floor_val = floor_bst(root.right, target)
return floor_val if floor_val is not None else root.val

Correct approach:

def floor_bst(root, target):
if root is None:
return None
if root.val == target:
return root.val # Correct: exact match
if root.val > target:
return floor_bst(root.left, target)
floor_val = floor_bst(root.right, target)
return floor_val if floor_val is not None else root.val

Root cause:

Confusing the condition for exact match causes missing the correct floor value.

#2 Not updating floor candidate when moving right on smaller node values.

Wrong approach:

def floor_bst(root, target):
floor_val = None
while root:
if root.val > target:
root = root.left
else:
root = root.right # Missing floor_val update
return floor_val

Correct approach:

def floor_bst(root, target):
floor_val = None
while root:
if root.val > target:
root = root.left
else:
floor_val = root.val # Update candidate
root = root.right
return floor_val

Root cause:

Forgetting to record the best floor candidate loses the correct answer.

#3 Assuming floor and ceil always exist and returning invalid values when they don't.

Wrong approach:

def ceil_bst(root, target):
ceil_val = 0 # Default to 0
while root:
if root.val < target:
root = root.right
else:
ceil_val = root.val
root = root.left
return ceil_val # Returns 0 even if no ceil exists

Correct approach:

def ceil_bst(root, target):
ceil_val = None
while root:
if root.val < target:
root = root.right
else:
ceil_val = root.val
root = root.left
return ceil_val # Returns None if no ceil exists

Root cause:

Using a default value instead of None hides the absence of a valid ceil.

Key Takeaways

Floor and ceil in a BST find the closest smaller-or-equal and larger-or-equal values to a target efficiently by using the tree's sorted structure.

They rely on moving left or right in the BST based on comparisons, recording candidates along the way to avoid checking all nodes.

Handling edge cases where floor or ceil does not exist is crucial for robust implementations.

Balanced BSTs ensure floor and ceil queries run fast, while unbalanced trees can degrade performance.

Understanding floor and ceil deepens knowledge of BST operations and connects to many real-world search and decision problems.

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