From the notes:

It is not difficult to observe that the suffix array $ \texttt{SA}$ of the text $ \texttt{T}$ can be obtained from its suffix tree $ \texttt{ST}$ by performing an in-order visit: each time a leaf is encountered, the suffix-index stored in this leaf is written into the suffix array $ \texttt{SA}$ ; each time an internal node u is encountered, its associated value is written into the array $ \texttt{lcp}$ .

**How do you do the inorder visit when a node has more than two children?**

Let’s say you visit the leftmost child, then the node, then the other leftmost child. Then do you visit again the node?

*SA* in an array of pointer to suffixes, ordered lexicographically.

*lcp* contains the longest common prefix between two consecutive suffixes $ \text{suff}_{SA[i]} \text{ and } \text{suff}_{SA[i+1]}$ .

The $ represents a char that’s smaller than every other char.

The value associated to each node is the length of the prefix spelled so far.

The leaves represents indices of suffixes. If T = banana$ , the leaf 3 represents nana$ (T[3,7])

In the image there’s what is supposed to be a suffix tree, but I think there’s an error since the edges should be sorted according to their label and the leaf 7 with the edge labeled "$ " should be the leftmost leaf and edge.

When simulating the algorithm, first you visit the node 7 ( using the fixed version of the tree ), then the root, so you have

`SA = [7, ...] lcp = [0, ...] `

Then let’s say you keep going on with an inorder visit of u. **When you go back to the root, do you insert the value 0 again in the lcp**? Or do you do it just the first time you visited the root?

In other words, do I visit child-root-child-root… or child-root-child-child…