Suffix Tree

The suffix tree of a string S of length n is a compressed trie of all n suffixes of S, with each edge labeled by a non-empty substring of S and the property that no two edges out of any node start with the same character. After the seminal O(n) construction algorithms of Weiner (1973), McCreight (1976), and Ukkonen (1995), suffix trees became one of the most powerful data structures in stringology — Apostolico’s 1985 survey called them the “myriad-virtues” data structure because the same O(n) build supports an extraordinary range of O(m)- or O(n)-time queries: substring search, longest repeated substring, longest common substring of multiple strings, longest palindromic substring (via the generalized suffix tree), distinct-substring counting, and fast-as-possible regex pre-processing. The tree has at most 2n − 1 nodes (one leaf per suffix plus at most n − 1 internal branching nodes); each edge is stored implicitly as a pair (start, end) of indices into the original string, giving Θ(n) total space. The classical comparison is with the Suffix Array: a suffix array is the sorted permutation of suffix start-indices and uses ~4n to 5n bytes; a suffix tree uses ~20n bytes in practice (pointers, child arrays, suffix links). The suffix array is much more cache-friendly and ~3–5× more memory-efficient, so it has largely supplanted suffix trees for production string-search engines (e.g., genomic indexing, web-scale full-text search). Yet the suffix tree retains its primacy as a teaching data structure — every theorem in stringology is most naturally first proved on it — and is still preferred for problems whose query algorithms exploit the tree topology directly (longest common substring of k strings via colored suffix-tree paths; problems requiring O(1) lowest-common-ancestor queries between suffixes via tree LCA). Of the three classical construction algorithms, Ukkonen’s 1995 on-line O(n) algorithm is the canonical one to know — it processes the string left-to-right, maintaining the suffix tree of the prefix seen so far, and uses suffix links to amortize the per-character work to O(1). The construction is famously tricky (Gusfield’s 1997 textbook devotes 30 pages to it), but the result is one of the most beautiful exponential-to-linear amortization arguments in the algorithms canon.

1. Definition and Structure

Let S be a string of length n over an alphabet Σ. By convention, append a sentinel $ ∉ Σ so that S$ has length n + 1 and no suffix of S$ is a prefix of another suffix.

The suffix tree of S$ is a rooted tree such that:

1. The tree has exactly n + 1 leaves, numbered 0, 1, …, n. Leaf i corresponds to the suffix S[i..n]$ (the suffix starting at position i, terminated by the sentinel).
2. Every internal node (except possibly the root) has at least 2 children. (This is the “compression” property — there are no chains of degree-1 nodes.)
3. Every edge is labeled with a non-empty substring of S$.
4. No two edges out of the same node start with the same character (so the path from the root to any leaf spells out a unique suffix when edge labels are concatenated).
5. The label of the path from the root to leaf i (concatenating edge labels) is exactly the suffix S[i..n]$.

The sentinel $ ensures property (5) holds for every suffix, not just the long ones — without it, a suffix like "ab" of "abab" would terminate inside an edge rather than at a distinct leaf, breaking the leaf-per-suffix correspondence.

A suffix tree of length n + 1 (with the sentinel) has at most:

• n + 1 leaves (one per suffix).
• n internal nodes (proven below — every internal node is the lowest common ancestor of two leaves; there are at most n such “branching” points in a tree on n + 1 leaves where every internal node has ≥ 2 children).
• Total: ≤ 2n + 1 nodes.

Each edge stores its label as (i, j) — a pair of indices into S$ indicating the substring S[i..j]. This keeps space Θ(n) regardless of alphabet size.

2. Tiny Worked Example — "banana$"

The string S$ = "banana$" has length 7. Its suffixes:

i	suffix S[i..n]$
0	banana$
1	anana$
2	nana$
3	ana$
4	na$
5	a$
6	$

The suffix tree:

                  (root)
                /  |  |   \
              a$   $  na   banana$
             /        / \
            na    na$   $
           /  \
         na$   $

Reading off the seven leaves and their root-to-leaf paths:

