# How to create a suffix tree by hand

I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand".

I do not see a simple way how to draw such a tree. Is there a simple step by step method for people not knowing the algorithms?

• Here are slides for McCreight & Ukkonen. There are sketches of intermediate representations of the first few steps on slide 4 and 48, respectively. Jan 5, 2015 at 10:22

Here is how to draw the suffix tree for the example $abaab\$$mentioned in the lecture notes appearing in greybeard's comment. Root. There are two characters appearing in the word, a,b, so the root has two outgoing edges, labeled a and b. Root->a. Following a, we have both characters a,b appearing in the word. So this note has two outgoing edges, labeled a and b. Root->a->a. There is only one suffix aab\$$ starting with$aa$, so we replace this node with a leaf, and modify the edge label to$ab\$$. Root->a->b. There are two suffixes abaab\$$ and $ab\$$starting with ab. Correspondingly, we add two children with edges labeled aab\$$ and$\$$. Root->b. Following b we have the two suffixes baab\$$ and $b\$$. Correspondingly, we add two children with edges labeled aab\$$ and$\.
The general method is similar. At each node $w$, we add children corresponding to all possible continuations of $w$ in the word. If there is only one continuation possible, we modify instead the edge label. This algorithm is easy to implement by hand, but could be hard to implement in linear time on a computer.