Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children

Question

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?

Answer 1

If a node has $l$ children, with $l \geq 2$ during the inorder visit you have to treat the first $l-1$ children as left nodes, and you have to visit the parent multiple ($l-1$) times, writing multiple times the length of the prefix spelled inside the lcp array.

This, applied to the tree in the image, would yield the correct:

SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

keeping in mind that the edge labeled "$" with the leaf 7 should be the leftmost.