Suffix Tree, in depth: from suffix tries to Ukkonen's linear-time construction, tested Python, a banana$ trace and the queries it unlocks

From suffix trie to suffix tree

Start with the suffix trie: insert every suffix of a string into a trie. Any substring is a prefix of some suffix, so it is a path from the root, and searching takes O(m). The problem is size. A string of n distinct characters has n(n+1)/2 distinct substrings, and the trie has a node for each.

Two moves fix it. First, compress every chain of single-child nodes into one edge, as in a radix tree. Every internal node now has at least two children. Second, never copy edge labels; store each as a pair of indices (start, end) into the original text. Append a terminator such as $ that occurs nowhere else, so no suffix is a prefix of another and every suffix ends at its own leaf.

Now count. There are exactly n leaves for a text of length n including the terminator. A tree whose internal nodes all branch has fewer internal nodes than leaves, so the whole tree has at most 2n - 1 nodes and as many edges, each stored in constant space. The size is O(n) even though the labels it spells add up to O(n²) characters.

Ukkonen's four ideas

Inserting suffixes one by one into a compressed tree takes O(n²) time, because each insertion walks down from the root. Weiner (1973) and McCreight (1976) gave linear algorithms; Ukkonen (1995) gave the online one used today. It processes the text left to right and, after reading character i, holds the tree of all suffixes of text[0..i]. Four ideas make it linear.

1. Three extension rules. Extending a suffix by the new character either grows a leaf (rule 1), creates a new leaf, possibly splitting an edge to make an internal node (rule 2), or finds the character already there and does nothing (rule 3).
2. Once a leaf, always a leaf. Leaves never stop growing, so give them all a shared end pointer, the global end. Incrementing it applies rule 1 to every leaf at once, in O(1).
3. Rule 3 ends the phase. If suffix s already contains the new character, every shorter suffix does too, so the phase can stop. The suffixes not yet made explicit are counted in remainder and carried to the next phase. The position where the next insertion happens is the active point: a node, the first character of an edge out of it, and a length along that edge.
4. Suffix links and skip/count. An internal node for the string xα keeps a link to the node for α. After an insertion at xα, follow the link to reach α without walking from the root. When the active length exceeds an edge, hop to the end of the edge in O(1) by comparing lengths rather than characters.

Each phase does O(1) work plus one step per explicit extension, and every suffix is made explicit only once, so the total is O(n) for a constant alphabet. With hash maps for children the expected cost is linear for any alphabet; sorted child arrays give O(n log σ) and ordered traversal.

A complete implementation

The implementation follows the four ideas directly. Children live in a dictionary keyed by the first character of the edge. Leaves have end = None, meaning the global end, until a final pass freezes them and records which suffix each leaf spells.

class Node:
    __slots__ = ("start", "end", "link", "children", "index")

    def __init__(self, start, end=None):
        self.start = start        # edge into this node is text[start:end]
        self.end = end            # None marks a leaf: its end is the global end
        self.link = None          # suffix link (internal nodes only)
        self.children = {}        # first character of edge -> child
        self.index = -1           # suffix start position, filled in for leaves


def build_suffix_tree(text):
    """Ukkonen's online construction. text must end with a unique terminator."""
    if not text or text[-1] in text[:-1]:
        raise ValueError("text must end with a character that occurs nowhere else")
    root = Node(-1, -1)
    root.link = root
    end = 0                                   # global end shared by every leaf
    active_node, active_edge, active_len = root, 0, 0
    remainder = 0                             # suffixes still waiting to be inserted

    def length(node):
        return (end if node.end is None else node.end) - node.start

    for i, ch in enumerate(text):
        end = i + 1                           # rule 1: every leaf grows, for free
        remainder += 1
        last_internal = None                  # node still waiting for a suffix link
        while remainder:
            if active_len == 0:
                active_edge = i
            nxt = active_node.children.get(text[active_edge])
            if nxt is None:                   # rule 2: new leaf off active_node
                active_node.children[text[active_edge]] = Node(i)
                if last_internal is not None:
                    last_internal.link = active_node
                    last_internal = None
            else:
                if active_len >= length(nxt):  # skip/count: hop whole edges
                    active_edge += length(nxt)
                    active_len -= length(nxt)
                    active_node = nxt
                    continue
                if text[nxt.start + active_len] == ch:   # rule 3: present, end phase
                    if last_internal is not None and active_node is not root:
                        last_internal.link = active_node
                        last_internal = None
                    active_len += 1
                    break
                split = Node(nxt.start, nxt.start + active_len)   # rule 2: split
                split.link = root
                active_node.children[text[active_edge]] = split
                split.children[ch] = Node(i)
                nxt.start += active_len
                split.children[text[nxt.start]] = nxt
                if last_internal is not None:
                    last_internal.link = split
                last_internal = split
            remainder -= 1
            if active_node is root and active_len > 0:
                active_len -= 1
                active_edge = i - remainder + 1
            elif active_node is not root:
                active_node = active_node.link
    # Freeze leaf ends and record which suffix each leaf spells.
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if node is not root and node.end is None:
            node.end = len(text)
        if node is not root:
            depth += node.end - node.start
        if not node.children:
            node.index = len(text) - depth
        for child in node.children.values():
            stack.append((child, depth))
    return root

