  We give an algorithm to enumerate the results on trees of monadic
second-order (MSO) queries represented by nondeterministic tree automata. After
linear time preprocessing (in the input tree), we can enumerate answers with
linear delay (in each answer). We allow updates on the tree to take place at
any time, and we can then restart the enumeration after logarithmic time in the
tree. Further, all our combined complexities are polynomial in the automaton.
  Our result follows our previous circuit-based enumeration algorithms based on
deterministic tree automata, and is also inspired by our earlier result on
words and nondeterministic sequential extended variable-set automata in the
context of document spanners. We extend these results and combine them with a
recent tree balancing scheme by Niewerth, so that our enumeration structure
supports updates to the underlying tree in logarithmic time (with leaf
insertions, leaf deletions, and node relabelings). Our result implies that, for
MSO queries with free first-order variables, we can enumerate the results with
linear preprocessing and constant-delay and update the underlying tree in
logarithmic time, which improves on several known results for words and trees.
  Building on lower bounds from data structure research, we also show
unconditionally that up to a doubly logarithmic factor the update time of our
algorithm is optimal. Thus, unlike other settings, there can be no algorithm
with constant update time.