Leaf	Path label	Suffix
5	a + $ = a$	a$ ✓
3	a + na + $ = ana$	ana$ ✓
1	a + na + na$ = anana$	anana$ ✓
6	$	$ ✓
4	na + $ = na$	na$ ✓
2	na + na$ = nana$	nana$ ✓
0	banana$	banana$ ✓

Every internal node corresponds to a repeated substring of S: the path label from the root to that internal node is a string that appears at least twice in S (specifically, in each of the suffixes corresponding to the leaves in its subtree). For "banana$":

• The a internal node (path a) — a appears at positions 1, 3, 5 in S (three times).
• The ana internal node (path ana) — wait, looking again at the tree above, the deeper internal node has path a + na = ana. And ana appears at positions 1 and 3 in S (twice).
• The na internal node — path na, appears at positions 2 and 4 (twice).

The deepest internal node has path label ana, length 3 — this is the longest repeated substring of "banana". This generalizes: in any suffix tree, the longest repeated substring is the path label to the deepest internal node, found in O(n) by a single tree traversal.

3. Why the Sentinel Matters

Without the $, consider "banana":

• Suffix 4 is na, suffix 2 is nana. The path for na is a prefix of the path for nana — meaning "na" would terminate in the middle of an edge on the path to "nana". There would be no leaf for "na" — the suffix tree’s “one leaf per suffix” property would fail.

Adding the sentinel $ (which by convention sorts smaller than every real character) ensures no suffix is a prefix of another: na$ and nana$ differ at position 2 (where one has $ and the other has n). They diverge at an internal node, and each gets its own leaf.

Some implementations skip the sentinel and use an implicit suffix tree where some suffixes terminate inside edges. Ukkonen’s algorithm builds an implicit suffix tree at each step and only needs the explicit version after final character processing — so the sentinel is added only at the end.

4. Operations

The suffix tree supports an extraordinary range of O(m) or O(n) queries after the O(n) build.

4.1 Substring Search — Does P (length m) appear in S?

Walk down from the root following the edges that match P, character by character. If you can match all m characters of P, then P occurs in S; otherwise it doesn’t. The leaves in the subtree rooted at where P ends are exactly the starting positions of all occurrences of P in S.

Time: O(m) to find whether P is in the tree, plus O(occ) to enumerate all occurrences (one per leaf in the matched subtree).

This is asymptotically optimal — better than Knuth-Morris-Pratt (O(n + m)) for repeated-pattern queries because the suffix tree pre-processes S once and answers any subsequent P query in O(m) time, not O(n + m).

4.2 Longest Repeated Substring

A substring is repeated iff its corresponding path in the suffix tree leads to an internal (branching) node — every internal node has at least two leaves in its subtree, meaning the path label appears in at least two distinct suffixes, i.e., at least twice. The longest repeated substring is the path label to the deepest internal node.

Compute by a DFS that tracks the depth (in characters, not edges) of the path; the maximum depth is the answer.

Time: O(n) by a single tree traversal.

For "banana", the deepest internal node is at depth 3 with path "ana", the answer.

4.3 Longest Common Substring of Two Strings

Build the generalized suffix tree of S₁#S₂$ (where # and $ are two distinct sentinels not appearing in either string). Mark every internal node with a color indicating which inputs (S₁, S₂, or both) have a leaf in its subtree. The longest path label whose subtree contains leaves from both S₁ and S₂ is the longest common substring.

Time: O(n₁ + n₂) for build + O(n₁ + n₂) for the coloring DFS.

This generalizes to k strings: a node is “good” if its subtree contains leaves from at least k of the input strings; the deepest “good” node gives the longest substring common to all k. Achieves O(N) where N = Σ |Sᵢ| — much better than the naive O(N²) cross-comparison.

4.4 Longest Palindromic Substring

