IEICE TRANS. FUNDAMENTALS, VOL.E82–??, NO.1 JANUARY 1999

1

PAPER

Constructing the Suﬃx Tree of a Treewith a Large Alphabet
Tetsuo SHIBUYA† ,SUMMARY The problem of constructing the suﬃx tree of atree is a generalization of the problem of constructing the suﬃx
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’sO(n log |Σ|) time algorithm where n is the size of the CS-tree
and |Σ| is the alphabet size, which requires O(n log n) time if|Σ| is large. We improve this bound by giving an optimal linear
time algorithm for integer alphabets. We also describe a newdata structure, the Bsuﬃx tree, which enables eﬃcient query forpatterns of completely balanced k-ary trees from a k-ary tree orforest. We also propose an optimal O(n) algorithm for constructing the Bsuﬃx tree for integer alphabets.
key words: algorithm, suﬃx tree, common suﬃx tree, integeralphabet, tree pattern matching1.

Introduction

The suﬃx tree of a string S ∈ Σn is the compacted trieof all the suﬃxes of S$ ($ ∈/ Σ). This is a very fundamental and useful structure in combinatorial patternmatching. Weiner [18] introduced this structure andshowed that it can be computed in O(n|Σ|) time, where|Σ| is the alphabet size. Since then, much work has been
done on simplifying algorithms and improving bounds[5], [15], [17], with algorithms achieving an O(n log |Σ|)computing time (see also [11] for details). Recently,
Farach [8] proposed a new algorithm that achieved alinear time (independent from the alphabet size) for
integer alphabets.
A common suﬃx tree, or a CS-tree for short, is adata structure that represents a set of strings. Thisis also an important problem that appears in tasks
such as minimizing sequential transducers of deterministic ﬁnite automata [4] and tree pattern matching [14].
Kosaraju [14] mentioned that the generalized suﬃx treeof all the suﬃxes of a set of strings represented by a
CS-tree can be constructed in O(n log n) time where nis the size of the CS-tree. Breslauer [4] improved thisbound by giving an O(n log |Σ|) algorithm. Note thatboth of the algorithms were based on Weiner’s suﬃx
tree construction algorithm [18]. But this algorithm
becomes O(n log n) when Σ is large. In this paper, we
improve their bound by giving an optimal O(n) algorithm for integer alphabets.
We also deal with a new data structure called a
Manuscript received August 21, 2002.
Manuscript revised October 15, 2002.
†
The author is with IBM Tokyo Research Laboratory.

Bsuﬃx tree, which is a generalization of the suﬃx treeof a string. Using the suﬃx tree of a CS-tree, we canﬁnd a given path in a tree very eﬃciently. The Bsuﬃx
tree is a data structure that enables us to query any
given completely balanced k-ary tree pattern from a kary tree or forest very eﬃciently. Note that the conceptof a Bsuﬃx tree is very similar to that of an Lsuﬃx tree[1], [10], [13], which enables us to query any square submatrix of a square matrix eﬃciently. We will show that
this data structure can be built in O(n) time for integeralphabets. Bsuﬃx trees have many useful features incommon with ordinary suﬃx trees. For example, using
this data structure, we can ﬁnd a pattern (a completely
balanced k-ary tree) in a text k-ary tree in O(m log m)time, where m is the size of the pattern. Moreover,
we can enumerate common completely balanced k-ary
subtrees in a linear time. Considering that general tree
pattern matching requires an O(n log3 n) time [6], theseresults mean that a Bsuﬃx tree is a very useful data
structure.
The extended abstract of this paper has appearedin [16]. Note that we improved the computation timebound for constructing the suﬃx tree of a tree, which
was O(n log log n) in the abstract.
2.

Preliminaries

