Floor in BST

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.

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)