Constructing the Suffix Tree of a Tree with a Large Alphabet

The problem of constructing the suffix tree of a common suffix tree (CS-tree) is
a generalization of the problem of constructing the suffix tree of a string.
It has many applications, such as in minimizing the size of sequential transducers and
in tree pattern matching. The best-known algorithm for this problem is Breslauer's
$O(n log d)$ time algorithm where n is the size of the CS-tree and
d is the alphabet size, which requires $O(n log n)$ time if d is large.
We improve this bound by giving an $O(n log log n)$ algorithm for integer alphabets.
For trees called shallow k-ary trees, we give an optimal linear time algorithm for them.
We also describe a new data structure, the Bsuffix tree, which enables efficient query for
patterns of completely balanced k-ary trees from a k-ary tree or forest.
We also propose an optimal O(n) algorithm for constructing the Bsuffix tree for
integer alphabets.