Finding optimal binary search trees in terms of minimal search cost for a sequence of key queries is a well studied problem in computer science. An important theorem over the combinatorial structure of the problem found by Knuth in 1971 can be used to speed up a dynamic program for the problem to O(n^2) time, where n is the number of keys. Recently, Berendsohn and Kozma gave a 2-approximation algorithm for a generalization of optimal binary search trees to search trees on trees, which runs in O(n^3) time. We show, that Knuth theorem also holds in this setting and use it to improve the running time of the algorithm to O(min(D^2*L^2, n^3)), where D denotes the diameter and L the number of leaves of the search space tree. We give a full implementation of both algorithms and verify the correctness and running time on randomly generated trees of different types. Further, we show that a bound given by Mehlhorn for binary search trees can be generalized to search trees on trees.