Build a generalized suffix tree of S#reverse(S)$. A maximal palindrome centred at position c of S is bounded by the longest common extension (LCE) of the forward suffix starting just right of c and the reverse suffix corresponding to the text just left of c; each such LCE is a longest-common-prefix query between two suffixes, which is exactly a lowest-common-ancestor (LCA) query in the generalized suffix tree (§4.6). After O(n) preprocessing for O(1) LCA queries, every one of the O(n) candidate centres is resolved in O(1), so the whole problem is solved in O(n) (Gusfield 1997, Ch. 9; the LCE-via-LCA reduction is the standard route). This bound is genuine, not folklore — but the constant factors and implementation burden (build the generalized tree, augment it for LCA, manage two sentinels) are large. In practice essentially everyone reaches for Manacher’s Algorithm instead, a Θ(n) direct two-pointer expansion with a tiny constant and ~20 lines of code; the suffix-tree route survives mainly because LCE/LCA queries also answer many other palindrome-and-repeat questions on the same preprocessed structure.

4.5 Distinct-Substring Counting

The number of distinct substrings of S is the sum, over all edges, of the edge’s label length. Equivalently, (n(n+1)/2) − Σ LCP[i] where LCP is the longest-common-prefix array of the suffix array — but on the suffix tree it’s a single DFS counting edge characters.

Time: O(n).

4.6 Lowest Common Ancestor of Two Suffixes

Build the suffix tree, then preprocess for O(1) LCA queries via the Tarjan offline LCA algorithm or the Schieber-Vishkin online algorithm. The LCA of leaves i and j in the suffix tree corresponds to the longest common prefix of suffixes S[i..] and S[j..] — answered in O(1) per query after O(n) preprocessing.

This is the bedrock of many O(1) string-distance and substring-equivalence queries, including approximate matching with k mismatches.

5. Construction Algorithms

Three classical O(n) construction algorithms exist. They are all non-trivial — the obvious algorithm (insert each suffix one at a time, each insertion costing O(n)) gives O(n²), which is too slow.

5.1 Weiner’s Algorithm (1973)

Weiner’s algorithm builds the tree by inserting suffixes from longest to shortest (S[0..], then S[1..], etc.). It uses link arrays and rightward extensions; the analysis is O(n |Σ|) with non-trivial space overhead.

5.2 McCreight’s Algorithm (1976)

McCreight’s algorithm inserts suffixes from longest to shortest like Weiner, but uses suffix links (a pointer from the node spelling xα to the node spelling α) to skip redundant work. It runs in O(n) time for a constant-size alphabet — O(n |Σ|) with array children, O(n log |Σ|) with balanced-tree children — the same asymptotic class as Weiner and Ukkonen. Its named contribution was space: McCreight could “dispense with most of Weiner’s auxiliary data structures; only suffix links remained” (per Wikipedia’s Suffix tree article), hence the paper title “A space-economical suffix tree construction algorithm” and the O(n)-space result over Weiner’s heavier O(n |Σ|) structures.

5.3 Ukkonen’s Algorithm (1995) — The Modern Choice

Ukkonen’s is the canonical algorithm to learn. Its key features:

1. On-line construction. It processes characters of S left-to-right, maintaining the suffix tree of the prefix seen so far. After processing S[0..i], the tree contains all suffixes of S[0..i]. This makes it suitable for streaming inputs — useful when S is generated incrementally.
2. Linear time O(n) for constant-size alphabets, O(n log |Σ|) for general alphabets.
3. Implicit suffix trees. During construction, the algorithm maintains an implicit suffix tree where some suffixes terminate inside edges (without leaves). After the final character is processed and the sentinel $ is appended, all suffixes get explicit leaves.

The algorithm processes phases. In phase i, it extends the tree from the suffix tree of S[0..i−1] to the suffix tree of S[0..i] by adding the new character S[i] to every active suffix.

5.3.1 Three Extension Rules

For each suffix S[j..i−1] (already in the tree), to extend it to S[j..i]:

