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 smallest 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.

1. The value is present in the tree

In this case, the given value is the lower bound, and we will reach it during the search.