Summary: We introduce the subtree max gap problem. Consider a rooted tree \(T\) with \(n\) leaves whose internal nodes have at least two children. Each leaf is associated with a real number. For each internal node \(v\), let \(A_v\) be the set of numbers associated with the leaves in the subtree rooted at \(v\) which are regarded as points on the \(x\)-axis. The subtree max gap problem is to compute the maximum distance (gap) between any two consecutive points of \(A_v\) for every internal node \(v\) of \(T\). Our algorithm for the subtree max gap problem follows a series of reductions to other combinatorial problems which are interesting on their own merit. The algorithm runs in \(O(\log n)\) time using \(n\) processors on the concurrent-read exclusive-write parallel random access machine. The subtree max gap problem plays a central role in the parallel solution of the string covering problem. Recently, C. S. lliopoulos, D. W. G. Moore and K. Park [“Covering a string”, Algorithmica 16, No. 3, 288–297 (1996; Zbl 0858.68067)] gave an \(O(n\log n)\) time sequential algorithm for the string covering problem. Neither parallelizing the above sequential algorithm nor using known techniques from algorithms on strings seems to yield an efficient parallel algorithm for string covering. Our parallel algorithm thus follows a new approach, using suffix trees and reducing the string covering problem to the subtree max gap problem. The algorithm runs in \(O(\log n)\) time using \(n\) processors on the concurrent-read concurrent-write parallel random access machine, thereby matching the number of operations of lliopoulos et al. (loc. cit.).