2.1 The Suﬃx Tree
The suﬃx tree of a string S ∈ Σn is the compacted trieof all the suﬃxes of S$ ($ ∈/ Σ). The tree has n + 1
leaves and each internal node has more than one child.
Each edge is labeled with a non-empty substring of S$
and no two edges out of a node can have labels whichstart with the same character. Each node is labeledwith the concatenated string of edge labels on the pathfrom the root to the node, and each leaf has a labelthat is a diﬀerent suﬃx of S$. Because each edge label
is represented by the ﬁrst and the last indices of thecorresponding substring in S$, the data structure canbe stored in O(n) space. In this paper, we deal with
only the suﬃx trees in which the edges going out froma node are sorted according to their labels. Notice that
this property is very convenient for querying substrings.
For this powerful and useful data structure, wehave the following theorems:
Theorem 1 (Farach [8]): The suﬃx tree of a string

IEICE TRANS. FUNDAMENTALS, VOL.E82–??, NO.1 JANUARY 1999

2

1

S1
S2
S4

5

5

S5
S6

3

4

S3

6
5

9

1
2

S7

3

$

8

Fig. 1 CS-tree of the strings S1 =‘1413$’, S2 =‘5413$’,
S3 =‘913$’, S4 =‘56213$’, S5 =‘3213$’, S6 =‘5213$’, and S7 =‘83$’

S ∈ {1, . . . , n}n can be constructed in O(n) time.

Note that alphabet {1, . . . , n} is called an integer alphabet. In this paper, we will deal with only integeralphabets. Farach’s suﬃx tree construction algorithm
and our algorithms to be presented use the following
theorem:
Theorem 2 (Harel and Tarjan [12]): For any treewith n nodes, we can ﬁnd the lowest common ancestor of any two nodes in a constant time after O(n)preprocessing if the following values can be obtainedin a constant time: bitwise AND, OR, and XOR of two
binary numbers, and the positions of the leftmost andrightmost 1-bit in a binary number.

linear to that of the CS-tree, because the number ofleaves of the suﬃx tree is equal to the number of edges
in the CS-tree. Note that the edge labels of the suﬃx
tree of a CS-tree corresponds to a path in the CS-tree,
and they can be represented by the pointers to the ﬁrst
edge (nearest to the leaves) and the path length.P
Let ni be the length of Si , and let N =i ni .
Let n be the number of nodes in the CS-tree of thestrings. The generalized suﬃx tree can be obtainedin O(N ) time in the case of integer alphabets (i.e.,Si ∈ {1, . . . , n}ni ) as follows. First, we construct thesuﬃx tree of a concatenated string of S1 $S2 $ · · · $Sk using Farach’s suﬃx tree construction algorithm. Then,
we obtain the generalized suﬃx tree by cutting away
the unwanted edges and nodes. But N is sometimes
much larger than the size n of the CS-tree: for example,
there exists a tree for which N is Θ(n2 ). This meansthat the O(N )-time suﬃx tree construction algorithm
given above is not at all a linear time algorithm. The
best-known O(n log |Σ|) algorithm [4] for this problem
is based on Weiner’s suﬃx tree construction algorithm[18]. We will improve it by giving a new algorithm
based on Farach’s linear-time suﬃx tree construction
algorithm.

This theorem indicates that the longest common preﬁx (LCP) of any two suﬃxes can be obtained from thesuﬃx tree in a constant time after linear-time preprocessing.

3.

2.2 The Suﬃx Tree of a TreeOur approach to constructing the suﬃx tree of a CStree is based on Farach’s suﬃx tree construction algorithm [8]. Farach’s algorithm has three steps. First, it
constructs a tree called an odd tree recursively. Next,
it constructs another tree called an even tree by using
the odd tree. Finally it constructs the suﬃx tree by
merging these two trees. Note that the odd tree is atrie of suﬃxes S[2i − 1] . . . S[n]$, and the even tree is atrie of suﬃxes S[2i] . . . S[n]$. This algorithm achievesan O(n) computation time for integer alphabets.
We later also deﬁne the odd and even trees for thesuﬃx tree of a CS-tree, and our algorithm also has three

