Floor and Ceil in BST in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the floor value in a BST.

DSA C

int floorBST(struct Node* root, int key) {
    int floor = -1;
    while (root != NULL) {
        if (root->data == key) {
            floor = root->data;
            break;
        } else if (root->data > key) {
            root = root->left;
        } else {
            floor = root->data;
            root = root->[1];
        }
    }
    return floor;
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to the left child when root->data < key, which misses possible larger floor values.

The floor is the greatest value less than or equal to the key. When root->data is less than key, we move to the right subtree to find a closer value.

2fill in blank

medium

Complete the code to find the ceil value in a BST.

DSA C

int ceilBST(struct Node* root, int key) {
    int ceil = -1;
    while (root != NULL) {
        if (root->data == key) {
            ceil = root->data;
            break;
        } else if (root->data < key) {
            root = root->right;
        } else {
            ceil = root->data;
            root = root->[1];
        }
    }
    return ceil;
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Croot

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to the right child when root->data > key, which misses possible smaller ceil values.

The ceil is the smallest value greater than or equal to the key. When root->data is greater than key, we move to the left subtree to find a closer value.

3fill in blank

hard

Fix the error in the code to correctly find the floor in BST.

DSA C

int floorBST(struct Node* root, int key) {
    int floor = -1;
    while (root != NULL) {
        if (root->data == key) {
            floor = root->data;
            break;
        } else if (root->data < key) {
            floor = root->data;
            root = root->[1];
        } else {
            root = root->left;
        }
    }
    return floor;
}

Drag options to blanks, or click blank then click option'

Aroot

Bleft

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to the left child instead of right child when root->data < key.

When root->data is less than key, we should move to the right child to find a closer floor value. The original code incorrectly moves to the left child.

4fill in blank

hard

Fill both blanks to complete the function that finds ceil in BST.

DSA C

int ceilBST(struct Node* root, int key) {
    int ceil = -1;
    while (root != NULL) {
        if (root->data == key) {
            ceil = root->data;
            break;
        } else if (root->data > key) {
            ceil = root->data;
            root = root->[1];
        } else {
            root = root->[2];
        }
    }
    return ceil;
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping left and right child traversal in conditions.

When root->data > key, move left to find smaller ceil candidates. When root->data < key, move right to find larger values.

5fill in blank

hard

Fill all three blanks to complete the function that finds floor and ceil in BST and returns them in an array.

DSA C

int* floorAndCeilBST(struct Node* root, int key) {
    static int result[2];
    result[0] = -1; // floor
    result[1] = -1; // ceil
    struct Node* current = root;
    while (current != NULL) {
        if (current->data == key) {
            result[0] = current->data;
            result[1] = current->data;
            break;
        } else if (current->data < key) {
            result[0] = current->data;
            current = current->[1];
        } else {
            result[1] = current->data;
            current = current->[2];
        }
    }
    return result;
}

// Usage example:
// int* res = floorAndCeilBST(root, 15);
// printf("Floor: %d, Ceil: %d\n", res[[3]], res[1]);

Drag options to blanks, or click blank then click option'

Aright

Bleft

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing left and right child traversal for floor and ceil.

Using wrong index to print floor value.

For floor, move right when current->data < key. For ceil, move left when current->data > key. The floor is stored at index 0 in the result array.

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