Skip to main content

Ceil from BST

Problem​

Ninja is given a binary search tree and an integer. Now he is given a particular key in the tree and returns its ceil value. Can you help Ninja solve the problem?

Solution Approach​

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

Click - to see solution code
int findCeil(BinaryTreeNode<int> *root, int x) {
    if (!root) return -1;
    if (root->data == x) return x;
    if (root->data > x) {
        int z = findCeil(root->left, x);
        if (z != -1) {
            return min(root->data, z);
        } else
            return root->data;
    }
    return findCeil(root->right, x);
}