Floor and Ceil in BST in DSA C#

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 a bookshelf sorted by book height. Floor is the tallest book not taller than your target height; Ceil is the shortest book not shorter than your target height.

       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 floor and ceil values for 5 in the BST

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

8[5]<-- target
BST unchanged

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

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

4[5]<-- target, ceil=8
BST unchanged

Why: 5 is less than 8, so ceil might be 8 or smaller; floor must be in left subtree

Step 3: Compare 5 with 4; 5 > 4, move to right child 6; update floor candidate to 4

6[5]<-- target, floor=4, ceil=8
BST unchanged

Why: 5 is greater than 4, so floor might be 4 or bigger; ceil might be 6 or smaller

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

null[5]<-- target, floor=4, ceil=6
BST unchanged

Why: No left child of 6, so stop search; floor and ceil candidates finalized

Result:

Floor: 4
Ceil: 6

Annotated Code

DSA C#

using System;

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class BSTFloorCeil {
    public static int? Floor(Node root, int target) {
        int? floor = null;
        Node curr = root;
        while (curr != null) {
            if (curr.val == target) {
                return curr.val; // exact match is floor
            } else if (curr.val > target) {
                curr = curr.left; // go left to find smaller or equal
            } else {
                floor = curr.val; // update floor candidate
                curr = curr.right; // try to find closer floor
            }
        }
        return floor;
    }

    public static int? Ceil(Node root, int target) {
        int? ceil = null;
        Node curr = root;
        while (curr != null) {
            if (curr.val == target) {
                return curr.val; // exact match is ceil
            } else if (curr.val < target) {
                curr = curr.right; // go right to find bigger or equal
            } else {
                ceil = curr.val; // update ceil candidate
                curr = curr.left; // try to find closer ceil
            }
        }
        return ceil;
    }

    static void Main() {
        Node root = new Node(8);
        root.left = new Node(4);
        root.right = new Node(12);
        root.left.left = new Node(2);
        root.left.right = new Node(6);
        root.right.left = new Node(10);
        root.right.right = new Node(14);

        int target = 5;
        int? floor = Floor(root, target);
        int? ceil = Ceil(root, target);

        Console.WriteLine($"Floor: {(floor.HasValue ? floor.ToString() : "null")}");
        Console.WriteLine($"Ceil: {(ceil.HasValue ? ceil.ToString() : "null")}");
    }
}

while (curr != null) {

loop to traverse BST nodes until no more candidates

if (curr.val == target) { return curr.val; }

exact match found, return immediately

else if (curr.val > target) { curr = curr.left; }

move left to find smaller or equal values for floor

else { floor = curr.val; curr = curr.right; }

update floor candidate and move right to find closer floor

else if (curr.val < target) { curr = curr.right; }

move right to find bigger or equal values for ceil

else { ceil = curr.val; curr = curr.left; }

update ceil candidate and move left to find closer ceil

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) where h is the height of the BST because we traverse down one path from root to leaf

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 uses BST property to reduce search to O(h)

Edge Cases

target smaller than all nodes

floor is null, ceil is smallest node

DSA C#

return floor;

target larger than all nodes

floor is largest node, ceil is null

DSA C#

return ceil;

target exactly matches a node

floor and ceil both equal target

DSA C#

if (curr.val == target) { return curr.val; }

When to Use This Pattern

When asked to find closest smaller or larger values in a BST, use floor and ceil search by moving left or right based on comparisons.

Common Mistakes

Mistake: Not updating floor or ceil candidates before moving pointers
Fix: Always update floor when moving right and ceil when moving left before pointer moves

Mistake: Returning null immediately when no exact match found
Fix: Keep track of best floor or ceil candidate while traversing

Summary

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

Use when you need nearest bounds for a value in a sorted tree structure.

The key is to move left or right and update candidates based on comparisons to target.

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