We prove that natural closure operations on quotient structures of the h-quasiorder of finite and (at most) countable k-labeled forests (k ≥ 3) are definable provided that minimal nonsmallest elements are allowed as parameters. This strengthens our previous result which holds that each element of the h-quasiorder of finite k-labeled forests is definable in the first-order language, and each element of the h-quasiorder of (at most) countable k-labeled forests is definable in the language Lω1ω; in both cases k ≥ 3 and minimal nonsmallest elements are allowed as parameters. Similar results hold true for two other relevant structures: the h-quasiorder of finite (resp. countable) k-labeled trees and k-labeled trees with a fixed label on the root element. © 2010 Springer Science+Business Media, Inc.