What is a Suffix Tree?
Learn what a suffix tree is, how it enables fast substring search, and how to explain it clearly in a technical interview.
Expected Interview Answer
A suffix tree is a compressed trie containing every suffix of a given string, built in O(n) time, that lets you answer substring existence, longest common substring, and repeated substring queries in time proportional to the pattern length rather than the whole text.
Instead of storing each suffix character by character like a plain trie, a suffix tree compresses chains of single-child nodes into one edge labeled with a substring, which keeps the tree size linear in the text length even though the sum of all suffix lengths is quadratic. Each leaf corresponds to one suffix, and internal nodes represent shared prefixes among multiple suffixes, so checking whether a pattern occurs in the text becomes a simple O(m) walk down the tree where m is the pattern length. Building one naively takes O(n²), but algorithms like Ukkonen's build it online in O(n) time. This structure underlies fast substring search, longest common substring between multiple strings, and genome sequence analysis where the same text is queried repeatedly with many different patterns.
- O(m) substring search after O(n) preprocessing
- Compressed edges keep the tree linear in text length
- Answers longest common substring and repeat queries efficiently
- Reusable across many pattern queries on the same text
AI Mentor Explanation
A suffix tree is like a coach who pre-indexes every possible tail-end sequence of a long innings commentary transcript — every suffix starting from each ball to the end — but compresses runs of identical continuation into single labeled branches instead of one branch per character. Checking whether a specific phrase like "six off the last ball" ever occurred becomes a quick walk down shared branches instead of rescanning the whole transcript. Building this indexed structure once takes effort proportional to the transcript length, but afterward, any phrase check is nearly instant. This is exactly why commentary-search tools can answer "has this ever happened before" so fast across a huge archive.
Step-by-Step Explanation
Step 1
Enumerate every suffix
Conceptually list every suffix of the string, from the full string down to its last character.
Step 2
Compress shared paths into edges
Merge chains of single-child nodes into one edge labeled with a substring, keeping the tree linear in text length.
Step 3
Build in linear time
Use an online algorithm like Ukkonen's to construct the tree in O(n) rather than the naive O(n²).
Step 4
Query by walking down
To check if a pattern exists, walk the tree matching characters against edge labels in O(m) time.
What Interviewer Expects
- Explain the tree contains every suffix of the string, compressed
- State O(m) substring search after O(n) preprocessing
- Mention Ukkonen's algorithm for linear-time construction
- Give real use cases: substring search, longest common substring, genome analysis
Common Mistakes
- Confusing a suffix tree with a trie of individual words rather than suffixes
- Assuming naive construction is O(n) instead of the O(n) achieved only via Ukkonen's algorithm
- Not mentioning edge compression, which is what keeps the tree linear-sized
- Forgetting suffix trees are best when the same text is queried repeatedly
Best Answer (HR Friendly)
“A suffix tree is a compressed structure that indexes every ending fragment of a string, so once it is built, checking whether any substring exists is very fast. I would reach for one when I need to answer many substring or repeated-pattern queries against the same large text, like in genome analysis or plagiarism detection.”
Code Example
def build_suffixes(text):
text = text + "$" # sentinel marks end of string
return sorted(text[i:] for i in range(len(text)))
def contains_substring(text, pattern):
# A real suffix tree walks compressed edges in O(m);
# this shows the concept with binary search over suffixes.
suffixes = build_suffixes(text)
lo, hi = 0, len(suffixes)
while lo < hi:
mid = (lo + hi) // 2
if suffixes[mid] < pattern:
lo = mid + 1
else:
hi = mid
return lo < len(suffixes) and suffixes[lo].startswith(pattern)
print(contains_substring("banana", "nan")) # TrueFollow-up Questions
- How does a suffix array compare to a suffix tree in space and construction time?
- How would you find the longest repeated substring using a suffix tree?
- How would you find the longest common substring between two strings?
- Why is edge compression essential for keeping a suffix tree linear in size?
MCQ Practice
1. After building a suffix tree in O(n), how long does a substring search of length m take?
Once built, a substring search walks the tree matching characters against edges, taking O(m) time.
2. What technique keeps a suffix tree's size linear in the text length despite the quadratic total length of all suffixes?
Edge compression merges long chains of single-path nodes into one labeled edge, keeping node count linear in n.
3. Which algorithm is known for constructing a suffix tree in O(n) time?
Ukkonen's algorithm builds a suffix tree online in linear time, avoiding the naive O(n²) construction.
Flash Cards
What does a suffix tree contain? — Every suffix of a given string, stored in a compressed trie.
What is the time complexity of a substring search after construction? — O(m), where m is the length of the pattern.
What algorithm builds a suffix tree in linear time? — Ukkonen's algorithm, in O(n).
Name a real-world use case for a suffix tree. — Genome sequence analysis, longest common substring, or repeated plagiarism-style substring search.