Understanding recursive upper bound search

Finding the upper bound of a value in a binary search tree can be implemented by piggybacking on any of the binary tree traversal algorithms. It is very similar to searching for the value, so we can exploit the special property of a binary search tree to devise an exponentially faster algorithm. Let us look at the cases we need to consider

Algorithm

To find the smallest element greater than the given value, we follow an algorithm similar to search. We create a variable that stores the smallest value greater than the given value seen so far. Starting from the root, we check if the value at the node is less than or equal to the given value, and we go to the right child. If the value at the node is greater than the given value, we compare it with the value stored in our variable and update it if needed. We will have our answer in that variable when hitting a leaf node. Let us look at some examples to understand this better.