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 the BST.

Analogy: Imagine a ladder with numbered steps. Floor is the highest step you can stand on without going above your target number. Ceil is the lowest step you can step on without going below your target number.

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

Dry Run Walkthrough

Input: BST: 8->4->12->2->6->10->14, target=5

Goal: Find floor and ceil values for 5 in the BST

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

8[compare with 5] -> 4 -> 12 -> 2 -> 6 -> 10 -> 14

Why: We check root to decide which subtree to explore

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

4[compare with 5] -> 2 -> 6

Why: Target less than current node, so floor/ceil must be in left subtree or current node

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

6[compare with 5]

Why: 5 is greater than 4, so 4 could be floor, check right subtree for closer floor or ceil

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

null

Why: 5 less than 6, so 6 could be ceil, but left child is null, stop here

Result:

Floor = 4, Ceil = 6

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for BST
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert node in BST
Node* insert(Node* root, int data) {
    if (root == NULL) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

// Find floor in BST
int findFloor(Node* root, int target) {
    int floor = -1; // -1 means no floor found yet
    while (root != NULL) {
        if (root->data == target) {
            floor = root->data; // exact match is floor
            break;
        } else if (root->data > target) {
            root = root->left; // go left to find smaller or equal
        } else {
            floor = root->data; // update floor candidate
            root = root->right; // try to find closer floor
        }
    }
    return floor;
}

// Find ceil in BST
int findCeil(Node* root, int target) {
    int ceil = -1; // -1 means no ceil found yet
    while (root != NULL) {
        if (root->data == target) {
            ceil = root->data; // exact match is ceil
            break;
        } else if (root->data < target) {
            root = root->right; // go right to find bigger or equal
        } else {
            ceil = root->data; // update ceil candidate
            root = root->left; // try to find closer ceil
        }
    }
    return ceil;
}

// Driver code
int main() {
    Node* root = NULL;
    int values[] = {8,4,12,2,6,10,14};
    int n = sizeof(values)/sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }
    int target = 5;
    int floor = findFloor(root, target);
    int ceil = findCeil(root, target);
    printf("Floor = %d\nCeil = %d\n", floor, ceil);
    return 0;
}

while (root != NULL) {

loop to traverse BST nodes until leaf or exact match

if (root->data == target) { floor = root->data; break; }

exact match found, floor or ceil is target itself

else if (root->data > target) { root = root->left; }

target smaller, move left to find smaller or equal values

else { floor = root->data; root = root->right; }

target greater, update floor candidate and move right for closer floor

else if (root->data < target) { root = root->right; }

target greater, move right to find bigger or equal values

else { ceil = root->data; root = root->left; }

target smaller, update ceil candidate and move left for closer 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 leaf at most once

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

vs Alternative: Compared to traversing entire BST (O(n)), this approach uses BST property to find floor and ceil efficiently in O(h)

Edge Cases

target smaller than all nodes

floor returns -1 (no floor), ceil returns smallest node

DSA C

int floor = -1; // -1 means no floor found yet

target greater than all nodes

floor returns largest node, ceil returns -1 (no ceil)

DSA C

int ceil = -1; // -1 means no ceil found yet

target equals a node value

floor and ceil both return that node value

DSA C

if (root->data == target) { floor = root->data; break; }

When to Use This Pattern

When asked to find closest smaller or equal (floor) or closest bigger or equal (ceil) values in a BST, use the BST property to traverse left or right accordingly to find candidates efficiently.

Common Mistakes

Mistake: Not updating floor or ceil candidate before moving to child nodes
Fix: Always update floor or ceil candidate when current node value is a valid candidate before moving further

Summary

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

Use when you need quick range queries or nearest values in a sorted tree structure.

The key insight is to use BST ordering to move left or right and update candidates without full traversal.

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