Suffix tree (conceptual): Worked examples — Coding deep dive

This page is the "put it into your hands" companion to Suffix tree (conceptual). We walk every kind of question a suffix tree can face — from a normal substring search to the weird degenerate cases (empty pattern, single repeated letter, pattern that ends inside an edge) — and solve each one fully.

The scenario matrix

Every question a suffix tree throws at you falls into one of these case classes. Our job is to hit every row.

#	Case class	What makes it tricky	Covered by
A	Pattern present, ends at a node	clean walk, stop on a branching point	Ex 1
B	Pattern present, ends inside an edge	you stop mid-label, not at a node	Ex 2, Ex 2b
C	Pattern absent — mismatch mid-edge	wrong letter inside a compressed edge	Ex 3
D	Pattern absent — no matching edge at a node	no child starts with the next letter	Ex 3
E	Counting occurrences (leaves below)	must count subtree leaves, not stop point	Ex 4
F	Degenerate: empty pattern / single char	zero-length, whole-alphabet answers	Ex 5
G	Degenerate: all-same string `aaaa$`	maximal sharing, deepest-chain repeats	Ex 6
H	Limiting: longest repeated substring	deepest internal node by char depth	Ex 7
I	Real-world word problem	DNA / log search framing	Ex 8
J	Exam twist: why the `$` changes leaf count	reasoning, not walking	Ex 9

Here is the tree we will read from for banana$. Study it before the examples — everything below "looks at" this picture.

Ex 1 — Case A: pattern present, ends at a node

Worked example Is

ana a substring of banana? Where does the walk stop? Forecast: guess now — does the walk end at a node or inside an edge, and how many times does ana occur?

Step 1. Start at the root. The next letter of $P$ is a. Find the child edge that starts with a. Why this step? By Rule 4 (edges out of a node start with distinct characters), at most one edge can match — the walk is deterministic.

Step 2. That edge is labeled a. Consume it → we are now at the internal node reached by a. Pattern remaining: na. Why this step? We spend pattern letters against edge letters, one region at a time.

Step 3. From that node, the next letter is n. Take the edge starting n, labeled na. Consume na. Pattern is now empty and we land exactly on an internal node. Why this step? When the pattern runs out and we are sitting on a node, $P$ matched and we stopped at a branch point (case A).

Answer: ana is a substring; the walk ends at the internal node whose root-string (concatenated edge labels from the root) is ana.

Verify: scan banana by eye — b·ana·na at index 1 and ban·ana at index 3. ana appears at indices 1 and 3, and the node ana has exactly 2 leaves below it (indices 1 and 3). Match. ✓

Ex 2 — Case B: pattern present, ends inside an edge

Worked example Is

nan a substring of banana? Where exactly does the walk stop? Forecast: the letters nan — do you finish on a node or halfway along an edge?

Step 1. From root, next letter n. Take the edge starting n; its label is na. Consume n, then a. Pattern remaining: n. We are now at the internal node reached by na. Why this step? We match the compressed label character-by-character.

Step 2. From node na, the next pattern letter is n. The child edge starting n is labeled na (leading to the nana$ leaf). Match the first letter n of that edge — pattern is now empty, but we are inside the edge, one character in. Why this step? The pattern ran out before reaching the next node. That is perfectly valid: we are at a mid-edge position.

Answer: nan is a substring; the walk stops inside the edge na after its first n.

Verify: ba·nan·a — nan sits at index 2. One occurrence. The stopping edge leads down to a single leaf (index 2), consistent with one occurrence. ✓

Ex 2b — Case B at the very first edge (the simplest mid-edge match)

Worked example Is

b a substring of banana? Where does the walk stop? Forecast: does the single letter b land on a node or inside an edge? (This is the canonical Case B at the root.)

Step 1. From the root, the next (and only) letter of $P$ is b. By Rule 4, exactly one edge can start with b: the edge labeled banana$. Why this step? b is unique to one suffix, so the root has just one b-edge — deterministic.

Step 2. Match the first character b of that edge. The pattern is now empty, but we are only one character into a long edge — nowhere near its child node. Why this step? Even at the first edge, a short pattern ends mid-label. This is the simplest possible mid-edge stop.

Answer: b is a substring; the walk stops inside the root edge banana$ after its first character. One leaf (index 0) hangs below → occurs once.

Verify: banana — b sits only at index 0 → 1 occurrence ✓, matching the single leaf below the stopping edge.

Ex 3 — Cases C & D: two ways to be absent

Worked example Are

nax and bx substrings of banana? Forecast: for each, will you fail because no child edge exists at a node (Case D), or because a letter inside a compressed edge disagrees (Case C)?

