We generalise a search algorithm by Mohri and Riley from strings to trees. The original algorithm takes as input a weighted automaton A over the tropical semiring, together with an integer N, and outputs N strings of minimal weight with respect to A. In our setting, the input automaton defines a weighted tree language, again over the tropical semiring, and the output is a set of N trees with minimal weight. We prove that the algorithm is correct, and that its time complexity is a low polynomial in N, m, n, and r, where m and n are the number of transitions and the number of states of A, respectively, and r is the maximum rank of symbols in the input alphabet.