• Rule 1 (leaf extension). If the path S[j..i−1] ends at a leaf, extend the leaf’s edge label by appending S[i]. Implementing leaf edges as “open-ended” (storing only the start index, with the end index implicit as “current end of string”) makes Rule 1 take O(1) per phase across all leaves — this is the famous trick #1.
• Rule 2 (split + new leaf). If the path S[j..i−1] ends inside an edge or at a non-leaf node, and the next character on that edge (or the next-character child) is not S[i], split the edge at the current position, create an internal node, and add a new leaf with edge label S[i].
• Rule 3 (already there — do nothing). If S[i] is already present as the next character on the active edge, just advance the active position by one and stop the phase. This is trick #2: once Rule 3 fires, we can stop the phase early, because all subsequent (shorter) suffixes also end with S[i] already in the tree.

5.3.2 Suffix Links

A suffix link is a pointer from internal node v (path label xα for some character x and string α) to internal node w (path label α). Suffix links exist for every internal node that has been constructed.

Ukkonen’s algorithm uses suffix links for the trick #3: after performing Rule 2 at the active position for suffix S[j..i], instead of walking from the root for the next suffix S[j+1..i], follow the suffix link from the parent of the just-created node, then traverse only the remaining edges. Combined with skip/count trick (when traversing a known prefix, jump entire edges in O(1) per edge instead of walking character by character), this gives an amortized O(n) total construction.

5.3.3 Ukkonen Pseudocode

build_suffix_tree(S):
    n := length(S)
    root := new node
    active_node := root
    active_edge := None       # character index in S
    active_length := 0        # how far down the active edge
    remaining := 0            # suffixes still to be inserted
    end := -1                 # global "end" pointer for leaf edges (Trick #1)

    for i from 0 to n − 1:
        end := i              # leaf edges automatically extend
        remaining += 1
        last_new_internal := None

        while remaining > 0:
            if active_length == 0:
                active_edge := i

            if S[active_edge] is not a child of active_node:
                # Rule 2: create a new leaf
                add new leaf labeled (i, end) under active_node
                if last_new_internal is not None:
                    last_new_internal.suffix_link := active_node
                    last_new_internal := None
            else:
                next_node := child of active_node along character S[active_edge]
                edge_len := length of next_node's edge

                if active_length >= edge_len:
                    # Walk down the edge entirely (skip/count trick)
                    active_edge += edge_len
                    active_length -= edge_len
                    active_node := next_node
                    continue

                if S[next_node.edge_start + active_length] == S[i]:
                    # Rule 3: character already present, end phase
                    active_length += 1
                    if last_new_internal is not None:
                        last_new_internal.suffix_link := active_node
                    break

                # Rule 2 with edge split
                split_node := split next_node at active_length
                add new leaf with label (i, end) under split_node
                if last_new_internal is not None:
                    last_new_internal.suffix_link := split_node
                last_new_internal := split_node

            remaining -= 1

            # After Rule 2 from this active position, follow suffix link
            if active_node == root and active_length > 0:
                active_length -= 1
                active_edge := i − remaining + 1
            else:
                active_node := active_node.suffix_link or root

The control flow is genuinely intricate; the canonical references are Ukkonen’s 1995 paper and Gusfield’s 1997 textbook (Ch. 6). For interview purposes, knowing the existence of O(n) Ukkonen’s algorithm and the role of suffix links is sufficient; full implementation is rarely demanded.

5.3.4 Complexity Argument — Why It’s O(n)

The total number of operations is bounded by:

1. Leaf extensions (Rule 1): O(1) per phase × n phases = O(n). (The “open-ended end pointer” trick: a leaf with edge-label (j, end) where end is a global variable that increments with each phase — no per-leaf work needed.)
2. Rule 2 splits: Each Rule 2 application creates one new internal node. There are at most n internal nodes total in the final tree, so total Rule 2 work across all phases is O(n).
3. Rule 3 early termination: Each phase ends as soon as Rule 3 fires. Rule 3 doesn’t create new nodes.
4. Suffix link traversal (skip/count): Each suffix-link traversal moves the active point. The total active-length decrease across all phases is bounded by the total active-length increases, which is O(n). So suffix-link traversals are also O(n) amortized.