A set of strings {S1 , . . . , Sk }, such that no string is a
suﬃx of another, can be represented by a common suﬃx
tree (CS-tree for short), which is deﬁned as follows:
Deﬁnition 1 (CS-tree): In the CS-tree of a set of
strings {S1 , . . . , Sk }, each edge is labeled with a single
character, and each node is labeled with the concatenated string of edge labels on the path from the node
to the root. In the tree, no two edges out of a node
can have the same label. Furthermore, the tree has kleaves, each of which has a diﬀerent label that is one of
the strings, Si .
Figure 1 shows an example of a CS-tree. The number of nodes in the CS-tree is equal to the number ofdiﬀerent suﬃxes of strings. Thus, the size of a CS-tree
is not larger than the sum of the lengths of the strings
represented by the CS-tree. Note that the CS-tree canbe constructed easily from strings in a time linear tothe sum of the lengths of the strings.
The generalized suﬃx tree of a set of strings{S1 , . . . , Sk } is the compacted trie of all the suﬃxes
of all the strings in the set. As mentioned in [14], thesuﬃx tree of a CS-tree is the same as the generalized
suﬃx tree of the strings represented by the CS-tree.
Furthermore, the size of the generalized suﬃx tree is

New Algorithm for Constructing the Suﬃx
Tree of a CS-Tree

3.1 Algorithm Outline

construct suﬃx tree(CS-tree U ){if (U consists of only 0 or 1 node) {The suﬃx tree T of U is obvious;
return(T );}Construct a tree U 0 (|U 0 | ≤ |U |/2);
TU 0 = construct suﬃx tree(U 0 );Construct a partial suﬃx tree Tsmall using TU 0 ;Construct a partial suﬃx tree Tlarge using Tsmall ;Merge Tsmall and Tlarge to construct T ;return(T );}Fig. 2 Algorithm outline for constructing the suﬃx tree of a
CS-tree.

SHIBUYA: CONSTRUCTING THE SUFFIX TREE OF A TREE WITH A LARGE ALPHABET

3

following similar steps. First we build the odd tree orthe even tree recursively, then we construct the evenor odd tree by using the odd or even tree, respectively,
and ﬁnally we merge them to construct the suﬃx tree.
Figure 2 shows the algorithm outline in a pseudo-code.
In our algorithm, we use the following theorem by
Dietz and several others [2], [3], [7]:Theorem 3: In any tree with n nodes, for any node
v in the tree and any integer d > 0 that is smaller thanthe depth of v, we can ﬁnd the ancestor of v whose
depth is d in constant time after O(n) preprocessing.
Let us now deﬁne several notations.
Let{S1 , . . . , Sk } be the strings represented by a given
CS-tree. Let ni be the length of Si and let Si =Si [ni ] . . . Si [1]. Note that the indices are arranged inreverse order. Above theorem 3 indicates that, for
any i and j, we can access Si [j] in constant timeafter O(n) preprocessing. Let Si (m) be Si ’s suﬃx
of length m, i.e., Si [m] . . . Si [1]. Let lcp(S, S 0 ) andlcs(S, S 0 ) be the lengths of the longest common preﬁx and suﬃx of strings S and S 0 , respectively. Let
parentU (v) be the parent node of v in the CS-tree U
if v is not the root node t; otherwise, let it be t: i.e.,
parentU (vi,j ) = vi,max(0,j−1) , where vi,j denotes the ancestor of vi whose depth is j. Let label(e) be the label
given to edge e in the CS-tree. Let TU be the suﬃx treeof the CS-tree U .
3.2

Building a Half of the Suﬃx Tree Recursively

