Introduction

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 TT of length nn is a compressed trie of all nn suffixes of TT. 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)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(n2)O(n^2) time and space, which is catastrophic for large texts. For years researchers assumed O(n)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)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.

Build It Yourself

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">String:</label>
  <input id="strInput" type="text" value="banana" maxlength="12" spellcheck="false" autocomplete="off" />
  <button id="btnReset" type="button">Reset</button>
  <button id="btnStep" type="button">Step →</button>
  <button id="btnAll" type="button">Build all</button>
</div>
<div class="progress-row">
  <span id="progressLabel">Ready. Press Step or Build all.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Simplified Ukkonen's suffix tree — step-by-step visualizer.
// We build the tree phase by phase (one character at a time) and
// draw the resulting tree after each phase using a canvas.
// For correctness we implement the three rules exactly:
//   Rule 1: leaf edges grow automatically (open end).
//   Rule 2: create new internal node + new leaf when mismatch.
//   Rule 3: path exists — stop (remainder > 0, move to next phase).

const INF = 1e9;

class Node {
  constructor(start, end) {
    this.start = start;
    this.end = end;         // number or reference to {val} for leaves
    this.children = {};     // char -> node index
    this.suffixLink = 0;    // index (0 = root)
    this.id = -1;
  }
  edgeLen(phase) {
    return Math.min(typeof this.end === 'object' ? phase + 1 : this.end, INF) - this.start;
  }
}

let nodes, text, phase, remainder, activeNode, activeEdge, activeLength;
let built = false;

function init() {
  const s = document.getElementById('strInput').value.replace(/[^a-z0-9]/gi,'');
  if (!s) return;
  // Append terminal character
  text = s + '


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)O(n).

;
  nodes = [];
  // node 0 = root
  nodes.push(new Node(-1, -1)); nodes[0].id = 0;
  phase = -1;
  remainder = 0;
  activeNode = 0;
  activeEdge = -1;
  activeLength = 0;
  built = false;
  document.getElementById('progressLabel').textContent = 'Ready. Press Step or Build all.';
  document.getElementById('infoLabel').textContent = '';
  drawTree();
}

function newNode(start, end) {
  const n = new Node(start, end);
  n.id = nodes.length;
  nodes.push(n);
  return n.id;
}

// Walk down from node using activeEdge/activeLength (canonicalize)
function walkDown(nodeIdx) {
  const n = nodes[nodeIdx];
  const len = n.edgeLen(phase);
  if (activeLength >= len) {
    activeEdge += len;
    activeLength -= len;
    activeNode = nodeIdx;
    return true;
  }
  return false;
}

function step() {
  if (built) return;
  phase++;
  if (phase >= text.length) { built = true; return; }
  const c = text[phase];

  // Extend all leaves (implicit via open end — tracked by `phase`)
  remainder++;
  let lastNewInternal = -1;

  while (remainder > 0) {
    if (activeLength === 0) activeEdge = phase; // active edge = current char

    const ae = text[activeEdge];
    if (nodes[activeNode].children[ae] === undefined) {
      // Rule 2: no edge from activeNode starting with ae — create leaf
      const leaf = newNode(phase, {val: INF}); // open end
      nodes[activeNode].children[ae] = leaf;
      if (lastNewInternal !== -1) {
        nodes[lastNewInternal].suffixLink = activeNode;
        lastNewInternal = -1;
      }
    } else {
      // Edge exists
      let next = nodes[activeNode].children[ae];
      if (walkDown(next)) continue; // Rule 3 shortcut: re-check after walk-down

      const nextNode = nodes[next];
      if (text[nextNode.start + activeLength] === c) {
        // Rule 3: character already on edge — just extend activeLength
        activeLength++;
        if (lastNewInternal !== -1) {
          nodes[lastNewInternal].suffixLink = activeNode;
        }
        break; // stop for this phase
      }

      // Rule 2: split edge
      const splitEnd = nextNode.start + activeLength;
      const split = newNode(nextNode.start, splitEnd);
      nodes[activeNode].children[ae] = split;

      // New leaf for current character
      const leaf = newNode(phase, {val: INF});
      nodes[split].children[c] = leaf;

      // Old edge continues from split point
      nextNode.start = splitEnd;
      nodes[split].children[text[splitEnd]] = next;

      if (lastNewInternal !== -1) {
        nodes[lastNewInternal].suffixLink = split;
      }
      lastNewInternal = split;
    }
    remainder--;
    if (activeNode === 0 && activeLength > 0) {
      activeLength--;
      activeEdge = phase - remainder + 1;
    } else if (nodes[activeNode].suffixLink > 0) {
      activeNode = nodes[activeNode].suffixLink;
    } else {
      activeNode = 0;
    }
  }

  updateProgress();
  drawTree();
}

function buildAll() {
  while (!built && phase < text.length - 1) step();
  if (!built) step(); // last step (terminal $)
}

function updateProgress() {
  const done = phase + 1;
  const total = text.length;
  const shown = text.slice(0, done);
  document.getElementById('progressLabel').textContent =
    fmt('Phase %done%/%total%: processed "%shown%" — nodes: %length%, remainder: %remainder%', { done: done, total: total, shown: shown, length: nodes.length, remainder: remainder });
  document.getElementById('infoLabel').textContent =
    phase < text.length - 1
      ? fmt('Active node: %activeNode%, active edge char: "%v%", active length: %activeLength%', { activeNode: activeNode, v: text[activeEdge] || '—', activeLength: activeLength })
      : 'Tree complete. Every suffix is a root-to-leaf path.';
}

