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.