All nodes in the CS-tree U = (V, E) have either odd oreven label length. Let Vodd and Veven be the nodes with
odd label lengths and those with even label lengths,
respectively. If |Vodd | ≥ |Veven |, let Vsmall = Veven
and Vlarge = Vodd ; otherwise, let Vsmall = Vodd andVlarge = Veven . We can obtain |Vodd | and |Veven | inO(n) time by the ordinary depth-ﬁrst search on the
CS-tree. Therefore, we can determine in a linear time
which node set is Vsmall . In this subsection, we willrecursively construct the compacted trie Tsmall of all
the labels of nodes in Vsmall . Note that the techniquefor constructing Tsmall is very similar to that for constructing the odd tree in Farach’s algorithm.
Consider a new CS-tree U 0 = (Vsmall , Esmall ),where Esmall = {(v, parentU 0 = parentU (parentU (v)))|v ∈ Vsmall , v 6= t} and the edge labels are determined as follows.
Radix sort the label pairspair(v) = (label((v, parentU (v))), label((parentU (v),parentU (parentU (v))))) for all v ∈ Vsmall \t and remove duplicates, where label(e) denotes the label ofan edge e in the original CS-tree U . Let rank(v)be the rank of pair(v) in the sorted list, which belongs to an integer alphabet [1, n/2] because the sizeof the new tree U 0 is not larger than half of that of
the original CS-tree U . Let orig pair(i) be a label pairpair(v) such that rank(v) = i. Let the label of an edge(v, parentU 0 (v)) ∈ Esmall be rank(v). Notice that allof these procedures can be performed in a linear time.
We then construct the suﬃx tree TU 0 of U 0 by using our entire algorithm recursively. After that, we construct Tsmall from TU 0 as follows. We can consider atree T 0 whose edge labels of TU 0 are modiﬁed to theoriginal labels in U : for example, if the label of an edge
in TU 0 is ijk, the label of the corresponding edge in T 0
is orig pair(i), orig pair(j), orig pair(k). Notice that
this modiﬁcation can be performed by making only aminor modiﬁcation of the edge label representation andthat it takes only linear time. We can construct Tsmall
from T 0 easily. T 0 contains all the labels of nodes in
Vsmall , but is not the compacted trie: the ﬁrst characters of labels of outgoing edges from the same node
may be the same. But the second character is diﬀerent, and the edges are sorted lexicographically. Thus
we can change T 0 to Tsmall by making only a minor adjustment: we merge such edges and make a node, andif all the ﬁrst characters of all the labels of edges are
the same, we delete the original node.
In this way, we can construct Tsmall in a T (n/2) +O(n) time, where T (n) is the time our algorithm takes
to build the suﬃx tree of a CS-tree of size n.
3.3 Building the Other Half of the TreeIn this section, we show how to construct the compacted trie Tlarge of all the labels of nodes in Vlarge
from Tsmall in a linear time. The technique is a slightly
modiﬁed form of the second step of Farach’s algorithm,
which constructs the even tree from the odd tree.
If we are given an lexicographic traverse of theleaves of the compacted trie (which is called lexordering in [8]), and the length of the longest common
preﬁx of adjacent leaves, we can reconstruct the trie[8], [9]. We will obtain these two parts of Tlarge from
Tsmall , and construct Tlarge in the same way. But thismethod can obtain only the label length from the leaf
or root for each node of the compacted trie. Recall thateach label is represented by the ﬁrst node and the label length in our case. We can obtain that node fromits speciﬁed depth and its some descendant leaf in constant time according to Theorem 3. Hence the total
time required by this procedure is O(n).
Any leaf in Tlarge , except for those with labels of
only one character, has a label consisting of a single
character followed by the label of some corresponding
leaf in Tsmall . We can obtain the lex-ordering of the labels of leaves in Tsmall by an in-order traverse of Tsmall
which takes only a linear time. Thus we can obtainthe lex-ordering of the labels of leaves (Si (m)) in Tlarge
by using the radix sorting technique, because we have
Si [m] and the lexicographically sorted list of Si (m − 1).
The longest common preﬁx length of adjacent
leaves of Tlarge can also be obtained easily by using Tsmall . Let Si (m) and Sj (n) be the labels of

IEICE TRANS. FUNDAMENTALS, VOL.E82–??, NO.1 JANUARY 1999

4

two adjacent leaves in Tlarge . If Si [m] 6= Sj [n], thelongest common preﬁx length is 0. Otherwise, it is
1 + lcp(Si (m − 1), Sj (n − 1)) which can be obtained ina constant time from Tsmall after linear-time preprocessing on Tsmall (see Theorem 2). In this way, we canconstruct Tlarge from Tsmall in O(n).
3.4