// ── Drawing ──────────────────────────────────────────────────────────────────
function drawTree() {
  const canvas = document.getElementById('treeCanvas');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // BFS to assign positions
  const pos = {}; // nodeId -> {x,y}
  // Count leaves under each node for width allocation
  function countLeaves(id) {
    const n = nodes[id];
    const ckeys = Object.keys(n.children);
    if (ckeys.length === 0) return 1;
    let s = 0;
    for (const k of ckeys) s += countLeaves(n.children[k]);
    return s;
  }
  const totalLeaves = Math.max(countLeaves(0), 1);
  const MARGIN = 28, TOP = 24, BOT = H - 20;

  function layout(id, xL, xR, depth, maxDepth) {
    const x = (xL + xR) / 2;
    const y = TOP + (depth / maxDepth) * (BOT - TOP);
    pos[id] = {x, y};
    const n = nodes[id];
    const ckeys = Object.keys(n.children).sort();
    let cx = xL;
    for (const k of ckeys) {
      const childId = n.children[k];
      const frac = countLeaves(childId) / totalLeaves;
      layout(childId, cx, cx + frac * (W - 2 * MARGIN), depth + 1, maxDepth);
      cx += frac * (W - 2 * MARGIN);
    }
  }

  // Compute tree depth
  function maxDepth(id, d) {
    const n = nodes[id];
    const ckeys = Object.keys(n.children);
    if (ckeys.length === 0) return d;
    return Math.max(...ckeys.map(k => maxDepth(n.children[k], d + 1)));
  }
  const md = Math.max(maxDepth(0, 0), 1);
  layout(0, MARGIN, W - MARGIN, 0, md);

  // Draw edges
  ctx.lineWidth = 1.4;
  function drawEdges(id) {
    const n = nodes[id];
    const {x: px, y: py} = pos[id];
    for (const k of Object.keys(n.children)) {
      const childId = n.children[k];
      const {x: cx, y: cy} = pos[childId];
      ctx.strokeStyle = '#7090b0';
      ctx.beginPath(); ctx.moveTo(px, py); ctx.lineTo(cx, cy); ctx.stroke();

      // Edge label
      const child = nodes[childId];
      const end = typeof child.end === 'object' ? phase : child.end;
      const label = text.slice(child.start, end + 1);
      const mx = (px + cx) / 2, my = (py + cy) / 2;
      ctx.save();
      ctx.font = '10px ui-monospace, monospace';
      ctx.fillStyle = '#1d3557';
      ctx.textAlign = 'center';
      ctx.textBaseline = 'middle';
      ctx.fillText(label.length > 8 ? label.slice(0, 7) + '…' : label, mx, my);
      ctx.restore();

      drawEdges(childId);
    }
  }
  drawEdges(0);

  // Draw suffix links (dashed)
  ctx.setLineDash([3, 3]);
  ctx.strokeStyle = '#e08c30';
  ctx.lineWidth = 1;
  for (const n of nodes) {
    if (n.suffixLink > 0 && pos[n.id] && pos[n.suffixLink]) {
      const {x: ax, y: ay} = pos[n.id];
      const {x: bx, y: by} = pos[n.suffixLink];
      ctx.beginPath();
      ctx.moveTo(ax, ay); ctx.lineTo(bx, by);
      ctx.stroke();
    }
  }
  ctx.setLineDash([]);

  // Draw nodes
  for (const n of nodes) {
    if (!pos[n.id]) continue;
    const {x, y} = pos[n.id];
    const isLeaf = Object.keys(n.children).length === 0;
    const isActive = n.id === activeNode;
    ctx.beginPath();
    ctx.arc(x, y, isLeaf ? 4 : 6, 0, 2 * Math.PI);
    ctx.fillStyle = isActive ? '#e63946' : (isLeaf ? '#9fb2c8' : '#1d3557');
    ctx.fill();
    if (!isLeaf) {
      ctx.strokeStyle = '#fff';
      ctx.lineWidth = 1.5;
      ctx.stroke();
    }
  }

  // Legend
  ctx.font = '10px system-ui';
  ctx.fillStyle = '#888';
  ctx.textAlign = 'left';
  ctx.fillText('● active node', 8, H - 8);
  ctx.fillStyle = '#e08c30';
  ctx.fillText('— suffix link', 95, H - 8);
}

// Wire up
document.getElementById('btnReset').addEventListener('click', init);
document.getElementById('btnStep').addEventListener('click', step);
document.getElementById('btnAll').addEventListener('click', buildAll);
document.getElementById('strInput').addEventListener('input', init);
init();
Result
Console

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)O(n).

The Real Complexity

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

  • Naïve construction inserts each of the nn suffixes into a trie one by one. The kk-th suffix has length kk, so the total work is 1+2+⋯+n=O(n2)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]T[1..i] is transformed into one for T[1..i+1]T[1..i+1] by a bounded number of operations, thanks to two observations:
    1. Implicit extensions: if the character T[i+1]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 vv that represents string ss, the algorithm follows the suffix link to the node representing ss without its first character. This jump is O(1)O(1) and prevents re-traversing long common prefixes.
  • Amortized O(n)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)O(n).
  • Space is also O(n)O(n): a suffix tree has at most 2n−12n-1 nodes and nn leaves. Edges are stored as (start,end)(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)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.

Where It Matters

A data structure that indexes every substring in O(n)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(n2)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)O(n) makes real-time indexing of large corpora feasible.
  • Longest common substring: given two strings SS and TT, build the suffix tree of S\T#$ and find the deepest internal node that has leaves from both strings — O(n+m)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)O(1) after O(n)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.

Conclusion

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(n2)O(n^2) construction into an O(n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ukkonen-suffix-tree/Content licensed under CC BY-NC 4.0.