It was checked against brute force on 3,000 random strings over two- and three-letter alphabets: all leaf indices present, every pattern's occurrence list correct, the longest repeat matching an exhaustive search, and node count at most 2n.

Tracing banana$

Trace banana$ (indices 0 to 6). The table shows the state at the end of each phase, taken from the code above.

Phases 3 to 5 do no structural work at all: the leaves grew through the global end and rule 3 stopped each phase immediately, deferring the suffixes a, an and ana. Phase 6 pays the debt. It splits the edge from the root at depth 3 to create node ana, follows the root rule (drop the first character) to na and splits there, linking ana to na; then does the same for a, linking na to a; and finally adds a leaf for $ at the root. That is exactly the tree in the diagram: three internal nodes, seven leaves.

Queries

Most queries are a walk from the root or a traversal of internal nodes.

def find_locus(root, text, pattern):
    """Walk pattern from the root; return the node at or below its end, or None."""
    node, i = root, 0
    while i < len(pattern):
        child = node.children.get(pattern[i])
        if child is None:
            return None
        label = text[child.start:child.end]
        k = min(len(label), len(pattern) - i)
        if label[:k] != pattern[i:i + k]:
            return None
        i += k
        node = child
    return node


def occurrences(root, text, pattern):
    """Start positions of pattern: the leaves below its locus. O(m + occ)."""
    locus = find_locus(root, text, pattern)
    if locus is None:
        return []
    out, stack = [], [locus]
    while stack:
        node = stack.pop()
        if not node.children:
            out.append(node.index)
        stack.extend(node.children.values())
    return sorted(out)


def longest_repeat(root, text):
    """Deepest internal node = longest substring occurring at least twice."""
    best, stack = (0, 0), [(root, 0)]
    while stack:
        node, depth = stack.pop()
        for child in node.children.values():
            if child.children:
                d = depth + child.end - child.start
                if d > best[0]:
                    best = (d, child.end - d)
                stack.append((child, d))
    return text[best[1]:best[1] + best[0]]


root = build_suffix_tree("banana$")
print(occurrences(root, "banana$", "ana"))   # [1, 3]
print(longest_repeat(root, "banana$"))       # ana

• Substring test: walk the pattern, O(m).
• All occurrences: walk to the locus, then collect the leaves below it, O(m + occ). Store a leaf count per node and counting becomes O(m).
• Longest repeated substring: the internal node with the greatest string depth. See longest repeated substring for the suffix-array route and corpus-scale variants.
• Longest common substring of two strings: build a generalized tree (below) and take the deepest internal node with leaves from both strings, O(n + m). Longest common substring compares methods.
• Distinct substring count: the sum of edge lengths minus one per leaf for its terminator; banana$ gives 22 - 7 = 15.
• Matching statistics: for each position of a query string, the longest prefix that occurs in the text, computed in linear time with suffix links.

Generalized suffix trees

A generalized suffix tree indexes several strings at once. The simplest construction concatenates them with distinct terminators, s1 + '#' + s2 + '$', builds one tree, and labels each leaf with the string its start position falls in. Leaves of s1 spell suffixes that run through # into s2; that is harmless for queries because no pattern contains the terminator, but trim labels at the first terminator when printing. A bottom-up pass computes, for each internal node, the set of strings below it, and most multi-string questions read off those sets.

Memory and alternatives

The O(n) bound hides a large constant. Each node holds two indices, a suffix link, a child structure and often a leaf index, and there are up to 2n nodes. Careful C implementations still spend well over ten bytes per input character; a Python object tree like the one above uses hundreds of bytes per node, so a 100-million-character genome would need tens of gigabytes. A suffix array with an LCP array answers most of the same queries in two integer arrays, and the suffix array deep dive shows how; compressed indexes such as the FM-index go further, to around the size of the compressed text.

Failure modes

• No unique terminator: without it some suffixes end inside an edge, have no leaf, and counts silently come out short. The code above refuses such input.
• Suffix-link mistakes: forgetting to link the last internal node of a phase, or linking it at the wrong time, gives a tree that is correct on small tests and quadratic or wrong on long ones. Test against brute force on thousands of random strings over tiny alphabets, where repeats are dense.
• Recursion depth: string depth can reach n, so recursive traversals overflow on long repetitive inputs; use explicit stacks as above.
• Characters versus bytes: mixing Unicode code points and UTF-8 bytes gives positions that do not line up with the source text.
• Terminator collisions: in generalized trees a terminator that can occur in the data corrupts every result; use values outside the alphabet.
• Memory surprise: a tree that fits for a test corpus can exhaust memory in production. Estimate bytes per character before choosing the structure.

What to do next

1. Draw the suffix tree of mississippi$ by hand, then compare it with the code's output.
2. Run the implementation against a brute-force checker on random strings over a two-letter alphabet.
3. Add a leaf count to every node and turn occurrence counting into O(m).
4. Build a generalized tree for two strings and extract their longest common substring.
5. Measure memory per input character for your implementation on real data.
6. Rebuild the same queries on a suffix array with LCP and compare speed and space.