Merging the Trees

Now we have two compacted tries Todd and Teven . In
this subsection, we merge Todd and Teven to construct
the target suﬃx tree TU . We call the compacted trieof odd/even-length suﬃxes of strings the generalized
odd/even tree of the strings. The odd/even tree ofa CS-tree is also the generalized odd/even tree of thestrings represented by the CS-tree. Farach’s algorithm
merges the odd and even trees in a time linear to thesum of the sizes of odd and even trees. It can be directly
applied also to our problem of merging generalized odd
and even trees and we can also achieve O(n) time inour case. The outline of the algorithm is as follows.
First, we merge the even and odd trees as following
by treating one of two edge labels as a preﬁx of the otherlabel if the ﬁrst characters of labels of two edges are thesame. Let edges e1 = (v, v1 ) and e2 = (v, v2 ) be theedges which starts from the same node v and have thesame ﬁrst character. Let l1 and l2 be the label lengthsof e1 and e2 , respectively. Without loss of generality,
we let l1 ≥ l2 . Then we construct a internal node v10
between v and v1 if l1 > l2 , otherwise let v10 be v1 . In
case that l1 > l2 , let the label of edge (v, v10 ) be theﬁrst l2 characters of the label of original edge (v, v1 )and let the label of edge (v10 , v1 ) be the last l1 − l2characters of the label of original edge (v, v1 ). Then wemerge two edges (v, v10 ) and e2 . This merging requires
only constant time because we can ﬁnd the node of theCS-tree which corresponds to the ﬁrst character of newedge (v10 , v1 ) in a constant time. We merge recursively
all over the two trees by the normal coupled depth ﬁrst
search. Thus the total computing time required for themerging is also O(n).
Next, we unmerge the edges with diﬀerent labels
because we have merged edges too far. Farach showedthat we can unmerge correctly in a linear time [8] forthe problem of strings, which is also the case for our
problem. Consider a node u in the merged tree M ,and let v 0 ∈ Todd and w0 ∈ Teven be some nodes that
become u’s descendants, v and w respectively, in M .
Let L(u) be the length of the label of u, and L̂(u) be
the longest common preﬁx length of the labels of v andw. We can see that u is merged too far if L(u) > L̂(u).
L(u) can be consulted in Todd or Teven , and L̂(u) can becomputed for all the nodes in O(n) time by the Farach’s
technique which uses a data structure called d-links.
We call u a border node if L̂(u) < L(u) and L̂(p) = L(p)where p is the parent of u. All the border nodes canbe found in a linear time. We can correct M by only

unmerging the border nodes. For each unmerged edge,
we must ﬁnd the node of the CS-tree that corresponds
to the ﬁrst character of its label, which requires only aconstant time according to Theorem 3. Thus the total
computing time for unmerging is O(n).
Hence the step of our algorithm for merging trees
takes a total of O(n) time. Thus we obtain an equation
T (n) = T (n/2) + O(n), where T (n) is the time needed
to construct the suﬃx tree of a CS-tree of size n. Therefore, our algorithm achieves the optimal T (n) = O(n)computing time for general CS-trees with integer alphabets.
4.

