Floor and Ceil in BST in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floor and Ceil Search in BST

What is the output of the following code that finds floor and ceil of a key in a BST?

DSA C++

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

int floorBST(Node* root, int key) {
    int floor = -1;
    while (root) {
        if (root->val == key) return root->val;
        if (root->val > key) root = root->left;
        else {
            floor = root->val;
            root = root->right;
        }
    }
    return floor;
}

int ceilBST(Node* root, int key) {
    int ceil = -1;
    while (root) {
        if (root->val == key) return root->val;
        if (root->val < key) root = root->right;
        else {
            ceil = root->val;
            root = root->left;
        }
    }
    return ceil;
}

int 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 key = 5;
    int f = floorBST(root, key);
    int c = ceilBST(root, key);
    std::cout << "Floor: " << f << ", Ceil: " << c << std::endl;
    return 0;
}

A Floor: -1, Ceil: -1

B Floor: 6, Ceil: 4

C Floor: 5, Ceil: 5

D Floor: 4, Ceil: 6

💡 Hint

Remember floor is the greatest value less than or equal to key, ceil is the smallest value greater than or equal to key.

The floor of 5 in the BST is 4 because 4 is the greatest value less than 5. The ceil of 5 is 6 because 6 is the smallest value greater than 5.

🧠 Conceptual

intermediate

Understanding Floor and Ceil in BST

In a Binary Search Tree (BST), which of the following statements about floor and ceil of a key is always true?

A Floor and Ceil are always equal to the key if the key exists in BST; otherwise both are -1.

B Floor is the smallest value in BST greater than the key; Ceil is the largest value in BST less than the key.

C Floor is the largest value in BST less than or equal to the key; Ceil is the smallest value in BST greater than or equal to the key.

D Floor is always the root value; Ceil is always the leaf value.

💡 Hint

Think about the definitions of floor and ceil in number sets.

Floor is the greatest value less than or equal to the key, and ceil is the smallest value greater than or equal to the key in the BST.

🔧 Debug

advanced

Identify the Bug in Floor Function

What error or wrong output will the following floor function produce when searching for key=1 in the BST below? BST structure: 5 / \ 3 7 / \ 2 4 Code: int floorBST(Node* root, int key) { int floor = -1; while (root) { if (root->val == key) return root->val; if (root->val < key) { floor = root->val; root = root->right; } else { root = root->left; } } return floor; }

A Returns 2 (incorrect, 2 is greater than 1)

B Returns -1 (correct floor since 1 is less than all nodes)

C Infinite loop due to wrong traversal

D Returns 3 (incorrect floor)

💡 Hint

Check the condition that updates floor and the direction of traversal.

The condition to update floor is incorrect. It updates floor when root->val < key, but for key=1, it incorrectly moves right and sets floor to 2, which is greater than 1. The correct floor should be -1.

❓ Predict Output

advanced

Output of Floor and Ceil for Key Not in BST

Given the BST below and key=13, what is the output of floor and ceil functions? BST: 10 / \ 5 15 / \ \ 3 7 18 Code snippet: int floorBST(Node* root, int key) { int floor = -1; while (root) { if (root->val == key) return root->val; if (root->val > key) root = root->left; else { floor = root->val; root = root->right; } } return floor; } int ceilBST(Node* root, int key) { int ceil = -1; while (root) { if (root->val == key) return root->val; if (root->val < key) root = root->right; else { ceil = root->val; root = root->left; } } return ceil; } int main() { // BST construction omitted for brevity int key = 13; int f = floorBST(root, key); int c = ceilBST(root, key); std::cout << "Floor: " << f << ", Ceil: " << c << std::endl; return 0; }

A Floor: 7, Ceil: 10

B Floor: 10, Ceil: 15

C Floor: -1, Ceil: -1

D Floor: 15, Ceil: 18

💡 Hint

Floor is the greatest value less than or equal to 13; ceil is the smallest value greater than or equal to 13.

Floor is 10 because it is the greatest value less than 13. Ceil is 15 because it is the smallest value greater than 13.

🚀 Application

expert

Number of Nodes Between Floor and Ceil in BST

Given a BST and a key, how many nodes have values between the floor and ceil of the key (inclusive)? BST: 20 / \ 10 30 / \ / \ 5 15 25 35 Key = 17 What is the count of nodes with values between floor and ceil of 17 (inclusive)?

A 2

B 3

C 4

D 5

💡 Hint

Find floor and ceil first, then count nodes in that range.

Floor of 17 is 15, ceil is 20. Nodes with values 15 and 20 are counted. Since 17 is not in BST, nodes between 15 and 20 inclusive are 15 and 20 only. So count is 2 nodes.