Floor and Ceil in BST in DSA C - Build from Scratch

Floor and Ceil in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores integer values. You want to find two special values for a given number:Floor: The greatest value in the BST less than or equal to the given number.Ceil: The smallest value in the BST greater than or equal to the given number.This is useful in many real-world cases like searching for closest available prices or dates.

🎯 Goal: Build a program in C that creates a BST with given values, sets a target number, and finds the floor and ceil values for that number in the BST.

📋 What You'll Learn

Create a BST by inserting these exact values in order: 20, 10, 30, 5, 15, 25, 35

Create an integer variable called target and set it to 16

Write two functions floorBST and ceilBST that find floor and ceil values for target in the BST

Print the floor and ceil values exactly as: Floor: X and Ceil: Y

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in a BST is useful in applications like price matching, scheduling, and range queries where you want the closest available value below or above a target.

💼 Career

Understanding BST operations and how to find floor and ceil values is important for software engineers working with search algorithms, databases, and real-time systems.

1

Create the BST structure and insert nodes

Define a struct called Node with int data, Node *left, and Node *right. Then write a function insertNode that inserts a new integer into the BST. Finally, create a BST by inserting these values in order: 20, 10, 30, 5, 15, 25, 35. Store the root in a variable called root.

DSA C

# Define struct Node
// Write insertNode function
// Insert values 20, 10, 30, 5, 15, 25, 35 into BST
// Store root in variable root

Hint

Start by defining the Node structure with data and pointers to left and right children. Then write a recursive insert function that places new values in the correct position. Insert the given values one by one into the BST.

2

Set the target value to find floor and ceil

Create an integer variable called target and set it to 16 inside the main function after building the BST.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (data data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

int main() {
    Node* root = NULL;
    root = insertNode(root, 20);
    root = insertNode(root, 10);
    root = insertNode(root, 30);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 25);
    root = insertNode(root, 35);

    // Create target variable and set to 16
    // Your code here

    return 0;
}

Hint

Inside the main function, declare an integer variable named target and assign it the value 16.

3

Write functions to find floor and ceil in BST

Write two functions: int floorBST(Node* root, int target) and int ceilBST(Node* root, int target). Each function should return the floor or ceil value for target in the BST. Use the BST property to traverse efficiently. Return -1 if floor or ceil does not exist.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (data data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

int floorBST(Node* root, int target) {
    // Your code here
}

int ceilBST(Node* root, int target) {
    // Your code here
}

int main() {
    Node* root = NULL;
    root = insertNode(root, 20);
    root = insertNode(root, 10);
    root = insertNode(root, 30);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 25);
    root = insertNode(root, 35);

    int target = 16;

    // Your code here

    return 0;
}

Hint

Use a loop to traverse the BST. For floor, move left if current node is greater than target, else update floor and move right. For ceil, move right if current node is less than target, else update ceil and move left. Return -1 if no floor or ceil found.

4

Print the floor and ceil values

Use printf to print the floor and ceil values for target exactly as: Floor: X and Ceil: Y, where X and Y are the results from floorBST(root, target) and ceilBST(root, target).

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (data data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

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

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

int main() {
    Node* root = NULL;
    root = insertNode(root, 20);
    root = insertNode(root, 10);
    root = insertNode(root, 30);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 25);
    root = insertNode(root, 35);

    int target = 16;

    // Print floor and ceil values
    // Your code here

    return 0;
}

Hint

Call floorBST(root, target) and ceilBST(root, target) and store their results. Then print them using printf with the exact format Floor: X and Ceil: Y.

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