The BSuﬃx TreeIn this section, we propose a new data structure, theBsuﬃx tree, which enables eﬃcient queries of completely balanced binary trees from any binary forest(including a single tree). It can also be used for querying completely balanced k-ary subtrees from any k-ary
forest (k need not be constant in this case), but we willdeal with binary trees at ﬁrst. The Bsuﬃx tree is adata structure for matching of nodes, but it can be also
used for matching of edges (see subsection 4.3).
4.1 Deﬁnition of the BSuﬃx Tree
Consider a completely balanced binary tree P of heighth. Let p1 , p2 , . . . , p2h −1 be the nodes of P in breadthﬁrst order, and let ci ∈ {1, . . . , n} be the alphabet given
for node pi . Note that pbi/2c is the parent of pi inthis order. We call c1 c2 · · · c2h −1 the label of P . We
call substring c2i · · · c2i+1 −1 of this label a Bcharacter.
Furthermore, we call a string of Bcharacters a Bstring.
For Bstring b1 b2 . . . bn , we call b1 b2 . . . bm (m < n) a
Bpreﬁx of the Bstring. Note that c1 c2 · · · c2h −1 is a
Bstring of length h. For two Bcharacters b1 and b2 ,we let b1 > b2 if b1 is lexicographically larger than b2 in
the normal string representation. Note that Bcharacterb = c2i · · · c2i+1 −1 can be represented by node p2i ∈ P
and integer i.
Consider a binary forest U of size n whose nodes
are labeled with a character of an integer alphabet{1, . . . , n}. Let v1 , v2 , . . . , vn be the concatenated listof the breadth-ﬁrst-ordered node lists of all the binary
trees in forest U , and let ai ∈ {1, . . . , n} be the label ofnode vi . Let Li be the label of the largest completely
balanced binary subtree of U whose root is node vi . We
call Li followed by $i ∈/ {1, . . . , n} ($i 6= $j ) the Blabelof node vi . If the roots of two completely balanced binary subtrees P1 and P2 of U are the same node and P1
includes P2 , the label of P2 is a Bpreﬁx of the label of
P1 . The Bsuﬃx tree of U is the compacted trie T of theBlabels of all the nodes in U in the Bstring sense, i.e.,the outgoing edges from some node in the suﬃx tree
have a label of diﬀerent Bcharacter. Figure 4 shows anexample of a Bsuﬃx tree. By using T , we can easily

SHIBUYA: CONSTRUCTING THE SUFFIX TREE OF A TREE WITH A LARGE ALPHABET

5query any completely balanced binary subtree of U .
Edge labels of T can be represented by the ﬁrst
node in U and the depths of the ﬁrst and the last nodes
in the corresponding subtree pattern. Therefore T canbe stored in O(n) space. Note that we can access any
member of the edge label of T in a constant time if wehave both the breadth-ﬁrst list and the depth-ﬁrst listof the nodes of each tree in forest U .
In a Bsuﬃx tree, to enable fast access to a node’s
outgoing edge whose ﬁrst Bcharacter of its label isgiven, two simple preprocessing can be considered. One
simple method is constructing a hash table for it, whichenables linear time query in average. The data structure for it can be built in linear time. The other method
is constructing a preﬁx tree to represent all of the ﬁrst
Bcharacters of edge labels, which enables deterministicO(m log |Σ|) query time for a query of size m, where |Σ|denotes the size of the alphabet. This data structure
can also be built in linear time.
4.2 Construction of the BSuﬃx TreeIn this subsection, we describe the O(n) algorithm forconstructing the Bsuﬃx tree T of U . Figure 3 shows
the outline of the algorithm in a pseudo-code.
If forest U consists of only nodes with less than twochildren, it is obvious that we can construct the Bsuﬃx
tree of U in O(n) time. Otherwise, we ﬁrst construct a
new binary forest U 0 as follows: For every node vi withtwo children vj , vj+1 , construct a node of U 0 (let it bewi ). If vj and/or vj+1 have two children, let wi be theparent of wj and/or wj+1 in forest U 0 . Radix sort thelabel pairs (aj , aj+1 ) and remove duplicates. Let thelabel a0i of wi be the rank of the label pair (ai , ai+1 ) in
the sorted list. Notice that the number of nodes in U 0 is
not larger than n/2. We construct the Bsuﬃx tree T 0 of
U 0 by using our entire algorithm recursively. Figure 5
shows an example of this recursive construction of new
binary forests (trees in this case). Next, we construct
T from T 0 .
If we are given the lexicographically sorted list of
the Blabels of all the nodes in U and the length (i.e.,
number of Bcharacters) of the longest common Bpreﬁxof adjacent Blabels in this list, we can construct Bsuﬃx
construct Bsuﬃx tree(binary forest U ){if (U has no node with more than 1 child) {The Bsuﬃx tree T of U is obvious;
return(T );}Construct a forest U 0 (|U 0 | ≤ |U |/2);
T 0 = construct Bsuﬃx tree(U 0 );Construct the Bsuﬃx tree T using T 0 ;return(T );}Fig. 3 Algorithm outline for constructing the Bsuﬃx tree of abinary forest.

