Floor and Ceil in BST in DSA C - Deep Dive

Overview - Floor and Ceil in BST

What is it?

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

Why it matters

Without floor and ceil operations, finding the closest smaller or larger value to a number in a BST would require scanning many nodes, losing the speed advantage of BSTs. These operations allow efficient searching for approximate matches, which is useful in many real-world tasks like searching ranges, scheduling, or data retrieval. Without them, many applications would be slower and less responsive.

Where it fits

Before learning floor and ceil in BST, you should understand what a Binary Search Tree is and how searching works in it. After mastering floor and ceil, you can explore related topics like range queries, predecessor and successor in BST, 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 BST'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 but not taller than a certain size (floor), you look left until you find the tallest book that fits. For the smallest book not shorter than that size (ceil), you look right until you find the shortest book that fits.

          [Root]
          /    \
      [Left]  [Right]

Floor search: move left if current node > target, else record current and move right.
Ceil search: move right if current node < target, else record current and move left.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its structure helps in searching values efficiently.

A Binary Search Tree is a tree where each node has up to two children. For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property allows searching for a value by comparing and moving left or right, skipping half the tree each step.

Result

You can find if a value exists in the BST in O(h) time, where h is the tree height.

Understanding BST structure is essential because floor and ceil operations rely on this sorted property to find closest values efficiently.

2

Foundation

Defining Floor and Ceil Concepts

Concept: Introduce what floor and ceil mean in the context of numbers and BST values.

Floor of a number is the greatest value less than or equal to it. Ceil is the smallest value greater than or equal to it. For example, floor(7) in [2,5,8,10] is 5, ceil(7) is 8.

Result

You understand the goal: find these closest values in the BST for any target number.

Knowing these definitions helps you see why simple search isn't enough; you need to track candidates as you traverse.

3

Intermediate

Finding Floor in BST by Traversal

🤔Before reading on: do you think you should move left or right when current node value is less than the target to find floor? Commit to your answer.

Concept: Floor search moves through the BST, updating the best candidate when current node is less than or equal to target, and deciding direction based on comparison.

Start at root. If current node value equals target, floor is found. If current node value is greater than target, move left to find smaller values. If less, record current node as floor candidate and move right to find closer values.

Result

You get the greatest value less than or equal to target in O(h) time.

Understanding how to update the candidate and choose direction lets you find floor without checking all nodes.

4

Intermediate

Finding Ceil in BST by Traversal

🤔Before reading on: do you think you should move left or right when current node value is greater than the target to find ceil? Commit to your answer.

Concept: Ceil search is similar to floor but reversed: update candidate when current node is greater than or equal to target, and move accordingly.

Start at root. If current node value equals target, ceil is found. If current node value is less than target, move right to find larger values. If greater, record current node as ceil candidate and move left to find closer values.

Result

You get the smallest value greater than or equal to target in O(h) time.

Knowing when to update candidate and direction ensures efficient ceil search without full traversal.

5

Intermediate

Implementing Floor and Ceil in C

Concept: Translate the floor and ceil logic into C code using BST node structure and recursion or iteration.

Use a struct Node with int data and left/right pointers. For floor, start at root, compare, update candidate pointer, and move left or right accordingly until NULL. Same for ceil with reversed conditions. Return candidate's data or -1 if none found.

Result

You have working C functions that return floor and ceil values for any target in a BST.

Implementing these functions solidifies understanding and prepares for practical use.

6

Advanced

Handling Edge Cases and Empty BST

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

Concept: Consider cases where no floor or ceil exists, such as target smaller than all nodes or larger than all nodes, and empty tree.

If BST is empty, return -1 or a sentinel value. If no floor (all nodes > target), return -1. If no ceil (all nodes < target), return -1. Check candidate pointer before returning result.

Result

Your functions handle all inputs gracefully without errors or wrong answers.

Anticipating edge cases prevents bugs and ensures robust code in real applications.

7

Expert

Optimizing Floor and Ceil in Balanced BSTs

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

Concept: Balanced BSTs keep height low, improving worst-case search time for floor and ceil to O(log n). Also, internal node caching or threaded BSTs can speed repeated queries.

Using AVL or Red-Black trees ensures height is O(log n), so floor and ceil searches are fast even in worst cases. Advanced implementations may store parent pointers or augment nodes with extra info to speed up queries.

Result

Floor and ceil operations become consistently fast and scalable for large datasets.

Knowing how tree structure affects performance helps design efficient systems and choose the right data structure.

Under the Hood

Floor and ceil searches use BST's property that left subtree has smaller values and right subtree has larger values. By comparing target with current node, the algorithm decides which subtree to explore next, while keeping track of the best candidate found so far. This avoids visiting unnecessary nodes, making the search efficient.

Why designed this way?