Part (i) — nax → Case D (no matching child at a node). Step 1. Match n, a down the na edge to node na (as in Ex 2). We arrive cleanly at a node. Step 2. Next letter x. From node na, children start with n (edge na) and $. Neither starts with x. Why this step? We are standing on a node and no child edge begins with the required character → the walk cannot continue. Failure at a node = Case D. Answer (i): nax is NOT a substring — Case D (no matching child at a node).

Part (ii) — bx → Case C (mismatch strictly inside a compressed edge). Step 1. From root, the letter b selects the edge labeled banana$ (b is unique to one suffix). Step 2. Consume b (position 1 inside that edge). Next pattern letter is x, but the edge's next stored character is a. x ≠ a. Why this step? A mismatch inside a compressed label kills the match immediately — you never reach a node. Failure mid-edge = Case C. Answer (ii): bx is NOT a substring — Case C (mismatch mid-edge).

Verify: banana contains no x at all, so both must fail. ✓ The two failures differ in where: nax fails standing on a node (D), bx fails halfway inside an edge (C).

Ex 4 — Case E: counting occurrences

Worked example How many times does

a occur in banana? And na? Forecast: guess the two counts before reading.

Step 1 — match a. From the root take the edge labeled a; consume its single character. The pattern a is now exhausted exactly as we arrive at the internal node a — this is a clean Case-A stop on a node, not a mid-edge position. Why this step? Reaching depth $∣ P ∣$ means $P$ matched; here the label a is length 1, so the match point lands precisely on the node. The count now lives in the subtree below.

Step 2 — count leaves in the subtree. Below node a hang the leaves for suffixes a(5), ana(3), anana(1). That is 3 leaves. Why this step? Each leaf below the stop point = one suffix that starts with $P$ = one occurrence of $P$ . Answer: a occurs 3 times.

Step 3 — match na. Take edge na from the root, consuming both characters; the pattern ends exactly at the internal node na. Below it: leaves for na(4) and nana(2) → 2 leaves. Answer: na occurs 2 times.

Verify: b a n a n a — the letter a sits at indices 1, 3, 5 → 3 times ✓. na at indices 2, 4 → 2 times ✓. Counting formula = leaves below match. ✓

Ex 5 — Case F: degenerate patterns (empty and single char)

Worked example What does the tree answer for

$P =$ "" (empty) and $P =$ z (a letter not in $S$ )? Forecast: how many occurrences of the empty string? Of a missing letter?

Step 1 — empty pattern. With zero letters to match, we never leave the root. We are "in the tree" at depth 0. Why this step? The walk consumes $∣ P ∣ = 0$ characters, so it trivially succeeds at the root. Occurrences: count all leaves below the root = every suffix = == $n + 1 = 7$ == positions. The empty string sits before every character, at all $n + 1$ = 7 places (indices 0..6 including the $-only suffix).

Step 2 — missing letter z. From root, no child edge starts with z. Why this step? Failure at the very first step (Case D at the root). Answer: z occurs 0 times — not a substring.

Verify: empty string is a prefix of all 7 suffixes → 7 leaves ✓. z ∉ banana$ → 0 ✓.

Ex 6 — Case G: the all-same string `aaaa`

Worked example Build the shape of the suffix tree for

$S =$ aaaa and count occurrences of aa. How many internal nodes does the tree have? Forecast: how many internal nodes? How many times does aa occur?

