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 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 closest matches in sorted data stored in a tree.

Why it matters

Without floor and ceil operations, finding closest smaller or larger values in sorted data would be slow and inefficient. They allow fast queries in many applications like searching ranges, nearest neighbors, or decision making. This makes BSTs more powerful and practical for real-world problems involving ordered data.

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 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 to a certain height, floor is the tallest book not taller than your target, and ceil is the shortest book not shorter than your target.

          [Root]
          /    \
      [Left]  [Right]

Floor search:
- If node value == target, floor = node value
- If node value > target, go left
- If node value < target, floor = node value or better in right subtree

Ceil search:
- If node value == target, ceil = node value
- If node value < target, go right
- If node value > target, ceil = node value or better in left subtree

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its sorted property works.

A Binary Search Tree is a tree where each node has up to two children. For every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property allows fast searching by comparing the target with the current node and deciding to go left or right.

Result

You can find if a value exists in the BST by moving left or right based on comparisons, skipping half the tree each step.

Understanding BST's sorted structure is key to efficiently finding values and their closest neighbors.

2

Foundation

Basic Search Operation in BST

Concept: How to search for a value in BST using comparisons.

Start at the root. If the target equals the node's value, found it. If target is smaller, go to left child. If larger, go to right child. Repeat until found or reach null (not found).

Result

Search either finds the target or confirms it is not in the tree.

This step-by-step comparison is the foundation for floor and ceil searches.

3

Intermediate

Finding Floor Value in BST

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

Concept: Floor is the greatest value less than or equal to the target. We use BST properties to find it efficiently.

Start at root. If node value equals target, floor is node value. If node value > target, floor must be in left subtree, so go left. If node value < target, node value is a candidate floor, but maybe a better floor exists in right subtree, so go right and update floor candidate.

Result

We find the closest smaller or equal value to the target in O(h) time, where h is tree height.

Knowing when to update the floor candidate and when to move left or right is crucial for correctness and efficiency.

4

Intermediate

Finding Ceil Value in BST

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

Concept: Ceil is the smallest value greater than or equal to the target. We use BST properties similarly but reversed.

Start at root. If node value equals target, ceil is node value. If node value < target, ceil must be in right subtree, so go right. If node value > target, node value is a candidate ceil, but maybe a better ceil exists in left subtree, so go left and update ceil candidate.

Result

We find the closest larger or equal value to the target in O(h) time.

The mirror logic of floor search helps us find ceil efficiently by carefully choosing when to update candidates.

5

Intermediate

Implementing Floor and Ceil in C#

Concept: Translate the floor and ceil logic into runnable C# code using BST node structure.

Define a BST node class with int value and left/right children. Implement Floor and Ceil methods that traverse the tree as per the logic above, updating candidate values and moving left or right accordingly. Return the candidate or null if none found.

Result

You get working methods that return floor and ceil values or null if no suitable value exists.

Implementing the logic concretely solidifies understanding and prepares for real use.

6

Advanced

Handling Edge Cases and Null Results

🤔Before reading on: If the target is smaller than all BST values, what should floor return? Commit to your answer.

Concept: Floor or ceil may not exist if target is outside BST value range. We must handle these cases gracefully.

If target is smaller than all nodes, floor does not exist (return null). If target is larger than all nodes, ceil does not exist (return null). Code must check candidate variables and return null if no candidate was found during traversal.

Result

Floor and ceil methods correctly return null when no valid floor or ceil exists.

Recognizing and coding for boundary conditions prevents bugs and unexpected results.

7

Expert

Optimizing Floor and Ceil for Balanced BSTs

🤔Before reading on: Does balancing the BST affect the time complexity of floor and ceil operations? Commit to your answer.

Concept: Balanced BSTs keep height low, improving worst-case time for floor and ceil from O(n) to O(log n).

In unbalanced BSTs, worst-case height can be linear, making floor and ceil slow. Balanced BSTs like AVL or Red-Black trees maintain height as O(log n). Using these trees ensures floor and ceil run efficiently even on large datasets. Implementations can be adapted to these trees without changing logic.

Result

Floor and ceil operations run in logarithmic time on balanced BSTs, making them scalable.

Understanding the impact of tree balance on operation speed is key for production-ready systems.

Under the Hood