BSTs were designed to allow fast search by ordering nodes. Floor and ceil operations leverage this ordering to find approximate matches quickly. Alternatives like linear search would be slower. The design balances simplicity and efficiency, making these operations intuitive and fast.

          [Current Node]
           /        \
    Smaller Values  Larger Values

Floor search:
If node > target -> go left
Else record node, go right

Ceil search:
If node < target -> go right
Else record node, go left

Myth Busters - 4 Common Misconceptions

Quick: If the target value exists in the BST, do floor and ceil always return that exact value? Commit yes or no.

Common Belief: Floor and ceil always return the target value if it exists in the BST.

Reality: Yes, if the target exists, floor and ceil both return the target itself because it is both the greatest less-or-equal and smallest greater-or-equal value.

Why it matters: Knowing this prevents unnecessary searching beyond the found node and helps optimize code by stopping early.

Quick: Can floor or ceil return a value that is not present in the BST? Commit yes or no.

Common Belief: Floor or ceil can return values not present in the BST, like the target itself if missing.

Reality: Floor and ceil always return values from the BST nodes, never arbitrary numbers or the target if it is not present.

Why it matters: This clarifies that floor and ceil find closest existing values, not hypothetical ones, which is important for correct application.

Quick: Does floor always come from the left subtree and ceil always from the right subtree? Commit yes or no.

Common Belief: Floor is always in the left subtree and ceil always in the right subtree of the target node.

Reality: Floor and ceil can come from either subtree depending on the traversal path and comparisons; they are not restricted to one side.

Why it matters: Misunderstanding this can lead to incorrect implementations that miss valid floor or ceil values.

Quick: Is the time complexity of floor and ceil search always O(log n) in any BST? Commit yes or no.

Common Belief: Floor and ceil search always take O(log n) time because BSTs are balanced.

Reality: In unbalanced BSTs, worst-case time can degrade to O(n) if the tree is skewed.

Why it matters: This affects performance expectations and guides the choice of balanced BSTs for reliable speed.

Expert Zone

1

Floor and ceil operations can be combined in a single traversal to find both values simultaneously, saving time.

2

In threaded BSTs, floor and ceil can be found even faster by using threads to move to in-order predecessor or successor without recursion or stack.

3

Augmenting BST nodes with subtree min/max values can help prune search paths early, optimizing floor and ceil queries in large trees.

When NOT to use

If the dataset is static and sorted, using a simple sorted array with binary search is often faster and simpler than BST floor and ceil. For very large dynamic datasets, balanced trees like AVL or Red-Black trees are preferred over plain BSTs to guarantee performance.

Production Patterns

Floor and ceil are used in database indexing to find range boundaries, in scheduling systems to find closest available time slots, and in autocomplete features to find nearest matches. Implementations often cache recent queries or use balanced trees to maintain speed.

Connections

Binary Search

Floor and ceil in BST build on the binary search principle of dividing search space by comparison.

Understanding binary search helps grasp how floor and ceil skip large parts of the tree, making search efficient.

Range Queries in Segment Trees

Floor and ceil help define boundaries for range queries, which segment trees use to answer range-based questions efficiently.

Knowing floor and ceil clarifies how to find query limits before applying segment tree operations.

Decision Making in Economics

Floor and ceil concepts relate to choosing closest acceptable options under constraints, similar to price floors and ceilings in markets.

Recognizing this connection shows how computer science concepts model real-world decision boundaries.

Common Pitfalls

#1 Returning the target value without checking if it exists in the BST.

Wrong approach:

int floor(Node* root, int target) {
return target; // wrong: assumes target exists
}

Correct approach:

int floor(Node* root, int target) {
int floor_val = -1;
while (root) {
if (root->data == target) return root->data;
else if (root->data < target) {
floor_val = root->data;
root = root->right;
} else {
root = root->left;
}
}
return floor_val;
}

Root cause:

Assuming the target is always present leads to incorrect results when it is missing.

#2 Not updating the candidate floor or ceil during traversal.

Wrong approach:

int ceil(Node* root, int target) {
while (root) {
if (root->data < target) root = root->right;
else root = root->left;
}
return -1; // never records candidate
}

Correct approach:

int ceil(Node* root, int target) {
int ceil_val = -1;
while (root) {
if (root->data == target) return root->data;
else if (root->data > target) {
ceil_val = root->data;
root = root->left;
} else {
root = root->right;
}
}
return ceil_val;
}

Root cause:

Forgetting to track the best candidate causes missing correct floor or ceil values.

#3 Confusing when to move left or right during floor or ceil search.

Wrong approach:

int floor(Node* root, int target) {
while (root) {
if (root->data > target) root = root->right; // wrong direction
else root = root->left;
}
return -1;
}

Correct approach:

int floor(Node* root, int target) {
int floor_val = -1;
while (root) {
if (root->data == target) return root->data;
else if (root->data < target) {
floor_val = root->data;
root = root->right;
} else {
root = root->left;
}
}
return floor_val;
}

