worst case time complexity of finding the floor of a number in a BST-CodePudding

I know that the worst case time complexity of searching a node in a BST is O(logn) if the tree is balanced. But what about searching for a floor of a number t in a BST?

because in the above scenario, we are not just searching for an exact node, but a node that is close or the same as t but not greater than t. there are many criterias involved. So would it still be O(logn) worst case? (tree is balanced)

below is my code and I'm struggling to find the worst case time complexity for this:

struct Node {
    int data;
    Node *left, *right;
};

int floor(Node* root, int key)
{
    if (!root)
        return INT_MAX;
 
    /* If root->data is equal to key */
    if (root->data == key)
        return root->data;
 
    /* If root->data is greater than the key */
    if (root->data > key)
        return floor(root->left, key);
 
    /* Else, the floor may lie in right subtree
      or may be equal to the root*/
    int floorValue = floor(root->right, key);
    return (floorValue <= key) ? floorValue : root->data;
}

Thanks.

CodePudding user response：

The time complexity is still O(log