Skip to main content

Floor in BST

Problem​

You are given a BST (Binary search tree) with’ N’ number of nodes and a value ‘X’. Your task is to find the greatest value node of the BST which is smaller than or equal to ‘X’. Note :‘X’ is not smaller than the smallest node of BST .

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
int floorInBST(TreeNode<int>* root, int X) {
    if (!root) return -1;
    if (root->val <= X) {
        return max(root->val, floorInBST(root->right, X));
    } else
        return floorInBST(root->left, X);
}