Root cause:

Misunderstanding BST property leads to wrong traversal direction and incorrect results.

Key Takeaways

Floor and ceil in BST find the closest smaller-or-equal and larger-or-equal values efficiently by leveraging the BST's sorted structure.

These operations update candidate values during traversal and choose direction based on comparisons to avoid full tree scans.

Handling edge cases like empty trees or no suitable floor/ceil is essential for robust implementations.

Balanced BSTs improve worst-case performance of floor and ceil searches to logarithmic time.

Misunderstandings about traversal direction or candidate updates cause common bugs, so careful logic is critical.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The smallest value in the BST greater than or equal to the given value

B. The root value of the BST

C. The greatest value in the BST less than or equal to the given value

D. The smallest value in the BST less than the given value

Solution

1. Step 1: Understand the definition of floor in BST

   The floor of a value is the greatest value in the BST that is less than or equal to the given value.

2. Step 2: Compare with options

   The greatest value in the BST less than or equal to the given value matches this definition exactly, while others describe different concepts.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option C

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 C function signature to find the ceil of a value in a BST node structure named Node?

easy

A. int ceilBST(Node* root, int key);

B. void ceilBST(Node root, int key);

C. Node* ceilBST(int key, Node* root);

D. int ceilBST(int key);

Solution

1. Step 1: Analyze function parameters and return type

   The function should take a pointer to the root node and the key to find ceil for, returning an integer value.

2. Step 2: Match with options

   int ceilBST(Node* root, int key); matches this: it takes Node* root and int key, returns int. Others have wrong parameter order, types, or return type.

3. Final Answer:

   int ceilBST(Node* root, int key); -> Option A

4. Quick Check:

   Correct signature: pointer root, key, returns int [OK]

Hint: Function takes root pointer and key, returns int [OK]

Common Mistakes:

• Passing root by value instead of pointer
• Wrong parameter order
• Returning Node* instead of int

3. Given the BST below and the key = 14, what is the output of the ceil function?

        10
       /  \
      5    15
          /  \
         12   20

medium

A. -1

B. 15

C. 12

D. 20

Solution

1. Step 1: Understand ceil definition and traverse BST

   Ceil is smallest value ≥ key. Starting at root 10, since 14 > 10, move right to 15. 15 ≥ 14, so candidate ceil is 15. Check left subtree of 15 (12) which is < 14, so ignore.

2. Step 2: Confirm smallest candidate

   15 is the smallest node ≥ 14. 20 is larger but not smaller than 15, so 15 is ceil.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Ceil(14) = 15 [OK]

Hint: Ceil is smallest node ≥ key, check right subtree carefully [OK]

Common Mistakes:

• Choosing 20 instead of 15
• Choosing 12 which is < 14
• Returning -1 when ceil exists

4. Consider the following buggy C code snippet to find floor in BST. What is the main error?

int floorBST(Node* root, int key) {
    if (!root) return -1;
    if (root->data == key) return root->data;
    if (root->data > key) return floorBST(root->left, key);
    int floorValue = floorBST(root->right, key);
    if (floorValue <= key && floorValue != -1) return floorValue;
    else return root->data;
}

medium

A. It returns root->data even if floorValue is -1

B. It does not check for NULL root

C. It returns -1 when key is found

D. It incorrectly searches left subtree when root->data < key

Solution

1. Step 1: Analyze return conditions

   If floorValue is -1 (meaning no floor found in right subtree), the code returns root->data without checking if root->data ≤ key, which can be incorrect.

2. Step 2: Identify the error

   The code should check if root->data ≤ key before returning it; otherwise, it may return a value greater than key, violating floor definition.

3. Final Answer:

   It returns root->data even if floorValue is -1 -> Option A

4. Quick Check:

   Missing check before returning root->data causes wrong floor [OK]

Hint: Check root->data ≤ key before returning it [OK]

Common Mistakes:

• Ignoring floorValue == -1 case
• Returning wrong subtree
• Not handling NULL root

5. You have a BST with nodes: 8, 4, 12, 2, 6, 10, 14. You want to find the floor and ceil of 5. Which pair is correct?

hard

A. Floor = 5, Ceil = 5

B. Floor = 6, Ceil = 4

C. Floor = 2, Ceil = 8

D. Floor = 4, Ceil = 6

Solution

1. Step 1: Identify floor of 5 in BST

   Floor is greatest value ≤ 5. Nodes ≤ 5 are 2 and 4. Greatest is 4.

2. Step 2: Identify ceil of 5 in BST

   Ceil is smallest value ≥ 5. Nodes ≥ 5 are 6, 8, 10, 12, 14. Smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option D

4. Quick Check:

   Floor(5)=4, Ceil(5)=6 [OK]

Hint: Floor ≤ key, ceil ≥ key; pick closest values [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals key if not present
• Choosing wrong closest values