tree T in a linear time. We obtain these two pieces of
information from T 0 .
Notice that the in-order traverse of leaves of T 0
corresponds to a lexicographically sorted list of all theﬁrst-character-deleted Blabels of nodes that have twochildren in U . Thus we can obtain the lexicographicallysorted list of all the node Blabels of U by radix sortingthe concatenated list of the in-order traverse of leavesof T 0 and the Blabels of nodes with no or only one child.
The longest common Bpreﬁx length l of adjacent
Blabels can also be obtained from T 0 . If the ﬁrst characters of two adjacent Blabels are diﬀerent, l = 0. Otherwise, if one of the adjacent Blabels consists of only
one character, the depth is l = 1. Otherwise, we compute the depth as follows. Let vi and vj be the adjacentnodes. Notice that we can obtain the longest common
Bpreﬁx length l0 of Blabels of wi and wj in U 0 in aconstant time (see Theorem 2). Then it is clear thatl = l0 + 1.
In this way we can construct T from T 0 in a linear
time. We obtain T (n) = T (n/2) + O(n), where T (n)denotes the time taken to compute the Bsuﬃx tree ofa binary tree of size n. Therefore we conclude that ouralgorithm runs in O(n) time.

4.3 Discussions on the Bsuﬃx Tree

Bsuﬃx trees are very similar to normal suﬃx trees. It
enables O(m log m) query for a completely balanced binary tree pattern of size m. It can also be used forﬁnding (largest) common completely balanced binary
subtrees of two binary trees in linear time. We canalso enumerate frequent patters of completely balanced
binary trees in linear time by using this data structure.
The data structure and our algorithm assume thatthe labels are given to nodes, but they can very easily
be modiﬁed to deal with edge-matching problems asfollows: Let the label of any node except for the root
be the label of the incoming edge from its parent. ThenT 0 in the above algorithm can be used as the compacted
trie for edge matching.
Bsuﬃx trees can also be used for querying completely balanced k-ary trees from any k-ary forest U .
First, if a node has less than k children, remove theedges between it and its children. Otherwise, we reconstruct each node that has k children as a completely
balanced binary tree of depth dlog2 ke and move eachchild to its leaf. For each inside node and leaf to which
no node was mapped, give as its label a new character
that is not in use but is same for all such nodes. Noticethat the size of the reconstructed forest is at most twiceas that of the original one. Then construct the Bsuﬃx
tree for this reconstructed binary tree. It can obviously
used for querying completely balanced k-ary trees.

IEICE TRANS. FUNDAMENTALS, VOL.E82–??, NO.1 JANUARY 1999

6

v1

1
2 v2
3

v4

4

1

v3

1

2

v7

v6
v5

3 v8

4

v9

34
$7

21

1
3421
$1

3
4
v10 v11

3434
$3

34
$8

$2

3434
$6

4

3

2
34

34
$9

$ 14

$4 $ 10$12$ 15$5 $ 11 $ 1334
34v12 v13 v14 v15(1) Binary tree U(2) Bsuﬃx tree for U
Fig. 4

1

v1
1

2 v2
3

v6

4
v4

An example of the Bsuﬃx tree.

v3

1

2

v7

v5
3 v8

4

v9

1

3
4
v10 v1134
3
4v12 v13 v14 v15
Fig. 5

5.

1

2
2

2

2
21
34

1

2
1
2

2
2
21
22

1
2

Recursive construction of new binary trees in computing Bsuﬃx tree

Concluding Remarks

