Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях).
По лексикографическому обходу листьев дерева и по известным длинам наибольшего общего префикса двух соседних листьев можно легко восстановить дерево.
Мы хотим получить лексикографически отсортированные нечетные суффиксы строки* [[ Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Строим по чётному дереву суффиксный массив]] — это можно сделать за О(n). * Дописываем ко всем суффиксам кроме того, что на нулевой позиции символ, предшествующий ему в строке. * Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже были отсортированыв суффиксном массиве. Тогда поразрядно отсортируем их по первому символу за линейное время. Для выяснение общего префикса строк можно находить общего предка вершин в * [[Сжатое суффиксное дерево|суффиксном дереве]]Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8. Такого предка можно найти за [http://e-maxxD0.ru/algo/lca_linear константное время, потратив <tex>O(n)</tex> на препроцессинг]B2. Для примера в этом дереве, общее начало строк '''5''' и '''3''' (<tex>11011111000</tex> и <tex>1111011111000</tex>) записано в пути от корня до общего предка этих вершин: (рисунок 3-1) [[Файл:treestep3_blueD0.jpgB0 |400px|рисунок 3-1Построить из нового суффиксного массива дерево]] Поскольку структуры нечётного дерева у нас заранее нет и мы её только строим, то подходящих предков мы можем найти в исходном чётном деревекоторое будет уже нечётным, для этого достаточно проверить вершины с номерами на единицу меньше и отрезать первый символ : (рисунок 3-2). [[Файл:treestep3_redчто тоже делается за линейное время.jpg|400px|рисунок 3-2]]
Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.