Floor and ceil work by traversing the BST from root, comparing the target with node values. At each node, the algorithm decides to go left or right based on BST ordering. It keeps track of the best candidate found so far. This selective traversal avoids visiting unnecessary nodes, leveraging BST's sorted structure to achieve efficient search.

Why designed this way?

BSTs were designed to allow fast search by ordering nodes. Floor and ceil extend this by using the same ordering to find closest values without scanning the entire tree. Alternatives like linear search are slower. This design balances simplicity and efficiency.

Start
  │
  ▼
[Compare target with node]
  ├─ If equal -> return node value
  ├─ If target < node value -> go left subtree (possible better floor/ceil)
  └─ If target > node value -> go right subtree (update candidate floor/ceil)
Repeat until leaf or candidate found

Myth Busters - 4 Common Misconceptions

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

Common Belief: Floor always returns the smallest value in the BST if the target is smaller than all values.

Reality: Floor returns null if no value less than or equal to the target exists, so it returns nothing in this case.

Why it matters: Assuming floor returns a value when none qualifies leads to incorrect results and bugs in applications relying on floor.

Quick: Does ceil always return a value even if the target is larger than all BST values? Commit to yes or no.

Common Belief: Ceil always returns a value, even if the target is larger than all BST values.

Reality: Ceil returns null if no value greater than or equal to the target exists, so it returns nothing if target is too large.

Why it matters: Misunderstanding this causes errors when ceil is assumed to always produce a result.

Quick: Is it correct to always go left when node value is greater than target for both floor and ceil? Commit to yes or no.

Common Belief: For both floor and ceil, if node value is greater than target, always go left subtree.

Reality: This is true for ceil but not for floor. For ceil, if node value > target, node is candidate and we go left to find smaller candidate. For floor, if node value > target, we must go left without updating candidate.

Why it matters: Confusing floor and ceil traversal logic leads to wrong answers and wasted search.

Quick: Can floor and ceil be found by a single traversal? Commit to yes or no.

Common Belief: Floor and ceil must be found by separate traversals of the BST.

Reality: They can be found in a single traversal by tracking both candidates simultaneously.

Why it matters: Knowing this can optimize performance in systems needing both values at once.

Expert Zone

1

Floor and ceil candidates must be updated only when moving in the correct subtree direction to avoid missing better matches.

2

In threaded or augmented BSTs, floor and ceil can be found even faster by using parent pointers or extra data.

3

When duplicates exist in BST, floor and ceil definitions and implementations must handle equality carefully to avoid off-by-one errors.

When NOT to use

If the data is not stored in a BST or is unsorted, floor and ceil operations are inefficient or impossible. Alternatives include balanced trees, sorted arrays with binary search, or specialized data structures like segment trees or interval trees for range queries.

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 performance.

Connections

Binary Search

Floor and ceil in BST use the same divide-and-conquer comparison logic as binary search on arrays.

Understanding binary search helps grasp how BST traversal narrows down candidates efficiently.

Predecessor and Successor in BST

Floor corresponds to predecessor or equal, and ceil corresponds to successor or equal in BST terminology.

Knowing predecessor and successor concepts clarifies floor and ceil as special cases including equality.

Decision Boundaries in Machine Learning

Floor and ceil find closest thresholds, similar to how decision boundaries separate classes by closest values.

Recognizing floor and ceil as boundary finders connects data structures to classification problems.

Common Pitfalls

#1 Returning the current node value as floor without checking right subtree for a better candidate.

Wrong approach:

if (node.Value < target) return node.Value; else go left;

Correct approach:

if (node.Value < target) { candidate = node.Value; go right; } else go left;

Root cause:

Misunderstanding that a better floor might exist deeper in the right subtree.

#2 Assuming floor or ceil always exist and returning a default value without null checks.

Wrong approach:

return candidate.Value; // without checking if candidate is null

Correct approach:

return candidate != null ? candidate.Value : (int?)null;

Root cause:

Ignoring edge cases where no floor or ceil is found.

#3 Using the same traversal logic for floor and ceil without adjusting direction and candidate updates.

Wrong approach:

For both floor and ceil, go left if node value > target, else right, updating candidate the same way.

Correct approach:

For floor, update candidate when node value < target and go right; for ceil, update candidate when node value > target and go left.

Root cause:

Confusing the opposite conditions for floor and ceil searches.

Key Takeaways

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

They work by traversing the tree, updating candidate values, and choosing left or right subtrees based on comparisons.

