Floor and Ceil in BST in DSA C++ - Time & Space Complexity

Time Complexity: Floor and Ceil in BST

O(h)

Understanding Time Complexity

We want to know how long it takes to find the floor or ceil of a value in a Binary Search Tree (BST).

Specifically, how the time grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int floorInBST(Node* root, int key) {
    int floorVal = -1;
    while (root) {
        if (root->data == key) return root->data;
        if (root->data > key) root = root->left;
        else {
            floorVal = root->data;
            root = root->right;
        }
    }
    return floorVal;
}
    

This code finds the floor value (largest value <= key) in a BST by traversing nodes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing down the BST nodes using a while loop.
• How many times: At most once per tree level, moving left or right child each step.

How Execution Grows With Input

As the BST grows, the number of steps depends on the tree height.

Input Size (n)	Approx. Operations
10	Up to 4 steps (if balanced)
100	Up to 7 steps (if balanced)
1000	Up to 10 steps (if balanced)

Pattern observation: The steps grow slowly, roughly proportional to the tree height, not total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the BST, which is the number of levels from root to leaf.

Common Mistake

[X] Wrong: "Finding floor or ceil always takes O(n) time because we might check every node."

[OK] Correct: The BST structure lets us skip large parts of the tree, so we only follow one path down, not all nodes.

Interview Connect

Understanding how BST properties help reduce search time is a key skill. It shows you can use data structure features to write efficient code.

Self-Check

"What if the BST is not balanced and becomes a linked list? How would the time complexity change?"