Total: O(n) (assuming constant alphabet size, which is the standard assumption; for general alphabets the bound is O(n log |Σ|) due to child-lookup costs).

5.4 Farach’s Algorithm (1997)

For very large alphabets (|Σ| = ω(n)), Farach’s 1997 algorithm achieves true O(n) construction by reduction to a modified O(n log n) integer sort. It is asymptotically optimal but rarely implemented because Ukkonen’s O(n log |Σ|) is fast enough in practice.

6. Generalized Suffix Tree

The generalized suffix tree of k strings S₁, S₂, …, S_k is the suffix tree of S₁ # S₂ # … # S_k $ where # and $ are distinct sentinels not appearing in any input string. Each leaf is labeled with (i, j) indicating “this is the j-th suffix of Sᵢ.”

The generalized suffix tree supports:

• Longest common substring of k strings in O(N) total (N = Σ |Sᵢ|) by coloring leaves by their string of origin and finding the deepest internal node whose subtree contains all k colors.
• Multi-pattern matching — given many query patterns, find all occurrences of each in O(|P|) + O(occurrences) per query.

7. Suffix Tree vs Suffix Array — Detailed Comparison

Property	Suffix Array	Suffix Tree
Build time	O(n log n) (Manber-Myers); O(n) via DC3 or SA-IS	O(n) (Ukkonen, McCreight, Weiner)
Build complexity	Conceptually simple, ~50 lines for O(n log n)	Conceptually intricate, ~300+ lines for O(n)
Memory (practical)	~4n–5n bytes (int[n] + LCP)	~20n–40n bytes (pointers, child arrays)
Cache friendliness	Excellent (array of integers, sequential access)	Poor (pointer-chased tree traversals)
Substring search	O(m log n) (binary search) or O(m + log n) with LCP-array enhancements	O(m)
Longest common substring of k strings	O(N log N) with augmentation	O(N)
LCA between two suffixes	Indirectly via RMQ on LCP array	Directly via tree LCA
In-place updates	Hard	Hard (suffix trees over evolving strings is an open research area)
Used in production	Yes — BWT-based aligners (BWA, Bowtie), genomic indexes, full-text search	Rarely; mainly pedagogical and theoretical

The suffix array dominates in practice because of the constant-factor space and cache-locality advantages. The suffix tree dominates in theory because tree-topology operations (LCA, deepest internal node, color-tracking DFS) are direct and natural.

For the SWE interview: knowing the suffix tree exists, that Ukkonen’s algorithm builds it in O(n), and that it supports substring search in O(m) is usually enough; the suffix array is the pragmatic choice and is more commonly tested in coding rounds.

8. Pseudocode — Substring Search on a Built Suffix Tree

search(tree, P):
    node := tree.root
    pos := 0                         # current index into P

    while pos < |P|:
        if no child of node has edge starting with P[pos]:
            return "NOT FOUND"

        child := child of node on character P[pos]
        edge := substring of S corresponding to (child.start, child.end)

        for k from 0 to |edge| − 1:
            if pos == |P|:
                break                # exhausted P inside this edge
            if edge[k] != P[pos]:
                return "NOT FOUND"
            pos += 1

        node := child

    # P matches a prefix of the path; all leaves in subtree(node) are matches
    return all leaf indices in subtree rooted at 'node'

O(m) to find the matching subtree, O(occ) to enumerate matches.

9. Python Implementation — Naive O(n²) for Pedagogy

A full Ukkonen implementation is ~200 lines; for pedagogical clarity here is the naive O(n²) build that explicitly inserts every suffix:

class SuffixTreeNode:
    def __init__(self):
        self.children: dict[str, "SuffixTreeNode"] = {}
        self.edge: str = ""           # edge label leading INTO this node from its parent
        self.suffix_index: int = -1   # if this is a leaf, which suffix it represents
 
 