Handling edge cases where floor or ceil do not exist is essential to avoid errors.

Balanced BSTs improve floor and ceil operation speed from linear to logarithmic time.

Understanding floor and ceil deepens knowledge of BST traversal and prepares for advanced tree operations.

Practice

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

easy

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

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

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

D. The root node value of the BST

Solution

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

   The floor of a value in BST is the largest value 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 ceil or unrelated 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 always smaller than the value
• Assuming floor is the root value

2. Which of the following is the correct C# method signature to find the ceil value in a BST node class?

easy

A. public int FindCeil(int key)

B. int FindCeil(int key, Node root)

C. public void FindCeil(Node root, int key)

D. public int FindCeil(Node root, int key)

Solution

1. Step 1: Understand method signature requirements

   The method should be public, return an int (the ceil value), and accept the BST root node and the key to find ceil for.

2. Step 2: Match with options

   public int FindCeil(Node root, int key) matches this: public int FindCeil(Node root, int key). int FindCeil(int key, Node root) has wrong parameter order, C returns void, D misses root parameter.

3. Final Answer:

   public int FindCeil(Node root, int key) -> Option D

4. Quick Check:

   Correct signature returns int and takes root, key [OK]

Hint: Method returns int, takes root and key in order [OK]

Common Mistakes:

• Wrong parameter order
• Using void return type
• Missing root parameter

3. Given the BST below and key = 14, what is the ceil value?

        10
       /  \
      5    15
          /  \
         12   20

medium

A. 12

B. 15

C. 20

D. 10

Solution

1. Step 1: Understand ceil definition and BST structure

   Ceil is the smallest value greater than or equal to 14. The BST nodes are 10, 5, 15, 12, 20.

2. Step 2: Find values ≥ 14 and pick smallest

   Values ≥ 14 are 15 and 20. The smallest among these is 15.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Ceil(14) = 15 [OK]

Hint: Ceil is smallest ≥ key in BST [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is greater but not smallest
• Confusing ceil with floor

4. Consider this buggy C# code snippet to find floor in BST:

int FindFloor(Node root, int key) {
  if (root == null) return -1;
  if (root.val == key) return root.val;
  if (root.val > key) return FindFloor(root.left, key);
  int floorVal = FindFloor(root.right, key);
  return (floorVal <= key && floorVal != -1) ? floorVal : root.val;
}

What is the main issue causing incorrect floor results?

medium

A. The condition to check floorVal is incorrect and may return wrong value

B. The base case returns -1 which may be confused with valid floor

C. The function does not handle the case when root.val < key

D. The function does not recurse on left subtree when root.val < key

Solution

1. Step 1: Analyze the floorVal condition

   The code checks if floorVal ≤ key and floorVal != -1 to decide return value. But floorVal could be less than root.val and still valid floor.

2. Step 2: Identify the incorrect logic

   The condition should check if floorVal is greater than root.val to pick the better floor, but it doesn't, causing wrong floor return.

3. Final Answer:

   The condition to check floorVal is incorrect and may return wrong value -> Option A

4. Quick Check:

   Incorrect floorVal check causes wrong floor [OK]

Hint: Check floorVal against root.val, not just key [OK]

Common Mistakes:

• Ignoring comparison with root.val
• Returning -1 as valid floor
• Not handling null root properly

5. You want to find both floor and ceil of a key in a BST efficiently. Which approach is best to implement in C#?

hard

A. Traverse the BST once, updating floor and ceil candidates during traversal

B. Perform two separate traversals: one for floor and one for ceil

C. Convert BST to sorted array, then use binary search twice

D. Use BFS traversal to find floor and ceil simultaneously

Solution

1. Step 1: Consider efficiency of approaches

   Two separate traversals or converting to array add extra time or space. BFS is not suitable for ordered search.

2. Step 2: Single traversal updating floor and ceil

   During one BST traversal, compare node values with key to update floor (largest ≤ key) and ceil (smallest ≥ key) efficiently.

3. Final Answer:

   Traverse the BST once, updating floor and ceil candidates during traversal -> Option A

4. Quick Check:

   Single traversal updates floor and ceil efficiently [OK]

Hint: Update floor and ceil in one BST traversal [OK]

Common Mistakes:

• Doing two separate traversals wasting time
• Using BFS which ignores BST order
• Converting BST to array wastes space