Exercise 14.3.3

Describe an efficient algorithm that, given an interval $i$, returns an interval overlapping $i$ that has the minimum low endpoint, or $T.nil$ if no such interval exists.

The existing algorithm is almost there – the only addition it needs to be made is that in case the current node overlaps with the supplied interval, instead of returning immediately, we need to keep track of the match, and continue left. Matches in the left subtree will have smaller low endpoints.

To keep it simple, we can just keep track of the matches, updating them only when the lower bound is smaller than the current match.