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 that creates a BST with given values, sets a target number, and finds the floor and ceil values in the BST for that target.

📋 What You'll Learn

Create a BST by inserting nodes with exact values: 8, 4, 12, 2, 6, 10, 14

Create an integer variable called target and set it to 5

Write two functions findFloor and findCeil that find floor and ceil values in the BST for target

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

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in sorted data is common in price matching, scheduling, and recommendation systems.

💼 Career

Understanding BST operations and search algorithms is essential for software engineering roles involving data structures and algorithm optimization.

1

Create the BST structure and insert nodes

Create a struct called Node with int data, Node* left, and Node* right. Then write a function insertNode that takes Node* root and int val and inserts a new node with val into the BST. Finally, create a Node* root and insert these values in order: 8, 4, 12, 2, 6, 10, 14.

DSA C++

// Define Node struct and insertNode function
// Create root and insert nodes 8, 4, 12, 2, 6, 10, 14
// Your code here

Hint

Start by defining the Node structure with data and pointers to left and right children. Then write a recursive insert function that places values correctly in the BST. Finally, create the root pointer and insert the given values one by one.

2

Set the target value to find floor and ceil

Create an integer variable called target and set it to 5 inside main() after the BST is created.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insertNode(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val data) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 8);
    root = insertNode(root, 4);
    root = insertNode(root, 12);
    root = insertNode(root, 2);
    root = insertNode(root, 6);
    root = insertNode(root, 10);
    root = insertNode(root, 14);
    
    // Create target variable and set to 5
    // Your code here
    return 0;
}

Hint

Just add a line inside main() to create an integer variable named target and assign it the value 5.

3

Write functions to find floor and ceil in BST

Write two functions: int findFloor(Node* root, int target) and int findCeil(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 no floor or ceil exists.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insertNode(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val data) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 8);
    root = insertNode(root, 4);
    root = insertNode(root, 12);
    root = insertNode(root, 2);
    root = insertNode(root, 6);
    root = insertNode(root, 10);
    root = insertNode(root, 14);
    
    int target = 5;
    
    // Write findFloor and findCeil functions below
    // 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 suitable value found.

4

Print the floor and ceil values

In main(), after calling findFloor and findCeil, print the results exactly as: Floor: X and Ceil: Y where X and Y are the floor and ceil values found.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insertNode(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val data) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

int findFloor(Node* root, int target) {
    int floor = -1;
    while (root != nullptr) {
        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 findCeil(Node* root, int target) {
    int ceil = -1;
    while (root != nullptr) {
        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 = nullptr;
    root = insertNode(root, 8);
    root = insertNode(root, 4);
    root = insertNode(root, 12);
    root = insertNode(root, 2);
    root = insertNode(root, 6);
    root = insertNode(root, 10);
    root = insertNode(root, 14);
    
    int target = 5;
    
    int floorVal = findFloor(root, target);
    int ceilVal = findCeil(root, target);
    
    // Print floor and ceil values
    // Your code here
    return 0;
}

Hint

Use cout to print the floor and ceil values with the exact format: Floor: X and Ceil: Y.