We have described an optimal O(n) algorithm for constructing the suﬃx tree of a common suﬃx tree (CStree). In addition, we proposed a new data structure
called a Bsuﬃx tree, that enables eﬃcient query forcompletely balanced subtrees. As for future work, wemust seek for more useful suﬃx trees that allow querying more general and ﬂexible patterns than paths orcompletely balanced trees. It is also an important problem to deal with dynamic trees.
References[1] A. Apostolico and Z. Galil, eds., Pattern Matching Algorithms, Oxford University Press, New York, 1997.
[2] S. Alstrup and J. Holm, “Improved Algorithms for Finding
Level Ancestors in Dynamic Trees,” Proc. 27th International Colloquium on Automata, Languages, and Programming, LNCS 1853, pp. 73-84, 2000.
[3] O. Berkman and U. Vishkin, “Finding Level-Ancestors in
Trees,” J. Comp. Sys. Sci., Vol. 48, pp. 214-230, 1994.
[4] D. Breslauer, “The Suﬃx Tree of a Tree and Minimizing Sequential Transducers,” Theoretical Computer Science, Vol.
191, pp. 131-144, 1998.
[5] M. T. Chen and J. Seiferas, “Eﬃcient and Elegant Subword

Tree Construction,” A. Apostolico and Z. Galil, eds., Combinatorial Algorithms on Words, Chapter 12, NATO ASI
Series F: Computer and System Sciences, pp. 97-107, 1985.
[6] R. Cole, R. Hariharan and P. Indyk, “Tree Pattern Matching and Subset Matching in Deterministic O(n log3 n)time,” Proc. 4th Symposium on Discrete Algorithms, pp.
245-254, 1999.
[7] P. Dietz, “Finding level-ancestors in dynamic trees,” Proc.
2nd Workshop on Algorithms and Data Structures, LNCS
1097, pp. 32-40, 1991.
[8] M. Farach, “Optimal Suﬃx Tree Construction with Large
Alphabets,” Proc. 38th IEEE Symp. Foundations of Computer Science, pp. 137-143, 1997.
[9] M. Farach and S. Muthukrishnan, “Optimal Logarithmic
Time Randomized Suﬃx Tree Construction,” Proc. 23rd International Colloquium on Automata, Languages, and Programming, pp. 550-561, 1996.
[10] R. Giancarlo, “The Suﬃx Tree of a Square Matrix, with Applications,” Proc. 4th Symposium on Discrete Algorithms,
pp. 402-411, 1993.
[11] D. Gusﬁeld, Algorithms on Strings, Trees, and Sequences:
Computer Science and Computational Biology, Cambridge
University Press, 1997.
[12] D. Harel and R. R. Tarjan, “Fast Algorithms for Finding
Nearest Common Ancestors,” SIAM J. Computing, Vol. 13,
pp. 338-355, 1984.
[13] D. K. Kim and K. Park, “Linear Time Construction of 2-D
Suﬃx Trees,” Proc. 26th International Colloquium on Automata, Languages, and Programming, pp. 463-472, 1999.

SHIBUYA: CONSTRUCTING THE SUFFIX TREE OF A TREE WITH A LARGE ALPHABET

7[14] S. R. Kosaraju, “Eﬃcient Tree Pattern Matching,” Proc.
30th IEEE Symp. Foundations of Computer Science, pp.
178-183, 1989.
[15] E. M. McCreight, “A Space-Economical Suﬃx Tree Construction Algorithm,” J. ACM, Vol. 23, pp. 262-272, 1976.
[16] T. Shibuya, “Constructing the suﬃx tree of a tree witha large alphabet,” Proc. 10th Annual International Symposium on Algorithms and Computation, LNCS 1741, pp.
225–236, 1999.
[17] E. Ukkonen, “On-Line Construction of Suﬃx-Trees,” Algorithmica, Vol. 14, pp. 249-60, 1995.
[18] P. Weiner, “Linear Pattern Matching Algorithms,” Proc.
14th Symposium on Switching and Automata Theory, pp.
1-11. 1973.