Floor and Ceil in BST in DSA C++

Mental Model

Floor is the greatest value less than or equal to target; ceil is the smallest value greater than or equal to target in a BST. We use BST properties to find them efficiently.

Analogy: Imagine looking for a seat number in a theater. Floor is the closest seat number before or exactly your number, ceil is the closest seat number after or exactly your number.

       8
      / \
     4   12
    / \   / \
   2   6 10  14

Dry Run Walkthrough

Input: BST: 8 -> 4 -> 12 -> 2 -> 6 -> 10 -> 14, find floor and ceil of 5

Goal: Find the floor and ceil values for 5 in the BST

Step 1: Start at root node 8, compare 5 with 8

Current node: 8

Why: We start from root to use BST property to decide direction

Step 2: Since 5 < 8, move to left child 4; update ceil candidate to 8

Current node: 4, ceil candidate: 8

Why: 5 is less than 8, so ceil could be 8 or smaller; floor must be <=5, so check left subtree

Step 3: Compare 5 with 4; since 5 > 4, update floor candidate to 4 and move to right child 6

Current node: 6, floor candidate: 4, ceil candidate: 8

Why: 5 is greater than 4, so floor could be 4 or higher; check right subtree for closer floor

Step 4: Compare 5 with 6; since 5 < 6, update ceil candidate to 6 and move to left child null

Current node: null, floor candidate: 4, ceil candidate: 6

Why: 5 is less than 6, so ceil could be 6 or smaller; left child is null, stop

Result:

Floor: 4
Ceil: 6

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

int findFloor(Node* root, int target) {
    int floor = -1;
    while (root) {
        if (root->val == target) {
            floor = root->val;
            break;
        } else if (root->val > target) {
            root = root->left; // move left to find smaller or equal
        } else {
            floor = root->val; // update floor candidate
            root = root->right; // move right to find closer floor
        }
    }
    return floor;
}

int findCeil(Node* root, int target) {
    int ceil = -1;
    while (root) {
        if (root->val == target) {
            ceil = root->val;
            break;
        } else if (root->val < target) {
            root = root->right; // move right to find larger or equal
        } else {
            ceil = root->val; // update ceil candidate
            root = root->left; // move left to find closer ceil
        }
    }
    return ceil;
}

int main() {
    Node* root = nullptr;
    int values[] = {8,4,12,2,6,10,14};
    for (int v : values) root = insert(root, v);

    int target = 5;
    int floor = findFloor(root, target);
    int ceil = findCeil(root, target);

    cout << "Floor: " << floor << "\n";
    cout << "Ceil: " << ceil << "\n";
    return 0;
}

while (root) {

loop to traverse BST nodes until null

if (root->val == target) { floor = root->val; break; }

exact match found, floor or ceil is target itself

else if (root->val > target) { root = root->left; }

move left to find smaller or equal values for floor

else { floor = root->val; root = root->right; }

update floor candidate and move right to find closer floor

else if (root->val < target) { root = root->right; }

move right to find larger or equal values for ceil

else { ceil = root->val; root = root->left; }

update ceil candidate and move left to find closer ceil

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) where h is the height of the BST because we traverse from root down to leaf at most once

Space: O(1) because we use only a few variables and no extra data structures

vs Alternative: Naive approach would traverse all nodes O(n) to find floor and ceil; BST property reduces it to O(h)

Edge Cases

target smaller than all nodes

floor remains -1 (no floor), ceil is smallest node

DSA C++

int floor = -1;

target larger than all nodes

ceil remains -1 (no ceil), floor is largest node

DSA C++

int ceil = -1;

target equals a node value

floor and ceil both equal target

DSA C++

if (root->val == target) { floor = root->val; break; }

When to Use This Pattern

When you need closest smaller or larger values in a sorted tree, use floor and ceil in BST pattern to leverage BST properties for efficient search.

Common Mistakes

Mistake: Not updating floor or ceil candidate before moving left or right
Fix: Always update floor or ceil candidate when moving towards potential answers before changing node

Summary

Finds the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a BST.

Use when you want quick nearest value queries in a sorted tree structure.

The key is to update candidates while traversing down the tree using BST ordering.

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