Ukkonen's Suffix Tree

Imagine you need to search a 3 billion-character genome for thousands of short patterns. Scanning the whole genome for each pattern would take forever. What if you could pre-process the genome once and then answer any query in time proportional only to the pattern's length?

That is exactly what a suffix tree delivers. A suffix tree for a string $T$ of length $n$ is a compressed trie of all $n$ suffixes of $T$. Every path from the root to a leaf spells out one suffix; every internal node marks a branching point where two or more suffixes diverge. Once built, the tree answers substring search in $O(m)$ — just walk the pattern down from the root.

The stumbling block is construction. A naïve approach — insert all suffixes one by one into a trie — costs $O(n^2)$ time and space, which is catastrophic for large texts. For years researchers assumed $O(n)$ was possible but elusive.

In 1995 the Finnish computer scientist Esko Ukkonen published an elegant online algorithm: he builds the suffix tree one character at a time, left to right, and never revisits earlier parts of the string. The key invention is the suffix link — a shortcut that lets the algorithm jump from an internal node to the node corresponding to the same string minus its first character. With suffix links in place, each character causes at most a constant amount of work amortized, giving an overall $O(n)$ time and space bound — proven optimal.

This article explains the idea, shows you the construction character by character, and explores where the algorithm matters in practice. For contrast, see also pattern matching and suffix automata.

Type any short string below (try banana or abcbc) and step through Ukkonen's algorithm one character at a time. Each step shows the current suffix tree, the active point (where the next extension begins), and the suffix links connecting internal nodes.

<div class="controls">
  <label for="strInput">{{lbl_string}}</label>
  <input id="strInput" type="text" value="banana" maxlength="12" spellcheck="false" autocomplete="off" />
  <button id="btnReset" type="button">{{btn_reset}}</button>
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnAll" type="button">{{btn_build_all}}</button>
</div>
<div class="progress-row">
  <span id="progressLabel">{{ready_msg}}</span>
</div>
<div class="canvas-wrap">
  <canvas id="treeCanvas" width="560" height="300"></canvas>
</div>
<div class="info-row">
  <span id="infoLabel"></span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .85rem; font-weight: 600; }
input[type=text] { font: 700 15px ui-monospace, monospace; padding: .3rem .5rem; border: 1px solid #adb1b8;
                   border-radius: 6px; width: 130px; letter-spacing: .05em; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button#btnReset { background: #fff; color: #1d3557; }
.progress-row { font-size: .82rem; color: #555; margin-bottom: .3rem; min-height: 1.3em; }
.canvas-wrap { background: #f4f7fa; border: 1px solid #dde3ea; border-radius: 10px;
               overflow: hidden; width: 100%; }
canvas { display: block; width: 100%; height: auto; }
.info-row { font-size: .8rem; color: #666; margin-top: .4rem; min-height: 1.2em; font-style: italic; }

// Code not found

Notice how adding one character never rebuilds the whole tree — the algorithm only updates the edges and nodes affected by that new character. The suffix links (dashed arrows) are the secret: they tell the algorithm exactly where to continue after creating a new internal node, avoiding redundant traversals. The total number of node and edge operations across the entire string is $O(n)$.

Why is building a suffix tree hard, and what makes Ukkonen's algorithm optimal?

• Naïve construction inserts each of the $n$ suffixes into a trie one by one. The $k$-th suffix has length $k$, so the total work is $1+2+\cdots+n = O(n^2)$, both time and space.
• Ukkonen's insight (1995) is to process the string left to right, extending every existing suffix implicitly. A suffix tree for $T[1..i]$ is transformed into one for $T[1..i+1]$ by a bounded number of operations, thanks to two observations:
  1. Implicit extensions: if the character $T[i+1]$ already exists on the edge leaving the active point, no structural change is needed — the new suffixes are already implicit in the tree.
  2. Suffix links: after creating a new internal node $v$ that represents string $s$, the algorithm follows the suffix link to the node representing $s$ without its first character. This jump is $O(1)$ and prevents re-traversing long common prefixes.
• Amortized $O(n)$: a potential argument shows the "active length" — the depth of the active point — increases by at most 1 per character added and decreases by 1 per suffix link followed. Since it can never go negative, the total number of suffix-link steps is $O(n)$.
• Space is also $O(n)$: a suffix tree has at most $2n-1$ nodes and $n$ leaves. Edges are stored as $(start, end)$ index pairs into the original string, so no substring copying is needed.

No algorithm can build a suffix tree faster than $O(n)$ (it must at least read the string), so Ukkonen's algorithm is asymptotically optimal. Compare this with pattern matching, where the KMP and Aho-Corasick algorithms also achieve linear time but only for a fixed pattern set — a suffix tree handles every possible query.

A data structure that indexes every substring in $O(n)$ time appears in surprising places:

• Bioinformatics: genome assemblers and aligners (BWA, Bowtie, MUMmer) build suffix trees or their close cousin the suffix array to map billions of short reads against a reference genome. The linear-time construction is essential — $O(n^2)$ would be orders of magnitude too slow.
• Full-text search engines: document indexing uses suffix arrays (a space-efficient cousin of the suffix tree). Building one in $O(n)$ makes real-time indexing of large corpora feasible.
• Longest common substring: given two strings $S$ and $T$, build the suffix tree of S\T#$ and find the deepest internal node that has leaves from both strings — $O(n+m)$ total.
• Data compression: Lempel-Ziv schemes find the longest previous match for each position; a suffix tree makes each lookup $O(1)$ after $O(n)$ preprocessing.
• Plagiarism and duplicate detection: suffix trees quickly find all repeated substrings or shared substrings between documents.

Understanding suffix trees gives you a window into the broader world of pattern matching and the frontier of sequence alignment in computational biology.

Ukkonen's suffix tree is a masterclass in algorithm design: a single structure that answers any substring query in optimal time, built online — one character at a time — with no backtracking over the input. The suffix link, a seemingly small pointer between internal nodes, is the idea that collapses an $O(n^2)$ construction into an $O(n)$ one.

The algorithm was published in 1995 and remains the reference construction today, underlying tools that handle some of the largest string-processing workloads on earth — from sequencing the human genome to indexing the web. If you have ever wondered how a search engine can find your query in milliseconds across billions of documents, a suffix-based index and Ukkonen's insight are a big part of the answer.