Intuition The one core ideaA suffix tree is a single tree that secretly stores every possible piece (substring) of a word, so that "is this little piece hiding inside?" becomes a short walk down from the top. To read the parent note you only need to trust one fact — a substring is always the beginning of some tail (suffix) of the word — and understand the handful of symbols we build below, one at a time.
This page assumes you have seen nothing . We introduce each symbol, draw its picture, and say why the topic can't live without it. Read top to bottom — every item leans on the one before it.
A string is just a row of characters written left to right, like beads on a wire.
We name the whole row with a single capital letter, usually S S tring).
Example: S = banana.
Think of a row of boxes, one letter per box. The boxes have addresses printed underneath.
Look at the figure below — that row of boxes is the string S
Why the topic needs it: the whole suffix tree is built out of pieces of this one row S S
i index is the position number of a character, counting from 0 at the far left.
So in banana: the b is at index 0 a at index 1
Common mistake Off-by-one trapWhy it feels wrong: humans count "1, 2, 3…", so the first letter feels like position 1.
The fix: in these algorithms we count "0, 1, 2…". The first letter is index 0
We write S [ i ] i S [ 3 ] = a.
n length n S banana, n = 6 0 , 1 , 2 , … , n − 1 0 5
A substring is a run of characters that sit next to each other in S S [ i .. j ] i j
Put two brackets around a stretch of the box row. Everything between the brackets, with no boxes skipped, is a substring. The red bracket in the figure below highlights S [ 2..4 ] = nan.
Common mistake Substring vs subsequenceWhy confused: both words start with "sub".
The fix: a substring is contiguous (nan from banana — the boxes touch). A subsequence may skip boxes (bnn is a subsequence but not a substring). The suffix tree is about substrings — contiguous chunks only.
Why the topic needs it: the entire purpose of a suffix tree is to answer questions about substrings ("does nan occur?"). This is the object we hunt.
A prefix is a substring that begins at the very start (index 0 banana: b, ba, ban, bana, banan, banana.
A prefix is what you get by covering the word with your hand from the right and reading what's still visible on the left . See the sliding hand in the figure.
Why the topic needs it: the parent's key claim — "a substring is a prefix of some suffix" — uses this word. We define suffix next, then glue the two ideas together.
A suffix is a substring that runs all the way to the end of the word.
You make a suffix by chopping letters off the front .
For S = banana, the suffixes are the "tails":
start index
suffix
0
banana
1
anana
2
nana
3
ana
4
na
5
a
Cover the word with your hand from the left this time, and read what remains on the right . Each stopping point of your hand gives one suffix. The figure shows the hand sliding rightward, exposing shorter and shorter tails.
Why the topic needs it: the suffix tree is literally the tree of all these tails. There are exactly n n n
Intuition The single most important sentenceTake any substring — say nan. It sits somewhere in the middle. Slide left until its start touches the front-cut: nan is the front part (prefix) of the tail nana (the suffix starting at index 2 every substring is the beginning of some tail.
Why the topic needs it: this is why a tree of suffixes can answer substring questions. If you store all tails and can walk their front-parts, you can find any chunk. Everything the parent note does rests on this line.
The alphabet is the set of allowed characters. For banana it is { a,b,n}
Definition Terminal symbol$
The terminal symbol $ is a special extra character that is not in the alphabet and appears only once , glued to the very end: banana$.
Why it exists: without it, one tail can be the front of another (a is the front of ana), so it would end inside the tree rather than at its own leaf. The $ is a unique flag that gives every tail its own private ending.
Picture a tiny flag stuck on the last box. Because no other box carries that flag, no tail can accidentally hide inside another tail. The figure in the tree section (below) shows why.
Why the topic needs it: it guarantees "exactly n + 1
Definition The tree vocabulary
Root ::: the single top box where every walk begins.Node ::: any junction box in the tree.Edge ::: a link between two nodes; in a suffix tree it carries a label (a substring).Leaf ::: a bottom node with no children — a dead end.Internal node ::: a node that is not a leaf and not… well, it can be the root; a branching internal node has ≥ 2 Path ::: the trail of edges from the root down to some node; reading its edge-labels in order spells a string.
Intuition The one rule that makes walking possibleOut of any node, no two edges start with the same character . So when you're spelling a pattern and the next letter is n, there is at most one edge you could take — the walk is never ambiguous. That is what makes searching a simple, deterministic stroll.
Why the topic needs it: "a path is a substring" is the punchline of the whole structure. The tree is a machine where walking down = spelling a substring .
Definition Index-pair labelInstead of writing the actual letters on an edge (which wastes space), we store two integers ( i , j ) S [ i .. j ] point at them inside S
Common mistake "Copying labels makes itO ( n 2 ) Why it feels right: the labels look like text (anana$), and adding up all those text lengths really is n 2 The fix: we never copy. Two integers per edge × O ( n ) = O ( n )
Why the topic needs it: this trick is the entire reason a suffix tree fits in O ( n )
O ( f ( n )) no faster than f ( n )
O ( n ) linear , cheap.O ( n 2 ) squared — expensive; doubling the input quadruples the work.O ( ∣ P ∣ ) ∣ P ∣ not on n
Two runners: the O ( n ) O ( n 2 )
Why the topic needs it: every payoff in the parent ("build O ( n ) O ( ∣ P ∣ ) ∣ P ∣ P ∣ ⋅ ∣
String S as a row of boxes
Bridge substring is prefix of a suffix
Tree words root node edge leaf path
Edge label as index pair i j
Read it as: rows of boxes give indices and length; indices carve out substrings; substrings specialise into prefixes and suffixes; the bridge fuses them; and the tree machinery plus the growth ruler turn it into the finished suffix tree.
Cover the right side and answer aloud before revealing.
In banana, what character is S [ 3 ] a (0-based: b=0, a=1, n=2, a=3).
What is n banana? 6 0 5
Is bnn a substring of banana? No — it skips boxes, so it's a subsequence, not a contiguous substring.
Write the substring S [ 2..4 ] banana. nan.
How many suffixes does a length-n Exactly n 0 … n − 1
Complete the bridge: a substring is a ____ of some ____. a prefix of some suffix .
Why glue a $ to the end? So no tail is the front of another tail; each suffix then ends at its own private leaf.
What does an edge label ( i , j ) The substring S [ i .. j ]
Why is the tree O ( n ) O ( n 2 ) Edges store two integers each, not copied text; O ( n ) × = O ( n )
What does O ( ∣ P ∣ ) It depends only on the pattern's length, not on the size n
Out of one node, can two edges start with the same character? No — distinct starting characters make the downward walk unambiguous.
Suffix tree (conceptual) (index 3.8.8) — the parent this page equips you for.Trie — the uncompressed tree these symbols first build.Suffix Array — the same suffix information stored as a sorted list.Ukkonen's Algorithm — the linear-time way to actually construct the tree.KMP Algorithm — another matcher that also cares about prefixes and suffixes.Longest Common Substring — a payoff built on these foundations.Burrows-Wheeler Transform — a cousin structure using the same suffixes. 
