Ceil in BST

Practice Link

Given a BST and a number X, find Ceil of X. Note: Ceil(X) is a number that is either equal to X or is immediately greater than X.

If Ceil could not be found, return -1.

Approach#

Mirror of the floor problem. At each node, if the node's value >= input it is a valid ceil candidate (record it) and we move left to look for a closer (smaller) candidate. If the node's value < input, it is too small to be the ceil, so we move right. The last recorded candidate is the answer. The BST property ensures we eliminate half the remaining nodes at each step.

int findCeil(Node* root, int input) {
    if (root == NULL) return -1;
    int c=-1;
    while(root)
    {
        if(root->data>=input)
        {
            c=root->data;
            if(c==input)
                break;
            else
                root=root->left;
        }else
            root=root->right;
        
    }
    return c;
    
}

Time Complexity:

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

Space Complexity: O(1)