  The monadic second-order theory of trees allows quantification over elements
and over arbitrary subsets. We classify the class of trees with respect to the
question: does a tree T have a definable choice function (by a monadic formula
with parameters)? A natural dichotomy arises where the trees that fall in the
first class don't have a definable choice function and the trees in the second
class have even a definable well ordering of their elements. This has a close
connection to the uniformization problem.
