Cracking the coding interview: Ceil in BST — 2
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.
X = 3
Explanation: We find 3 in BST, so ceil
of 3 is 3.
X = 6
Explanation: We find 7 in BST, so ceil
of 6 is 7.
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).
1 <= Number of nodes <= 105
1 <= Value of nodes<= 105
Time complexity: O(1)
Space complexity: O(1)
To approach the problem, recursive algorithm could be an effective strategy to solve it. According to the requirement of the question, it demands to find out the ceiling value, which is equivalent or greater than x. The idea of doing it is to search from the smallest value of x from left hand side, then recursively filtering out the closest ceiling value, then return it.