This problem statement is confusing. I'm not sure that the assumption made by the current solution is correct, due to the problem's difficulty being an '8' in the textbook. Is it possible that the intent of the problem statement is for the phrase "every key in $S_{1}$ is smaller than any key in $S_{2}$" to be interpreted as "There exists some key, $k$, in $S_{2}$ such that all keys in $S_{1}$ are smaller than $k$?"
I'm not sure that my new interpretation is correct, because I haven't been able to come up with the required $O(h)$ solution using the new interpretation.