Understanding iterative upper bound search

Like the lower bound, we can find the upper bound for a given value in a binary search tree iteratively. Since we only move from top to bottom in the tree and do not backtrack, we can replace the recursive function calls with loops to get an algorithm to find the upper bound of value in a binary search tree iteratively.

Algorithm

The iterative algorithm for finding the upper bound is similar to the recursive algorithm. We can piggyback on the iterative search algorithm we learned earlier and keep track of the most recent value greater than the given value as we go down the tree to get the upper bound.