Every suffix in one structure
A suffix tree is a tree that contains every suffix of a string as a path from the root to a leaf. Because many suffixes share beginnings, those shared starts collapse into common branches, so the tree stays compact rather than storing each suffix separately.
Compressed paths
A naive tree of all suffixes would have long thin chains. A suffix tree fixes this by compressing each chain of single child edges into one edge labeled with a range of the text. Each internal node then has at least two children, which keeps the total number of nodes proportional to the text length.
- Each leaf marks where one suffix ends.
- Each edge label is stored as positions in the text, not copied characters.
- A special end marker ensures every suffix ends at its own leaf.
What it unlocks
Once built, the tree answers many questions quickly:
- Does a pattern occur? Walk it down from the root.
- How many times does it occur? Count the leaves below.
- What is the longest repeated substring? Find the deepest internal node.
Clever constructions build the whole tree in time linear in the text length, which is what makes the structure practical.
Key idea
Collapse all suffixes into one compressed tree with edges labeled by text positions, so pattern and repeat queries are walks from the root.