DSA

Floor in BST

BST. Space O(1).

August 8, 2026
PatternBST Property
Solve on GeeksforGeeks
Key insighttry it first, then reveal

Exploit the BST property to navigate directly toward the floor value.

Practice Link

You are given a BST(Binary Search Tree) with n number of nodes and value x. your task is to find the greatest value node of the BST which is smaller than or equal to x. Note: when x is smaller than the smallest node of BST then returns -1.

Approach#

Exploit the BST property to navigate directly toward the floor value. At each node, if the node's value is <= x it is a valid floor candidate (record it) and we move right to look for a closer (larger) candidate. If the node's value is > x, it cannot be the floor, so we move left. The last recorded candidate when traversal ends is the answer. This is analogous to binary search — we halve the search space at every step.

cpp
class Solution{

public:
    int floor(Node* root, int x) {
        int f = -1;
        while(root)
        {
            if(root->data <= x)
            {
                f = root->data;
                if(root->data ==x)
                    break;
                else
                    root=root->right;
            }else
                root=root->left;
        }
        return f;
    }
};

Time Complexity:

  • Average -> O(logn) (balanced)
  • Worst -> O(n) (skewed)

Space Complexity: O(1)