def build_suffix_tree_naive(S: str) -> SuffixTreeNode:
    """
    Naive O(n^2) suffix-tree construction. Inserts each suffix one at a time.
    Pedagogical only; use Ukkonen's O(n) for real applications.
    """
    if not S.endswith("$"):
        S = S + "$"
    root = SuffixTreeNode()
    n = len(S)
 
    for i in range(n):
        suffix = S[i:]
        _insert_suffix(root, suffix, i)
 
    return root
 
 
def _insert_suffix(root: SuffixTreeNode, suffix: str, suffix_index: int) -> None:
    node = root
    j = 0
    while j < len(suffix):
        c = suffix[j]
        if c not in node.children:
            # Create a new leaf with the rest of the suffix as its edge label.
            leaf = SuffixTreeNode()
            leaf.edge = suffix[j:]
            leaf.suffix_index = suffix_index
            node.children[c] = leaf
            return
 
        child = node.children[c]
        edge = child.edge
        # Walk down the edge as far as we match.
        k = 0
        while k < len(edge) and j + k < len(suffix) and edge[k] == suffix[j + k]:
            k += 1
        if k == len(edge):
            # Matched the whole edge; descend into child and continue.
            node = child
            j += k
            continue
        # Edge differs at position k: split.
        split = SuffixTreeNode()
        split.edge = edge[:k]
        node.children[c] = split
        child.edge = edge[k:]
        split.children[edge[k]] = child
        # Add new leaf for the rest of the suffix.
        leaf = SuffixTreeNode()
        leaf.edge = suffix[j + k:]
        leaf.suffix_index = suffix_index
        if leaf.edge:
            split.children[leaf.edge[0]] = leaf
        else:
            # The suffix ended exactly at the split point — this shouldn't happen
            # if the sentinel '$' is present, but guard anyway.
            pass
        return
 
 
def search_naive(root: SuffixTreeNode, P: str) -> list[int]:
    """
    Find all occurrences of P in S by walking the suffix tree.
    Returns the list of starting positions.
    """
    node = root
    j = 0
    while j < len(P):
        c = P[j]
        if c not in node.children:
            return []
        child = node.children[c]
        edge = child.edge
        k = 0
        while k < len(edge) and j < len(P):
            if edge[k] != P[j]:
                return []
            k += 1
            j += 1
    # Collect all leaf suffix_indices in subtree rooted at 'child'.
    return _collect_leaves(node if j == 0 else child)
 
 
def _collect_leaves(node: SuffixTreeNode) -> list[int]:
    if node.suffix_index >= 0:
        return [node.suffix_index]
    out: list[int] = []
    for ch in node.children.values():
        out.extend(_collect_leaves(ch))
    return out
 
 
# Sanity test
if __name__ == "__main__":
    tree = build_suffix_tree_naive("banana")
    occurrences = sorted(search_naive(tree, "ana"))
    assert occurrences == [1, 3], occurrences
    print("ok")

The naive version is O(n²) because each suffix insertion can walk up to n characters. Ukkonen’s O(n) algorithm avoids this by maintaining an active point (active node, active edge, active length) and using suffix links to amortize work — but the implementation is too long to fit here. The standard reference is the Stanford CS166 lecture notes or cp-algorithms.com Ukkonen page.

10. Complexity — Detailed Analysis

10.1 Construction

Algorithm	Time	Space	Year
Naive (insert each suffix)	O(n²)	O(n)	—
Weiner	`O(n	Σ	)`
McCreight	`O(n	Σ	)`
Ukkonen	`O(n	Σ	)(constant Σ:O(n)`)
Farach (large alphabet)	O(n)	O(n)	1997

For modern interviews, “Ukkonen 1995, O(n)” is the canonical answer.

10.2 Query Times

