  We study the compressed representation of a ranked tree by a (string)
straight-line program (SLP) for its preorder traversal, and compare it with the
well-studied representation by straight-line context free tree grammars (which
are also known as tree straight-line programs or TSLPs). Although SLPs turn out
to be exponentially more succinct than TSLPs, we show that many simple tree
queries can still be performed efficiently on SLPs, such as computing the
height and Horton-Strahler number of a tree, tree navigation, or evaluation of
Boolean expressions. Other problems on tree traversals turn out to be
intractable, e.g. pattern matching and evaluation of tree automata.
