Understanding recursive lower bound search

Finding the lower 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 a 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

We follow the same path as the search by slightly modifying the search algorithm to find the first element greater than or equal to the given value. To search for the lower bound, we keep track of the most recent value we have seen so far that is greater than or equal to the given value. We will have our answer in that variable when hitting a leaf node. Let us look at the possible cases we need to consider.