Query	Suffix tree	Notes
Exact pattern matching P,	P	=m
Longest repeated substring	O(n)	Single DFS
Longest common substring of 2 strings	O(n₁ + n₂)	Generalized tree
Longest common substring of k strings	O(N) where `N = Σ	Sᵢ
Distinct substring count	O(n)	Sum of edge lengths
LCA between 2 suffixes	O(1) after O(n) preprocessing	Tarjan or Schieber-Vishkin
Substring at position i, length m	O(1) after O(n) preprocessing (with weighted ancestor)	Less common

10.3 Space

Naive: O(n) nodes, but each node has up to |Σ| children pointers — total O(n · |Σ|) if using arrays of children. With hash maps or balanced BSTs for children: O(n) total space, O(log |Σ|) child lookup.

In production, suffix trees use ~20n bytes typically (4-byte integer indices, 4-byte child pointers, suffix link, 1 internal node per leaf on average).

11. Diagram — Suffix Tree of "banana$"

flowchart TD
    R[("root")]
    R -->|"a"| A["int a"]
    R -->|"$"| D["leaf 6: $"]
    R -->|"na"| N["int na"]
    R -->|"banana$"| B["leaf 0: banana$"]

    A -->|"$"| A1["leaf 5: a$"]
    A -->|"na"| AN["int ana"]

    AN -->|"na$"| AN1["leaf 1: anana$"]
    AN -->|"$"| AN2["leaf 3: ana$"]

    N -->|"na$"| N1["leaf 2: nana$"]
    N -->|"$"| N2["leaf 4: na$"]

    style R fill:#fed
    style A fill:#fea
    style N fill:#fea
    style AN fill:#bfb

What this diagram shows. The full suffix tree of "banana$". The root has four children, one per distinct first-character of any suffix: a (matches suffixes starting with a), $ (the sentinel-only suffix), n (matches suffixes starting with n), and b (the unique suffix starting with b). The internal nodes are branching points — they exist precisely where two or more suffixes share a common prefix. The deepest internal node is the green one with path label "ana" — this is the longest repeated substring of "banana", found by walking the tree once. Each leaf’s label i is the starting position in the original string; e.g., leaf 1 corresponds to the suffix starting at position 1 ("anana$"). Edge labels are stored implicitly as (start, end) index pairs into the original string — the figure shows them as substrings for readability, but in memory they’re just two integers each. The four root-level edges and four internal nodes of varying depth illustrate how the tree’s topology reflects the string’s repetitive structure: the more repetition, the more branching nodes near the top.

12. Pitfalls

1. Forgetting the sentinel. Without $ (or some unique terminator), suffixes that are prefixes of longer suffixes don’t get explicit leaves, breaking many queries. Always append a sentinel.
2. Naive O(n²) build masquerading as suffix tree. The naive algorithm inserts each suffix in O(n) time, giving O(n²) total. This is correct but defeats the purpose. Ukkonen’s O(n) is the canonical algorithm.
3. Confusing implicit and explicit suffix trees. During Ukkonen’s construction, the algorithm maintains an implicit suffix tree where some suffixes terminate inside edges. After processing the sentinel, all terminations are made explicit. Querying the implicit tree gives wrong answers for some short patterns.
4. Misunderstanding suffix links. The suffix link from node v (path label xα) points to node w (path label α) — not the parent of v in the suffix tree, and not the parent in any “suffix” relation. The link is purely a construction-time optimization; querying never needs them.
5. Confusing suffix tree and suffix array. They are different data structures. Suffix tree = compressed trie of suffixes (tree). Suffix array = sorted permutation of suffix start-indices (array). The suffix array is built from the suffix tree by an in-order DFS that emits leaf suffix-indices in sorted order — but not vice versa. Modern systems usually prefer suffix array for the constant-factor space win.
6. Implementing suffix tree edges as concrete strings. Each edge label is a substring of S; storing it as a copy of the substring uses O(n) space per edge, total O(n²) — defeating the linear-space property. Edges must be stored as (start, end) index pairs into S.
7. Off-by-one in the active-point semantics. Ukkonen’s (active_node, active_edge, active_length) triple is notoriously tricky to maintain correctly. Active edge is an index into S (the character that determines which edge to traverse from active node), not a pointer to an edge object. Active length is how far into that edge we have descended.
8. Not handling the alphabet’s size assumption. Many references say “Ukkonen is O(n)” without qualification; strictly it’s O(n |Σ|) or O(n log |Σ|) depending on child-lookup data structure. For DNA (|Σ| = 4) or ASCII (|Σ| = 128), it’s effectively O(n). For Unicode or large integer alphabets, the log factor matters.
9. Confusing “longest repeated substring” with “longest substring that appears at least k times.” The deepest internal node gives the longest substring appearing ≥ 2 times. To find the longest substring appearing ≥ k times, find the deepest node whose subtree has at least k leaves.
10. Believing suffix trees are obsolete. They are largely superseded by suffix arrays for production use, but several stringology problems (longest common substring of k strings via colored DFS, weighted ancestor queries) are still cleanest on suffix trees. They remain the central pedagogical data structure for stringology.

13. Common Interview Problems

Problem	Source	Suffix-tree technique
Longest Repeated Substring	Classic	Find deepest internal node — O(n)
Longest Common Substring (2 strings)	LeetCode 1143-flavor	Generalized suffix tree of S#T$, deepest “two-color” node
Longest Common Substring (k strings)	Classic stringology	k-color DFS, deepest “all-color” node — O(N)
All Occurrences of P in S	Practical	Suffix-tree walk — `O(
Distinct Substring Count	Classic	Sum of edge lengths — O(n)
Find a substring that occurs at least k times	Classic	Find deepest node with ≥ k leaves in subtree
Build BWT (Burrows-Wheeler Transform)	Bioinformatics	BWT can be derived from suffix array, which is derivable from suffix tree
Aho-Corasick equivalent (multi-pattern matching)	Classical	Generalized suffix tree of all patterns; usually Aho-Corasick preferred for online
Repeated Substring of Length ≥ k	Variant	Tree DFS counting depth
Number of distinct substrings of every prefix	Online	Ukkonen’s natural output as it processes characters left-to-right

14. Open Questions

• Is there a simple O(n) suffix-tree construction algorithm? Ukkonen, McCreight, and Weiner are all intricate. Farach’s is O(n) for arbitrary alphabets but also intricate. A truly elegant O(n) algorithm, comparable in simplicity to Suffix Array DC3, has not emerged.
• Can suffix trees be efficiently maintained under string updates? Inserting a character at the end is supported by Ukkonen’s online construction. Inserting in the middle, deletion, or substring replacement are all hard — the fully dynamic suffix tree is an open research problem.
• How does the suffix tree compare to the suffix automaton (Suffix Automaton) for various queries? The suffix automaton is more space-efficient for some queries (smallest representation of all distinct substrings) but the suffix tree has better worst-case bounds for others (depth-based queries).
• What is the gap between O(n) Ukkonen and Õ(n) BWT-based representations like FM-index? The FM-index is much more space-efficient (~n log |Σ| bits) and supports counting and pattern-locating queries; it has largely replaced suffix trees in genomic applications.
• Suffix tree generalizations to trees (not strings) — the generalized suffix tree of a tree — exist and are used in XML/JSON path indexing. Their construction is O(n log n) to O(n α(n)) depending on alphabet (Cole-Hariharan 2000); a true O(n) algorithm is open.

15. See Also

• Suffix Array — sibling data structure; ~3–5× more memory-efficient, slightly slower for some queries
• Trie — uncompressed version; suffix tree is a compressed trie of suffixes
• Compressed Trie — the general compression technique applied to any trie
• Suffix Automaton — alternative substring-indexing structure, even more compressed
• Knuth-Morris-Pratt — single-pattern matching in O(n + m) without preprocessing for repeated queries
• Aho-Corasick — multi-pattern matching extension of KMP; comparable to generalized suffix tree
• Z-Algorithm — O(n) string preprocessing for pattern matching, simpler than suffix tree
• Manacher’s Algorithm — Θ(n) longest palindromic substring directly without suffix tree
• Rabin-Karp — randomized substring search via rolling hash
• String Hashing — hash-based substring equivalence, often combined with suffix arrays
• Lowest Common Ancestor — used inside suffix tree for O(1) LCP queries
• Big-O Notation
• SWE Interview Preparation MOC