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.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The greatest value in the BST less than or equal to the given value

B. The smallest value in the BST greater than or equal to the given value

C. The root value of the BST

D. The average of all values in the BST

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 other options

   The smallest value in the BST greater than or equal to the given value describes ceil, while the remaining options are unrelated to floor concept.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option A

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(int val);

B. void ceilBST(Node root, int val);

C. Node* ceilBST(int val, Node* root);

D. int ceilBST(Node* root, int val);

Solution

1. Step 1: Analyze function parameters and return type

   The function should take a pointer to the root node and the value to find ceil for, returning an integer ceil value.

2. Step 2: Check each option

   int ceilBST(Node* root, int val); matches correct signature: returns int, takes Node* and int. Others have wrong parameter order, missing pointers, or wrong return type.

3. Final Answer:

   int ceilBST(Node* root, int val); -> Option D

4. Quick Check:

   Correct signature returns int and takes Node* root [OK]

Hint: Function needs root pointer and value, returns int [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Wrong parameter order
• Incorrect return type

3. Given the BST below and the value 14, what is the ceil value?

        10
       /  \
      5    15
          /  \
         12   20

medium

A. 12

B. 15

C. 20

D. 10

Solution

1. Step 1: Locate value 14 in BST context

   14 is not in BST. We look for smallest value ≥ 14.

2. Step 2: Check nodes greater than or equal to 14

   Nodes ≥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 node ≥ target [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is larger but not smallest ≥14
• Confusing floor and ceil

4. Consider this buggy C++ code snippet to find floor in BST:

int floorBST(Node* root, int val) {
  if (!root) return -1;
  if (root->data == val) return root->data;
  if (root->data > val) return floorBST(root->left, val);
  int floorRight = floorBST(root->right, val);
  return (floorRight != -1 && floorRight <= val) ? floorRight : root->data;
}

What is the bug?

medium

A. It always returns root->data without recursion

B. It does not check for null root

C. It returns root->data when floorRight is greater than val, which is incorrect

D. It returns -1 for all values

Solution

1. Step 1: Understand the floor logic in code

   If root->data > val, search left subtree. Else search right subtree and compare.

2. Step 2: Identify incorrect return condition

   The code returns root->data if floorRight > val. However, since floorRight is never > val (returns -1 or ≤ val), this never triggers, causing it to return -1 (when right subtree has no floor ≤ val) instead of root->data.

3. Final Answer:

   It returns root->data when floorRight is greater than val, which is incorrect -> Option C

4. Quick Check:

   Floor must be ≤ val, code returns invalid value [OK]

Hint: Floor must never exceed val; check return conditions [OK]

Common Mistakes:

• Returning values greater than val as floor
• Missing null checks
• Ignoring recursion on left subtree

5. You have a BST with nodes: 8, 4, 12, 2, 6, 10, 14. You want to find both floor and ceil for value 7. Which pair is correct?

hard

A. Floor = 6, Ceil = 8

B. Floor = 8, Ceil = 6

C. Floor = 4, Ceil = 10

D. Floor = 7, Ceil = 7

Solution

1. Step 1: Identify floor of 7 in BST

   Floor is greatest value ≤7. Values ≤7 are 2,4,6. Greatest is 6.

2. Step 2: Identify ceil of 7 in BST

   Ceil is smallest value ≥7. Values ≥7 are 8,10,12,14. Smallest is 8.

3. Final Answer:

   Floor = 6, Ceil = 8 -> Option A

4. Quick Check:

   Floor ≤7 = 6, Ceil ≥7 = 8 [OK]

Hint: Floor ≤ val, Ceil ≥ val; pick closest values [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals the value if not present
• Choosing values not in BST