Suffix tree (conceptual): Visual walkthrough — Coding deep dive

Step 0 — What is a string, a substring, and a suffix?

WHAT we set up: the raw material. WHY: every substring of $S$ is the front part of some tail. If you want nan, look at the tail nana and read its first three letters. So if we store all the tails, we secretly store all the substrings. PICTURE: the marker swipe (substring) sitting inside the tail (suffix) that contains it.

The symbol $n$ from here on means ==the length of $S$ == (number of letters). For banana, $n = 6$ .

Step 1 — List every suffix

start index $i$	suffix $S [i .. end]$
0	`banana`
1	`anana`
2	`nana`
3	`ana`
4	`na`
5	`a`

WHAT we did: wrote out all $n = 6$ tails, each tagged by where it starts. WHY: these are the "puzzle pieces." Because every substring is the head of one of these, a structure that holds all six tails can answer any "is X inside banana?" question. PICTURE: a staircase — each step drops the front letter and shifts left.

The number tag $i$ (the start index) is important: later, a tag hanging off the tree tells us where in banana a match begins.

Step 2 — Why the raw tails need a terminal `$`

WHAT we did: turned banana into banana$ (now length $n + 1 = 7$ ). WHY: look at two tails — a and ana. The tail a is the front of the tail ana. If we build a tree without $, the short tail a would stop in the middle of a path instead of at its own endpoint, and we could not tag it. Adding $ makes each tail end in a symbol no other tail shares at that spot, so every tail gets its own private endpoint — exactly $n + 1$ of them.

PICTURE: left, a buried inside ana (no clean stop). Right, a$ and ana$ now split apart the moment their letters differ.

Step 3 — Insert the tails into a trie (one letter per edge)

WHAT we did: dropped all 7 tails of banana$ into one trie, letter by letter. The tails ana$ and anana$ both begin a-n-a, so they travel the same three edges, then split. WHY: sharing common heads is the entire trick — it turns "scan every tail" into "walk once." Searching a pattern $P$ becomes: follow $P$ 's letters from the root. PICTURE: the branching trie. Notice the long single-file chains where nothing branches (e.g. down the b-a-n-a-n-a-$ path — no choices at all).

The trouble is visible in the picture: those single-file chains have a node per letter. In the worst case a trie of all tails has $\approx \frac{n ^{2}}{2}$ nodes — the parent's $O (n^{2})$ warning. Step 4 fixes exactly this.

Step 4 — Compress every single-child chain

WHAT we did: took every "no-choice" chain from the trie and squeezed it into one fat edge. The chain n → a → n → a → $ becomes a single edge labeled nana$. WHY: a one-child node carries zero information for searching — you never make a decision there. Deleting it costs nothing and shrinks the tree. What survives are only the branching nodes (real forks) and the leaves (tail endpoints). PICTURE: the same tree as Step 4, but chains collapsed to labeled edges. Count the nodes — dramatically fewer.

Step 5 — Store edge labels as index pairs, not text

WHAT we did: replaced each written label with a pair of numbers pointing back into the one copy of banana$ we already keep. WHY: two integers per edge, and there are $O (n)$ edges → $O (n)$ integers total → $O (n)$ space. The text lives in S; the tree just points at it. PICTURE: an edge label nana$ with an arrow showing it is really "look at banana$, positions 2 through 6."

Step 6 — Read answers straight off the tree

WHAT we did: turned three hard string questions into "walk down" or "count leaves" or "find the deepest fork." WHY: a path from the root is a substring — that one law makes every query a walk. PICTURE: the finished tree with the nan walk traced in coral, the three a-leaves circled in mint, and the deepest fork ana starred.

The one-picture summary

Everything at once: banana → tails → trie → compress → index-pair labels → answers.

Recall Feynman: tell the whole walk to a 12-year-old

Take the word banana. Chop off the front letter over and over to get its tails: banana, anana, nana, ana, na, a. Stick a tiny flag $ on the end of the word first, so no tail can hide inside a bigger one — every tail gets its own leaf. Now file all the tails into a tree where tails that start the same walk down the same branch (like ana and anana sharing ana). This first tree has one node per letter — way too many. So we squeeze: wherever the tree walks in a straight line with no choices, we glue that whole run into one edge and write the letters on it. And because writing the letters would waste space, we instead write two numbers that say "look at these positions in the original word." Done! To ask "is nan in here?" you just walk n-a-n. To count how many times something appears, count the leaves hanging below where you stopped. To find the longest piece that repeats, find the deepest fork. The whole magic is one sentence: a path from the root is a substring.

Active Recall

Compressing merges nodes that have how many children?

Exactly one — a "no-choice" node, so deleting it removes no decision.

Index pair for anana$ inside banana$?

(1, 6)

— positions 1 through 6.

Leaves below the walk na in banana$, and their meaning?

2 leaves (indices 2 and 4) → na occurs twice.

Deepest branching node string in banana$?

ana, the longest repeated substring.

The one-sentence law that makes every query a walk?

A path from the root spells a substring of

S

Connections

Parent: Suffix tree (conceptual) — the concepts this page derives visually.
Trie — Step 3's uncompressed starting structure.
Ukkonen's Algorithm — builds this exact tree in $O (n)$ without ever forming the huge trie.
Suffix Array — same information, flatter and smaller in practice.
Longest Common Substring — Step 6's "deepest fork" idea, generalized to two strings.
KMP Algorithm — a leaner single-pattern matcher when you don't need the whole tree.
Burrows-Wheeler Transform — another suffix-based structure, used in compression.

Visual walkthrough — Suffix tree (conceptual)