Suffix tree (conceptual): Question bank — Coding deep dive

This bank sharpens your model of the suffix tree: what its rules actually guarantee, where beginners slip, and what happens at the weird edges (empty string, one letter, repeated letters, the $ marker).

True or false — justify

Every "answer" below is a reason, never a bare yes/no.

TF1. Every internal node (except the root) has at least two children.

True. That is rule 2 of the definition — internal nodes are branching points; a node with a single child would carry no decision and gets compressed away.

TF2. A suffix tree of a length-

n

string can have more than

2 n + 1

total nodes.

False. With

n + 1

leaves and each internal node having

\geq 2

children, internal nodes

\leq n

, so total

\leq (n + 1) + n = 2 n + 1 = O (n)

TF3. Storing the edge label anana$ costs 6 characters of memory.

False. Labels are stored as an ==index pair

(i, j)

== meaning

S [i .. j]

— just two integers — so the memory is constant per edge regardless of label length.

TF4. Without the $ marker, a suffix tree of banana still has exactly

n

leaves.

False. Without $, a is a prefix of ana, so a ends inside an edge, not at its own leaf — some suffixes hide inside others and you get fewer than

n

leaves.

TF5. Two edges leaving the same node may both start with the letter a.

False. Rule 4 forbids it — distinct first characters keep the walk deterministic, so matching a pattern picks at most one edge per step.

TF6. Every substring of

S

corresponds to some path starting at the root (not necessarily ending at a node).

True. A substring is a prefix of some suffix, and reading a prefix of a suffix means walking part-way down that suffix's root-to-leaf path — you may stop in the middle of an edge.

TF7. Every path from the root to a leaf spells a distinct suffix.

True. The $ marker guarantees each suffix ends at its own leaf, and no suffix equals another, so the

n + 1

leaves label

n + 1

distinct suffixes.

TF8. The number of leaves in the subtree below a matched pattern equals the number of times that pattern occurs.

True. Each leaf is one suffix that starts with

P

, and a suffix starting with

P

is exactly one occurrence of

P

— so leaf count

= occ

TF9. A suffix tree and a suffix trie store the same information.

True. Compression only removes non-branching intermediate nodes; every suffix and every substring is still spelled by exactly one path — no information is lost.

TF10. The deepest leaf (by character depth) tells you the longest repeated substring.

False. You want the deepest internal (branching) node, not the deepest leaf. Branching means

\geq 2

continuations, hence

\geq 2

occurrences; a leaf is a single suffix and need not repeat.

Spot the error

Each line states a flawed claim; the reveal names the flaw.

SE1. "Searching for pattern

P

takes

O (n)

time because the tree has

O (n)

nodes."

The flaw: search cost depends on

P

, not

S

. You read

P

's characters walking down, so it is

O (∣ P ∣)

— independent of

n

SE2. "The suffix tree is

O (n^{2})

because summing all edge-label lengths gives

O (n^{2})

The flaw: labels are never copied as text. Each edge holds two integers

(i, j)

; with

O (n)

edges that is

O (n)

space — the text lives once in

S

SE3. "Every node in the tree has at least two children."

The flaw: the root is exempt (it can have one child, e.g. aaaa$), and leaves have zero children. The "

\geq 2

" rule is only for internal non-root nodes.

SE4. "Because a occurs 3 times in banana, there must be an internal node whose path string is a with 3 children."

The flaw: leaf count, not child count, gives occurrences. The node for a needs enough leaves below it to total 3 — those may sit under further branching, not as 3 direct children.

SE5. "Compression can merge two edges even if they leave the same node."

The flaw: compression only collapses a chain of single-child nodes into one edge. Sibling edges are never merged — they represent different branching choices.

SE6. "To count occurrences of

P

we count the internal nodes below the match."

The flaw: occurrences are counted by leaves below the match point, not internal nodes. Each leaf is one starting position of

P

SE7. "The $ must be an ordinary letter of the alphabet so it fits in existing edges."

