Ceil in BST

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.

Example 1:

Input:
      5
    /   \
   1     7
    \
     2 
      \
       3
X = 3
Output: 3
Explanation: We find 3 in BST, so ceil
of 3 is 3.

Example 2:

Input:
     10
    /  \
   5    11
  / \ 
 4   7
      \
       8
X = 6
Output: 7
Explanation: We find 7 in BST, so ceil
of 6 is 7.

Your task:
You don’t need to read input or print anything. Just complete the function findCeil() to implement ceil in BST which returns the ceil of X in the given BST.

Expected Time Complexity: O(Height of the BST)
Expected Auxiliary Space: O(Height of the BST).

Constraints:
1 <= Number of nodes <= 10⁵
1 <= Value of nodes<= 10⁵

Solution:

public class CeilInBST {
    static int findCeil(BinaryTreeNode root, int key) {
        int ceil = -1, t;
        if (root == null) return ceil;
        if (root.data == key)
            return key;
        if (root.data > key) {
            ceil = root.data;
            t = findCeil(root.left, key);
        } else
            t = findCeil(root.right, key);
        if (t != -1 && (ceil == -1 || ceil > t))
            ceil = t;
        return ceil;
    }

    public static void main(String[] args) {
//        String tree = "5 1 7 N 2 N N N 3";
//        int key = 3;
//        String tree = "10 5 11 4 7 N N N N N 8";
//        int key = 6;
        String tree = "7 1 9 N 4 8 10";
        int key = 2;
        BinaryTreeNode root = Util.buildBinaryTree(tree);
        System.out.println(findCeil(root, key));
    }
}

Explanation:

As it is binary search tree we have to travel only the portion of the given tree.

At first we will compare the current node value. If it is same as key then we can return that value and no need to travel further as we got the exact value what we are looking for.

If the number is greater it might be the possible ceil. So record that number (c1) and travel left to find is there any other ceil which is lesser than current node value (c2).

If the number is smaller it can’t be the ceil, So we have to travel right to find the ceil (c2).

Once the above step completed compare c1 and c2 whichever is smaller that is the ceil.