Step 0 — append the terminal. As stated in our opening definition, a proper suffix tree is built on $S\$$, so we work with$ S$ = $‘ aaaa$ . Here $n = |S| = 4$. *Why this step?* Without $‘, e v er y s h or t a l l - ‘ a ‘ s u f f i x w o u l d hi d e in s i d e a l o n g er o n e; t h e ‘$ ` forces each its own leaf.

Step 1 — list suffixes of aaaa$: aaaa$, aaa$, aa$, a$, $ (5 suffixes, indices 0–4, so $n + 1 = 5$ leaves). Why this step? Suffixes are the raw material; maximal sharing means maximal compression stress-test.

Step 2 — every non-$ suffix starts with a. So from the root there is one shared chain that branches every time a $ can peel off. The internal (branching) nodes are exactly the root-strings a, aa, aaa — at each one, either a $ terminates here or another a continues, giving ≥ 2 children. Why this step? Branching happens exactly where suffixes stop agreeing — here each extra a is a branch point because one suffix can terminate ($) while others continue with another a. Internal-node count: the branching nodes are a, aa, aaa ⇒ 3 internal nodes (the root is not counted among them). This matches the bound "≤ $n - 1$ non-root internal nodes" for $n = 4$ .

Step 3 — count aa. Match a, a from the root, ending exactly at node aa. Below it hang the suffixes that start with aa: aa$(2), aaa$(1), aaaa$(0) → 3 leaves. Answer: aa occurs 3 times; the tree has a spine of 3 internal nodes (a, aa, aaa) plus 5 leaves.

Verify: in aaaa, aa sits at indices 0,1,2 → 3 occurrences ✓. Leaves $= n + 1 = 5$ ✓; internal branching nodes $= 3$ ✓. This is the maximal-repeat extreme; note the $ is what stops it collapsing into one infinite edge.

Ex 7 — Case H: longest repeated substring (limiting query)

Worked example Find the longest repeated substring of

banana. Forecast: which string repeats and is as long as possible?

Step 1 — repeated ⇒ branching internal node. A substring repeats $\geq 2$ times iff its root-string ends at an internal (branching) node — because $\geq 2$ leaves hang below it. Why this step? By Rule 2, an internal node has $\geq 2$ children ⇒ $\geq 2$ different continuations ⇒ $\geq 2$ occurrences.

Step 2 — longest ⇒ deepest by character depth. Among internal nodes, compute character depth (total root-string length root→node):

node a → depth 1
node na → depth 2
node ana → depth 3 ← deepest

Why this step? We want the most letters, so we maximise character depth (not node count). Answer: longest repeated substring = ==ana==, length 3, occurring at indices 1 and 3.

Verify: banana — ana appears at index 1 (b**ana**na) and index 3 (ban**ana**) → repeats ✓. No length-4 substring repeats (check anan occurs only at index 1). ✓

Ex 8 — Case I: real-world word problem

Worked example A DNA scanner stores the read

$S =$ ACGTACG in a suffix tree. A lab asks: "does the motif GTA appear, and how many times does ACG appear?" Forecast: guess both answers.

Step 1 — motif GTA. Walk from root: G → T → A. Each step must find a matching edge/character. Why this step? Substring query = walk; cost $O (∣ P ∣) = O (3)$ , independent of read length $n = 7$ . Reading ACGTACG: AC**GTA**CG — GTA sits at index 3. The walk succeeds. GTA is present.

Step 2 — count ACG. Match A,C,G then count leaves below. Suffixes starting with ACG: ACGTACG(0) and ACG(4) → 2 leaves. Why this step? Occurrences = leaves below match point. Answer: ACG occurs 2 times (indices 0 and 4).

Verify: ACGTACG — ACG at index 0 (**ACG**TACG) and index 4 (ACGT**ACG**) → 2 ✓. GTA at index 3 → present ✓. Units check: answer is a count (dimensionless), and $2 \leq n = 7$ suffixes. ✓

Ex 9 — Case J: exam twist (reason, don't walk)

Worked example Someone builds the tree for

abab without the $. How many leaves does it have, and what breaks? Forecast: should it be 4 leaves? Fewer?

Step 1 — list suffixes of abab (here $n = ∣ S ∣ = 4$ ): abab, bab, ab, b (indices 0–3). Why this step? We test the rule "one leaf per suffix" against a self-nested case.

Step 2 — spot the nesting. ab is a prefix of abab; b is a prefix of bab. So the suffix ab ends inside the edge spelling abab, and b ends inside bab — they do NOT get their own leaves. Why this step? Without a unique terminator, a shorter suffix can hide inside a longer one, violating "each suffix at its own leaf."

Step 3 — add $ → abab$. Now suffixes are abab$, bab$, ab$, b$, $ (5 of them). The $ is unique, so no suffix is a prefix of another; each ends at its own leaf → exactly $n + 1 = 5$ leaves. Answer: without $, abab gives fewer than 4 true leaves (2 suffixes hide inside edges); with $, abab$ gives exactly 5 leaves.

Verify: $n = 4$ for abab; with $, leaves $= n + 1 = 5$ ✓. This is precisely why the parent note insists on the terminal symbol.

Recall Self-test on the matrix

Which case class does each hit? nan in banana ::: Case B — present, ends inside an edge. b in banana ::: Case B — present, ends inside the very first (root) edge. bx in banana ::: Case C — mismatch strictly inside a compressed edge. nax in banana ::: Case D — no matching child while standing on a node. Occurrences of empty string in a length- $n$ string ::: Case F — degenerate, answer $n + 1$ . Longest repeated substring of banana ::: Case H — ana, deepest internal node, depth 3. Leaves of the tree for abab$ ::: Case J — exactly 5 ( $n + 1$ ). What is $n$ ? ::: The length of the original string $S$ (before the $ is appended).

Connections

Suffix tree (conceptual) — the parent concept these examples exercise.
Trie — where the uncompressed walk logic comes from.
Suffix Array — same queries with less memory; occurrences become a range.
Ukkonen's Algorithm — how the tree we read from is built in $O (n)$ .
Longest Common Substring — extends Ex 7 to two strings.