The flaw: $ must be a symbol not in the alphabet and unique. If it were an ordinary letter it couldn't force each suffix to a distinct leaf.

SE8. "A suffix tree lets you search any pattern; therefore it stores all substrings explicitly as strings."

The flaw: substrings are stored implicitly as root paths, not explicitly. There are

O (n^{2})

substrings but only

O (n)

nodes — you read them off paths on demand.

Why questions

WQ1. Why is a tree used instead of just a sorted list of suffixes?

Many suffixes share prefixes (ana, anana), and a tree merges those shared beginnings into one path, so matching

P

O (∣ P ∣)

instead of scanning every suffix.

WQ2. Why must every suffix end at a leaf rather than inside an edge?

So that leaf count cleanly equals occurrence count and every suffix has a unique endpoint — the $ marker enforces this by making no suffix a prefix of another.

WQ3. Why does a branching node (not any node) mark a repeated substring?

A branch means the path string has

\geq 2

different next-characters, so that string is followed by two different things, i.e. it appears in at least two places in

S

WQ4. Why store edge labels as index pairs instead of the substrings themselves?

Copying substrings sums to

O (n^{2})

characters; two integers per edge keeps total space at

O (n)

while still pointing into the single stored copy of

S

WQ5. Why is "substring of

S

= prefix of some suffix of

S

" the founding idea?

Any contiguous chunk of

S

begins at some position

i

and is exactly the front of suffix

i

; so a structure holding all suffixes automatically holds all substrings as their prefixes.

WQ6. Why must edges from one node begin with distinct characters?

It makes the walk deterministic — given the next character of

P

, at most one edge can match, so you never branch-search and stay at

O (∣ P ∣)

WQ7. Why can a suffix trie have

O (n^{2})

nodes while the suffix tree has only

O (n)

The trie keeps every single-character step as its own node; the tree compresses non-branching chains, and with

n + 1

leaves the branching structure allows at most

n

internal nodes.

Edge cases

EC1. What does the suffix tree of the empty string (with $) look like?

Just a root and one leaf reached by the edge $ — there is exactly

n + 1 = 1

suffix (the empty suffix, i.e. just $), so a single leaf.

EC2. What is the shape for a single distinct letter repeated, e.g. aaa$?

A skewed tree: the root has one branch on a and one on $; along the a side each further step branches into "more as" versus "$". It is the worst case for depth — the longest repeated substring aa sits at the deepest branching node.

EC3. For a string of all distinct characters, e.g. abcd$, how many internal nodes are there?

Only the root — no two suffixes share a first character, so nothing branches below the root; you get

n + 1

leaves hanging directly off it and zero non-root internal nodes.

EC4. Can the root ever be a leaf?

No — the root is where all suffixes begin; it always has children (unless the string is truly empty of everything, which we don't allow since we always append $).

EC5. If a pattern

P

matches only part-way into an edge and then ends, is

P

still a substring?

Yes — reaching depth

∣ P ∣

anywhere, including mid-edge, means

P

was spelled successfully; you need not land exactly on a node to conclude

P

occurs.

EC6. What happens if

P

is longer than any suffix (longer than

n

The walk runs out of characters to match before finishing

P

, so

P

is not a substring — you fall off the tree, which correctly reports zero occurrences.

EC7. In banana$, why does the deepest branching node give ana and not anana?

anana occurs only once (it does not branch — a single continuation to a leaf), while ana is followed by two different things (na$ and $), so ana branches and is the longest string that repeats.

EC8. For a string with no repeats at all, what is the longest repeated substring?

The empty string — the only branching node is the root at depth 0, so the "deepest branch" has path length 0, correctly meaning nothing repeats.

Connections

Suffix tree (conceptual) — the parent concept these traps stress-test.
Trie — the uncompressed structure many of these errors confuse with the tree.
Suffix Array — the memory-lighter cousin; contrast its leaf-ordering idea.
Ukkonen's Algorithm — how the tree is actually built in $O (n)$ .
Longest Common Substring — extends the "deepest branching node" trap to two strings.