We consider the problem of finding an optimal spanning tree with respe
ct to objective functions which depend on the set of leaves of the tre
e. We address 18 different such problems and determine their computati
onal complexity. Only a few of the problems examined have been given a
ttention in the existing literature. (C) 1996 John Wiley & Sons, Inc.