Introduction

If the original suffix tree is built for S[1..m]$ with a unique terminal symbol, then the suffix tree for S[2..m]$ is much simpler than it first appears. You do not need to rebuild every suffix from scratch, because the new suffix set is exactly the old suffix set with the first suffix removed.

The Key Observation

The suffixes of S[1..m]$ are:

• 'S[1..m]$'
• 'S[2..m]$'
• 'S[3..m]$'
• and so on

The suffixes of S[2..m]$ are exactly the same list except for the first one. Therefore, if your suffix tree stores all suffixes of S[1..m]$, the new tree is obtained by deleting the leaf for suffix S[1..m]$ and then compressing any internal node that becomes unary.

That is the whole structural change.

Why This Works

A suffix tree is a compressed trie of all suffixes. Removing one suffix means:

1. delete the leaf for that suffix
2. walk back toward the root
3. if an internal node now has only one child, merge its incident edges
4. stop once you reach a node that still has at least two children, or the root

No other suffix changes. The edge labels for the remaining suffixes are still valid because they still point into the same original text.

This is why the transformation is linear in the worst case and often much smaller in practice. You only touch the path that belonged uniquely to the removed suffix.

Small Example

Take banana$. Its suffixes are:

1banana$
2anana$
3nana$
4ana$
5na$
6a$
7$

Now drop the first character of the text. The new string is anana$, whose suffixes are:

1anana$
2nana$
3ana$
4na$
5a$
6$

That is exactly the original suffix set without banana$. So the new suffix tree is the old one with the banana$ leaf removed and any resulting one-child path compressed.

A Runnable Illustration

The following Python example uses a plain suffix trie to demonstrate the deletion idea. A production suffix tree uses compressed edges, but the pruning logic is the same.

1class Node:
2    def __init__(self):
3        self.children = {}
4        self.terminal = False
5
6
7def insert_suffix(root, suffix):
8    node = root
9    for ch in suffix:
10        node = node.children.setdefault(ch, Node())
11    node.terminal = True
12
13
14def build_suffix_trie(text):
15    root = Node()
16    for i in range(len(text)):
17        insert_suffix(root, text[i:])
18    return root
19
20
21def delete_suffix(node, suffix, index=0):
22    if index == len(suffix):
23        node.terminal = False
24    else:
25        ch = suffix[index]
26        child = node.children[ch]
27        should_delete = delete_suffix(child, suffix, index + 1)
28        if should_delete:
29            del node.children[ch]
30    return not node.terminal and not node.children
31
32text = "banana$"
33root = build_suffix_trie(text)
34delete_suffix(root, text)
35print("removed first suffix")

In a compressed suffix tree, after deleting the leaf you would additionally compress unary internal nodes by joining edge labels.

Complexity Discussion

If the tree is stored explicitly, the update costs O(length of removed suffix) in the worst case because only one root-to-leaf path can be affected. Since the removed suffix has length m, the bound is O(m).

This is already optimal for explicit tree editing because the changed path itself may be linear in size.

Connection to Suffix Links

Suffix links are useful for online construction algorithms such as Ukkonen’s method, but you do not need them for this particular transformation. The new tree is not a mysterious new combinatorial object; it is the old tree minus one suffix path, followed by compression.

That distinction matters because it keeps the update logic simple.

Common Pitfalls

The biggest mistake is thinking every remaining suffix label must be rewritten because the string now starts one position later. If edge labels are stored as references into the original text, the substrings remain valid.

Another issue is forgetting the unique terminal symbol. Without it, suffix-tree reasoning becomes ambiguous because one suffix can be a prefix of another.

A third mistake is deleting the leaf but not compressing unary internal nodes, which leaves you with a trie-like structure rather than a proper compressed suffix tree.

Summary

• The suffixes of S[2..m]$ are the suffixes of S[1..m]$ minus the first suffix.
• Delete the leaf for S[1..m]$, then compress any unary internal nodes.
• Only one root-to-leaf path can change.
• The update is O(m) in the worst case and does not require rebuilding the whole tree.
• A unique terminal symbol is essential for the standard suffix-tree argument.